Certificateless designated verifier signature revisited: achieving a concrete scheme in the standard model

Abstract

In a designated verifier signature (DVS) scheme, the signer (Alice) creates a signature which is only verifiable by a designated verifier (Bob). Furthermore, Bob cannot convince any third party that the signature was produced by Alice. A DVS scheme is applicable in scenarios where Alice must be authenticated to Bob without disturbing her privacy. The de-facto construction of DVS scheme is achieved in a traditional public key infrastructure (PKI) setting, which unfortunately requires a high-cost certificate management. A variant of identity-based (ID-based) setting DVS eliminates the need of certificates, but it introduces a new inherent key escrow problem, which makes it impractical. Certificateless public key cryptography (CL-PKC) is empowered to overcome the problems of PKI and ID-based settings, where it does not suffer from any of the aforementioned problems. However, only a few number of certificateless DVS (CL-DVS) schemes have been proposed in the literature to date. Moreover, all existing CL-DVS schemes are only proven secure in the random oracle model, while some of them are already known to be insecure. We provide three contributions in this paper. First, we revisit the security proofs of existing CL-DVS schemes in the literature and show that unfortunately there are some drawbacks in the proofs of all of those schemes. Second, we concentrate on the recently proposed CL-DVS scheme (IEEE Access 2018) and show a drawback in its security proof which makes it unreliable. Furthermore, we show that this scheme is delegatable in contrast to the author’s claim. Finally, we propose a CL-DVS scheme and prove its security requirements in the standard model. Our scheme is not only the first scheme with a complete and correct security proofs, but also the only scheme in the standard model.

1 Introduction

A digital signature is a well-known primitive that provides integrity and authenticity of messages in cryptographic protocols [1]. In an ordinary digital signature scheme, the signer (Alice) creates a signature which is publicly verifiable by everyone. The privacy of Alice is not preserved in a traditional digital signature, since a verifier (Bob) can convince any third party about Alice’s signature by presenting her signature to the third party (without the need of Alice’s consent). This public verifiability of digital signatures is a useful and necessary property in some applications, but it is not a desirable property in some specific applications such as e-votings, e-auctions and fair exchanges, in which integrity and authenticity must be satisfied without disturbing the privacy of the signer. Many works have been devoted to overcome the conflicts between the authenticity and privacy of the signer in digital signatures. In 1989, the concept of undeniable signature was proposed in which some help of the signer is necessary in the verification phase [2]. In 1996, Jakobsson et al. [3] and Chaum [4] independently proposed the concept of designated verifier signature/proof (DVS/DVP), in order to avoid the interaction between the signer and the verifier. In a DVS scheme, a signer (Alice) generates a signature which can only be verified by a designated verifier (Bob). Moreover, Bob cannot transfer his conviction about Alice’s signature to any third party, since he can produce a signature which is indistinguishable from the one generated by Alice. Thus, the authenticity of Alice is proved to Bob and her privacy is preserved at the same time, without any interaction between Alice and Bob. Note that the main advantage of a DVS scheme in comparison with other privacy-preserving authentication schemes such as [5, 6] is privacy-preserved authentication of Alice to Bob without any reciprocal communications between Alice and Bob.

In a traditional public key cryptography (PKC), a user selects a public/private key pair (PK, SK) for him/herself. In a conventional public key infrastructure (PKI), a digital certificate is issued by a certificate authority (CA) to bind between the public key and the identity of a user. The management of the certificates requires a large amount of computation, storage and communication costs in a traditional PKI. To solve this problem, the notion of identity-based cryptography (ID-PKC) was put forth by Shamir in 1984 [7]. In an ID-PKC, a trusted third party called the private key generator (PKG) produces the private key of a user from his/her unique identifier information. An inherent problem of ID-PKC is the key escrow problem, i.e., the PKG knows all users’ private keys. To overcome these problems simultaneously, Al Riyami and Paterson introduced the concept of certificateless public key cryptography (CL-PKC) in 2003 [8]. In a CL-PKC, a public/secret key pair (PK, x) is generated by the user him/herself without requiring PK to be certified. Also, a partial private key d is created by a semi-trusted third party called key generation center (KGC), from the unique identifier information of the user. The knowledge of both x and d is required for a user to acquire his/her full private key SK. One can consider CL-PKC as an intermediate solution between a traditional PKI and ID-PKC.

The concept of certificateless designated verifier signature (CL-DVS) was put forward by Huang et al. [9]. Subsequently, only several CL-DVS schemes have been proposed in the literature [10,11,12,13,14,15,16,17]. Although these schemes are claimed to be secure in the random oracle model (ROM), unfortunately there exist some drawbacks in the security proofs of all of them. Additionally, the proposed scheme in [16] is insecure against the key replacement attack proposed in [18]. Furthermore, since the introduction of the notion of the malicious KGC attack in CL-PKC [19], the need for a secure scheme under this type of attack becomes essential. Unfortunately, as shown in [19, 20], the proposed CL-DVS schemes in [9, 14] are insecure against malicious KGC attack. There are also key-compromise and malicious KGC attacks against the scheme in [14] proposed in [21]. We should note that the malicious KGC attack was not claimed in the original paper of [9], but the work in [19] shows that there is some lack of completeness of this paper in accordance with the current state-of-the-art knowledge.

Our Contributions

We provide three contributions in this paper. First, we revisit the existing CL-DVS schemes and their security proofs and show that unfortunately there are issues in the security proofs of all of those schemes. Second, we concentrate on the recently proposed CL-DVS scheme [17] and show some drawbacks in its security proofs which make them unreliable. Moreover, we show that this scheme is delegatable in contrast to the author’s claim. Finally, we present a CL-DVS scheme and prove its security requirements without random oracles. Note that as Rogaway discussed in [22], the schemes which their security requirements are proved in the ROM might not be secure when the random oracles are replaced with the real-world primitives (such as hash functions). Therefore, we provide the security proof of our proposal in the standard model (without random oracles). Not only our proposal is the first CL-DVS scheme in the standard model, but also it does not suffer from the drawbacks in the security proofs of the previous proposals.

Paper Organization

In Sect. 2, we provide some preliminaries that will be used throughout this work. In Sect. 3, the formal model of a CL-DVS scheme is described. In Sect. 4, we provide a discussion on the security proofs of CL-DVS schemes. In Sect. 5, we provide a discussion on a recently proposed CL-DVS scheme (IEEE Access 2018) and show some drawbacks in this scheme. Subsequently, in Sect. 6, we propose our new CL-DVS scheme. In Sect. 7, we prove the security requirements of our proposal in the standard model. In Sect. 8, a comparison between our proposal and other existing schemes is provided. Finally, Sect. 9 concludes this work.

2 Preliminaries

2.1 Bilinear pairings

Consider two multiplicative cyclic groups $G_1$ and $G_2$ of prime order p and let g be a generator of $G_1$. The mapping $e:G_1\times G_1\longrightarrow G_2$ is an admissible bilinear pairing if and only if the following properties are satisfied:

• 1. Bilinearity: $e(g^a,g^b )=e(g,g)^{ab}$, for all $a,b\in \mathbb {Z}_p^*$.

• 2. Non-degeneracy: i. e., $e(g,g)\ne 1_{G_2}$.

• 3. Computability: There exists an efficient algorithm for computing e(g, g).

The readers can refer to [23] for more details about bilinear pairings.

2.2 Related complexity assumption

Consider a set of integers $\mathcal {S}\subset \mathbb {Z}$, and define $\mathcal {S}+_p \mathcal {S}\triangleq \{i+j$ mod $\lambda (p):i,j\in \mathcal {S}\}$, where $\lambda (p)$ is the order of elements modulo p. Also, consider another target integer $m \notin S+_p \mathcal {S}$. The $(\mathcal {S},m)$-Computational-Bilinear Diffie–Hellman Exponent-Set ($(\mathcal {S},m)$-CBDHE-Set) problem [24] is that on inputs $\{g^{a^i} \in G_1:i\in \mathcal {S}\}$, for unknown $a\in \mathbb {Z}_p^{*}$, calculate $e(g,g)^{a^m}$. It is said that $(\varepsilon ,t)$-$(\mathcal {S},m)$-CBDHE-Set assumption holds in $(G_1,G_2)$, if no t-time algorithm can solve the $(\mathcal {S},m)$-CBDHE-Set problem in $(G_1,G_2)$, with probability at least $\varepsilon$.

Remark 1

By assigning $\mathcal {S}=\mathcal {S}_K=\{0,1,2,\ldots ,K\}$, and $m=2K+1$, the $(\mathcal {S},m)$-CBDHE-Set problem is that on inputs $g,g^a,g^{a^2 },\ldots ,g^{a^K}\in G_1$, for unknown $a\in \mathbb {Z}_p^{*}$, calculate the value of $e(g,g)^{a^{2K+1}}$. The unforgeability of our proposed scheme is based on $(\mathcal {S}_2,5)$-CBDHE-Set and $(\mathcal {S}_4,9)$-CBDHE-Set assumptions against $\mathcal {A}_I$ and $\mathcal {A}_{II}$, respectively.

3 Formal model of CL-DVS

3.1 Algorithms and syntax

A CL-DVS scheme comprises three entities: the key generation center (KGC), the real signer (S) and the designated verifier (V). It is defined by the following eight algorithms [9]:

• Setup KGC runs this probabilistic polynomial time (PPT) algorithm which takes a security parameter $\lambda$ as input and outputs system parameters params and a master secret key msk. Then, KGC publishes params and keeps msk secret.

• Partial-Private-Key-Extract (PPKE) KGC runs this PPT algorithm which takes params, msk and an identity $ID_U\in \{0,1\}^{*}$ as input and outputs a partial private key $d_{U}$. Then KGC sends $d_{U}$ to the corresponding user via a secure channel.

• Set-Secret-Value (SSV) The user with identity $ID_U$ runs this PPT algorithm which takes params and $ID_U$ as input and outputs a random choice $x_{U}$. The user keeps $x_{U}$ as his secret value.

• Set-Private-Key (SPrK) The user with identity $ID_U$ runs this (P)PT algorithm which takes params, $ID_U$, $d_{U}$ and $x_{U}$ as input and outputs the user’s full private key $SK_{U}$.

• Set-Public-Key (SPuK) The user with identity $ID_U$ runs this PT algorithm which takes params, $ID_U$, $x_{U}$ (and maybe $d_U$) as input and outputs the user’s public key $PK_{U}$. The user publishes $PK_{U}$ without requiring to be certified.

• DVS Signing (DSign) The signer with identity $ID_S$ runs this (P)PT algorithm which takes params, a message m, the signer’s identity $ID_S$, the signer’s private key $SK_{S}$, the verifier’s identity $ID_V$ and the verifier’s public key $PK_{V}$ as input and outputs a signature $\sigma$ on message m.

• DVS Verification (DVer) The verifier with identity $ID_V$ runs this deterministic PT algorithm which takes params, a message/DVS pair $(m,\sigma )$, $ID_S$, $PK_S$, $ID_V$ and $SK_V$ as input and outputs 1 if $\sigma$ is valid and 0, otherwise.

• Transcript Simulation (TS) The verifier with identity $ID_V$ is able to run this algorithm to produce a signature $\sigma '$ which is indistinguishable from $\sigma$ created by the original signer.

Remark 2

The SPrK algorithm is defined based on one of the two following methods:

• SPrK1$SK_U$ is directly set as $x_U$ and $d_U$ (or maybe a part of $d_U$), i.e., $SK_U=(d_U,x_U)$, such as the schemes in [10, 11, 14,15,16,17].

• SPrK2$SK_U$ is set as a function of $d_U$ and $x_U$, i.e., $SK_U=func(d_U,x_U)$, such as the scheme in [9].

There are some subtle differences in oracle accesses in the security proof of CL-DVS schemes based on whether they use SPrK1 or SPrK2 algorithms, which will be discussed in Sect. 4.

3.2 Security requirements

Correctness, unforgeability and non-transferability (source hiding) are three basic security requirements of a CL-DVS scheme. They are described as follows.

• Correctness If the signer properly creates a CL-DVS by the DSign algorithm, then this signature must pass the DVer algorithm successfully.

• Unforgeability It is computationally infeasible to create a valid CL-DVS for everyone except the signer or the designated verifier. See Sect. 4 for more descriptions about the security model for proving the unforgeability of a CL-DVS scheme.

• Non-Transferability Given a message m and a CL-DVS $\sigma$ on m, it is infeasible to determine whether the original signer or the designated verifier creates $\sigma$, even if one knows all private keys.

Remark 3

In 2005, a new security notion called as non-delegatability was proposed for designated verifier signature schemes [25]. According to this property, neither the signer nor the designated verifier is able to delegate the signing rights to a third party without revealing his/her private key. However, the authors in [26] pointed out that although the non-delegatability has been a focus of many recent researches, it may be undesirable in some applications. Therefore, the non-delegatable DVS schemes should be considered as a special category which are useful in specific applications where the responsibility of the signer is important and cannot be delegated to another entity. Among all proposed CL-DVS schemes [9,10,11,12,13,14,15,16,17], only the schemes in [15,16,17] are claimed to be non-delegatable. However, the scheme in [16] is forgeable according to the attack proposed in [18]. Moreover, we show in Sect. 5.1 that the scheme in [17] is delegatable in contrast to its author’s claim. We should emphasize that our proposal (in Sect. 6) is not placed in the category of non-delegatable CL-DVS schemes, too.

4 A discussion on security proofs

In a certificateless public key cryptography, two types of adversaries are considered [9,10,11,12,13,14,15,16,17]:

• 1. The type I adversary $\mathcal {A}_I$ who cannot obtain the master secret key but he can replace the public key of an arbitrary entity because of the uncertified nature of the public keys generated by the users. In fact, $\mathcal {A}_I$ is a key replacement attacker.

• 2. The type II adversary $\mathcal {A}_{II}$ who possesses the master secret key but cannot replace any public keys (malicious KGC attacker).

In a CL-DVS scheme, the adversaries may access to the following oracles:

• Hash Oracle ($\mathcal {O}_{H}$): Given any input, returns its hash function.

• PPKE Oracle ($\mathcal {O}_{d}$): Given an identity $ID_U$, returns $d_{U}$.

• SPuK Oracle ($\mathcal {O}_{PK}$): Given an identity $ID_U$, returns $PK_{U}$.

• SSV Oracle ($\mathcal {O}_{x}$): Given an identity $ID_U$, returns $x_{U}$.

• SPrK Oracle ($\mathcal {O}_{SK}$): Given an identity $ID_U$, returns $SK_{U}$.

• Replace-Public-Key Oracle ($\mathcal {O}_{RPK}$): Given an identity $ID_U$ and a new valid public key $PK'_{U}$, replaces $PK_{U}$ with $PK'_{U}$.

• DSign Oracle ($\mathcal {O}_{S}$): Given a message m, $ID_S$ and $ID_V$, returns a valid signature $\sigma$ on m from S to V.

• DVer ($\mathcal {O}_{V}$): Given a signature $\sigma$, $ID_S$ and $ID_V$, returns 1 if $\sigma$ is valid and 0 otherwise.

The third and the forth columns of Table 1 show the oracle accesses of $\mathcal {A}_I$ and $\mathcal {A}_{II}$ in the proposed CL-DVS schemes, while the second column shows whether the scheme is based on SPrK1 or SPrK2 algorithms (which is described in Sect. 3.1). Note that $\mathcal {O}_I$ and $\mathcal {O}_{II}$ denote the set of oracles which can be accessed by $\mathcal {A}_I$ and $\mathcal {A}_{II}$, respectively.

Unforgeability of a CL-DVS scheme is defined by the two following games for type I and type II adversaries, respectively.

Game 1

A challenger $\mathcal {C}$ plays this game with $\mathcal {A}_I$ as follows:

• Setup$\mathcal {C}$ takes a security parameter $\lambda$ as input and produces params and msk. $\mathcal {C}$ sends params to $\mathcal {A}_I$ and keeps msk secret.

• Queries$\mathcal {A}_I$ issues polynomially bounded number of queries to the oracles in set $\mathcal {O}_I$ and $\mathcal {C}$ must answer these queries by simulating the oracles.

• Forgery Finally, $\mathcal {A}_I$ creates a forged message/signature $(m^{*},\sigma ^{*})$ from the signer with identity $ID_{S^{*}}$ to the verifier with identity $ID_{V^{*}}$.

Game 2

A challenger $\mathcal {C}$ plays this game with $\mathcal {A}_{II}$ as follows:

• Setup$\mathcal {C}$ takes a security parameter $\lambda$ as input and produces params and msk. $\mathcal {C}$ sends params and msk to $\mathcal {A}_{II}$.

• Queries$\mathcal {A}_{II}$ issues polynomially bounded number of queries to the oracles in set $\mathcal {O}_{II}$ and $\mathcal {C}$ must answer these queries by simulating the oracles.

• Forgery Finally, $\mathcal {A}_{II}$ creates a forged message/signature $(m^{*},\sigma ^{*})$ from the signer with identity $ID_{S^{*}}$ to the verifier with identity $ID_{V^{*}}$.

It is said that $\mathcal {A}_I$ wins Game 1 (or $\mathcal {A}_{II}$ wins Game 2) if $\sigma ^{*}$ is a valid signature on $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$ and meanwhile $\sigma ^{*}$ is not obtained from the $\mathcal {O}_{DSign}$ oracle. Moreover there are some trivial conditions that must be satisfied according to the oracle accesses and the construction of the scheme which will be discussed in Sect. 4.2.

Table 1 Oracle accesses in the existing CL-DVS schemes

4.1 A discussion on oracle accesses

Here, we provide a discussion on oracle accesses in the proposed CL-DVS schemes which are shown in Table 1. Note that the adversaries may obtain some information from the environment which must be simulated by the oracle accesses in the security model. As the authors in [11] do not model the oracle accesses, their security proof is not rigorous at all. So we do not consider this scheme in the following discussions.

When the security is proved in the ROM, the adversaries are considered to have access to $\mathcal {O}_{H}$. In fact, a hash function is simulated as a random oracle and as Rogaway discussed in [22], these schemes are not secure when the random oracles are replaced with the real hash functions. As the proposed CL-DVS schemes in [9, 10, 12,13,14,15,16,17] are provable in the ROM, the adversaries have access to $\mathcal {O}_{H}$ in the security proof of all of them.

In the security model of the schemes in [9, 10], the adversaries have only access to $\{\mathcal {O}_{H},\mathcal {O}_{S},\mathcal {O}_{V}\}$. In fact, in these schemes, only the existential unforgeability against chosen message attack (EUF-CMA) is considered in which the adversaries can only obtain a signature on every message m and the verification result on every signature from $ID_{S^{*}}$ to $ID_{V^{*}}$ and finally forge a signature on a new challenge message $m^{*}$ from $ID_{S^{*}}$ to $ID_{V^{*}}$. However, in a certificateless setting, the existential unforgeability against chosen message and identity attack (EUF-CM&IDA) must be considered in which the adversaries are considered more powerful as they can obtain the signature on every message m from every $ID_S$ to every $ID_V$, the verification result of every signature from every $ID_S$ to every $ID_V$, and even the keys of every $ID_U$ of their choice and finally forge a signature on a challenge message $m^{*}$ from $ID_S^{*}$ to $ID_V^{*}$. Hence, we concentrate on the security model of the schemes in [12,13,14,15,16,17] in which the EUF-CM&IDA is considered.

For considering EUF-CM&IDA, $\mathcal {A}_I$ has access to the oracles in set $\mathcal {O}_I=\{\mathcal {O}_{H},\mathcal {O}_{d},\mathcal {O}_{PK},\mathcal {O}_{x} (\text {and/or}\,\,\mathcal {O}_{SK}), \mathcal {O}_{RPK},\mathcal {O}_{S},\mathcal {O}_{V}\}$. However, $\mathcal {A}_{II}$ (a malicious KGC) possesses the master secret key and is able to obtain $d_U$ of every user, so he/she does not require to have access to $\mathcal {O}_{d}$ (while it is not any problem to consider $\mathcal {O}_{d}$ in set $\mathcal {O}_{II}$ such as [15, 17]). Moreover, it is assumed that $\mathcal {A}_{II}$ does not replace public keys and so he/she does not have access to $\mathcal {O}_{RPK}$, too. As a result, $\mathcal {A}_{II}$ has access to the oracles in set $\mathcal {O}_{II}=\{\mathcal {O}_{H},\mathcal {O}_{PK},\mathcal {O}_{x} (\text {and/or}\,\,\mathcal {O}_{SK}),\mathcal {O}_{S},\mathcal {O}_{V}\}$.

As shown in Table 1, all of the schemes in [12,13,14,15,16,17] are based on SPrK1 algorithms, i.e., $SK_U=(d_U,x_U)$, and the adversary can obtain $SK_U$ by obtaining $x_U$ from $\mathcal {O}_{x}$ and $d_U$ from $\mathcal {O}_{d}$, so it is not a requirement for simulating $\mathcal {O}_{SK}$ in these schemes. However, in the scheme in [15], only $\mathcal {O}_{SK}$ is considered which is in fact a combination of $\mathcal {O}_{x}$ and $\mathcal {O}_{d}$. In CL-DVS schemes based on the SPrK2 algorithm, $SK_U=func(x_U,d_U)$, i.e., $x_U$ is not directly used in the signing process and so it is sufficient to consider $\mathcal {O}_{SK}$ without simulating $\mathcal {O}_{x}$ [27].

As shown in Table 1, in the security proof of the scheme in [15], $\mathcal {O}_{V}$ is not simulated, so its security proof is unfortunately not rigorous as well. As a result, only in the proofs of the schemes in [12,13,14, 16, 17] the oracle accesses seems to be reasonable.

Table 2 The conditions for the success of $\mathcal {A}_I$ and $\mathcal {A}_{II}$

4.2 The conditions for the adversary success

As mentioned, it is said that $\mathcal {A}_I$ wins Game 1 (or $\mathcal {A}_{II}$ wins Game 2) if $\sigma ^{*}$ is a valid signature on $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$ and meanwhile $\sigma ^{*}$ is not obtained from the $\mathcal {O}_{DSign}$ oracle. Furthermore, there are some trivial conditions that must be satisfied according to the construction of the scheme and the oracle accesses. In this section, we provide a discussion on these conditions. We only consider the schemes in which EUF-CM&IDA is considered (i.e., the schemes in [12,13,14,15,16,17]).

It is obvious that $SK_{S^{*}}$ must not be extracted at any point, since it is trivial that by obtaining $SK_{S^{*}}$, the adversary can forge a signature by running the DSign algorithm. Moreover, as in all of the schemes in [12,13,14,15,16,17], the verifier can use his full private key $SK_V$ to create a valid signature by the TS algorithm, $SK_{V^{*}}$ must not be extracted at any point, too.

There are four conditions for the success of the adversary ($\mathcal {A}_I$ in Game 1 or $\mathcal {A}_{II}$ in Game 2) in the proposed schemes as follows:

• C1: $ID_{S^{*}}$ and $ID_{V^{*}}$ have not been submitted to $\mathcal {O}_{d}$.

• C2: $ID_{S^{*}}$ and $ID_{V^{*}}$ have not been submitted to $\mathcal {O}_{x}$.

• C3: $ID_{S^{*}}$ has not been submitted to $\mathcal {O}_{RPK}$.

• C4: $ID_{V^{*}}$ has not been submitted to $\mathcal {O}_{RPK}$.

There are some contradictions between the conditions which are considered in the definition and in the process of the proof for some of the proposed schemes. In Table 2, the conditions for winning $\mathcal {A}_I$ in Game 1 and $\mathcal {A}_{II}$ in Game 2 are summarized both in the definition and the process of the proof for the schemes in [12,13,14,15,16,17]. There are some considerations on Table 2 which will be described in Sects. 4.2.1 and 4.2.2.

4.2.1 The conditions for the success of $\mathcal {A}_I$ In Game 1

The conditions C1 and C2 are considered for preventing $\mathcal {A}_I$ from obtaining $SK_{S^{*}}$ and $SK_{V^{*}}$. Note that if $\mathcal {A}_I$ cannot obtain $d_{S^{*}}$ ($d_{V^{*}}$) he/she cannot obtain $SK_{S^{*}}$ ($SK_{V^{*}}$) even if he/she knows $x_{S^{*}}$ ($x_{V^{*}}$). Hence, the condition C1 seems to be sufficient and there is not any reason for considering the condition C2. In other words, C1 must be satisfied in Game 1, but there is not any necessity for satisfying C2, although there is not any problem to consider C1 and C2 together.

About the condition C3, note that $\mathcal {A}_I$ is a key replacement attacker who tries to forge a signature from a signer with identity $ID_{S^{*}}$ to the verifier with identity $ID_{V^{*}}$ via Game 1. Hence, it is not reasonable to prevent $\mathcal {A}_I$ from replacing the public key of $ID_{S^{*}}$, i.e., C3 is not a reasonable condition at all. Although the authors in [16] consider C3 in their definition of the success of $\mathcal {A}_I$ in Game 1, they do not consider this condition in their proof, so although their definition is not correct, their proof seems to be true in this sense. The only scheme for which this unreasonable condition (i.e., C3) is considered in the security proof is the scheme in [17], so its security proof against $\mathcal {A}_I$ is not rigorous at all (see Sect. 5.2 for more descriptions).

Although C3 is not reasonable, there is not any problem to consider C4 in the conditions of the $\mathcal {A}_I$’s success, since $\mathcal {A}_I$ does not gain any benefits from replacing $PK_{V^{*}}$. More precisely, note that $\mathcal {A}_I$ tries to forge a signature from $ID_{S^{*}}$ to $ID_{V^{*}}$ via Game 1, i.e., $\mathcal {A}_I$ is trying to cheat $ID_{V^{*}}$ by a forged signature from $ID_{S^{*}}$. Even if $\mathcal {A}_I$ has the permission to replace $PK_{V^{*}}$ with another public key $PK'_{V^{*}}$ in Game 1 and forges a signature $\sigma ^{*}$, he/she does not obtain any advantage from this replacement, as $ID_{V^{*}}$ uses his/her real public key $PK_{V^{*}}$ to verify the forged signature $\sigma ^{*}$. As a result, $\sigma ^{*}$ will not pass the DVer algorithm as it is a forged signature corresponding to $PK'_{V^{*}}$ not $PK_{V^{*}}$. So, as $\mathcal {A}_I$ does not gain any benefits from replacing $PK_{V^{*}}$, it is not unreasonable to consider C4 in the conditions of his/her success.

To sum up, considering C1, C2 and C4 is reasonable, while considering C3 is not reasonable for the success of $\mathcal {A}_I$ in Game 1. Hence, as shown in 2, the conditions for the success of $\mathcal {A}_I$ in Game 1 are reasonable in the proof of all of the schemes except the scheme in [17].

4.2.2 The conditions for the success of $\mathcal {A}_{II}$ in Game 2

Note that $\mathcal {A}_{II}$ is a malicious KGC attacker who possesses the master secret key, so he/she can compute the partial private key of every user and does not require to have access to $\mathcal {O}_{d}$. Moreover, $\mathcal {A}_{II}$ does not have access to $\mathcal {O}_{RPK}$ for any user. As a result the conditions C1, C3 and C4 are meaningless for $\mathcal {A}_{II}$’s success in Game 2. Although these conditions are considered in the definition of $\mathcal {A}_{II}$’s success in some papers (see Table 2), they are not considered in the process of the proof. Therefore, the only reasonable condition for the success of $\mathcal {A}_{II}$ in Game 2 is C2, as if $\mathcal {A}_{II}$ can obtain $x_{S^{*}}$ ($x_{V^{*}}$) he/she can easily obtain $SK_{S^{*}}$ ($SK_{V^{*}}$) as he/she knows all partial private keys. Hence, as shown in 2, the conditions for the success of $\mathcal {A}_{II}$ in Game 2 are reasonable in the proof of all of the schemes.

4.3 Probability analysis

It is well known that in a security proof, a simulator $\mathcal {B}$ is constructed which uses the adversary ($\mathcal {A}_{I}$ or $\mathcal {A}_{II}$) as a subroutine and tries to solve a hard problem. $\mathcal {B}$ must simulate $\mathcal {C}$ and all oracle accesses of $\mathcal {A}_{I}$ ($\mathcal {A}_{II}$) in Game 1 (Game 2). If the success probability of the adversary in his/her attack ($\varepsilon$) is non-negligible, then the success probability of $\mathcal {B}$ for solving the hard problem ($\varepsilon '$) must be non-negligible too, as would be a contradiction to the intractability of the hard problem. From this contradiction, we conclude that $\varepsilon$ is negligible. It is obvious that if $\varepsilon '$ is negligible, there is not any contradiction which leads us to conclude that $\varepsilon$ is negligible, and so a security proof is valueless without probability analysis. Unfortunately, probability analysis is not provided in none of the schemes in [12,13,14,15,16,17], except [15, 17].

5 Discussions on Lin’s scheme

Recently (in IEEE Access 2018), Lin proposed a CL-DVS scheme in the ROM with the claim of satisfying the following properties [17]:

• 1. Essential security properties, i.e., correctness, unforgeability (against $\mathcal {A}_I$ and $\mathcal {A}_{II}$) and non-transferability which are described in Sect. 4.

• 2. SSA-KCA (signer ambiguity against key-compromise attack) which is a notion introduced by Lin himself [17].

• 3. Non-delegatability which is described in Remark 3.

In this section, we first provide an overview on the algorithms of Lin’s Scheme. Then, we show that in contrast to his claim, his scheme is delegatable. Moreover, we have a comment on the proof of the unforgeability of his scheme.

5.1 An overview of Lin’s scheme

The algorithms of Lin’s CL-DVS scheme are as follows:

• Setup On input a security parameter $\lambda$, the KGC chooses a large prime p and an elliptic curve $E/F_p$ over the field $F_p$. Let $G_1$ be a cyclic additive group on $E/F_p$ and P be a base point of order q (another large prime) over $G_1$. The KGC also picks three collision-resistant hash functions $H_1:G_1\times \{0,1\}^{*}\longrightarrow \mathbb {Z}_q^{*}$, $H_2:G_1^4\longrightarrow \mathbb {Z}_q^{*}$ and $H_3:\{0,1\}^{*}\times G_1\longrightarrow G_1$. Moreover, the KGC selects a random $s\in _R \mathbb {Z}_q^{*}$ as his/her master secret key and computes $P_s=sP$ as his/her public key. The public parameters are $\varOmega =\{F_p,E/F_p,G_1,q,P,H_1,H_2,H_3,P_s\}$.

• PPKE On input an identity $ID_i$ (corresponding to the user $U_i$), the KGC first selects a random $u_i\in _R \mathbb {Z}_q^{*}$ and then computes $D_i=u_iP$, $q_i=H_1(D_i,ID_i)$ and $s_i=u_i+q_is \,\, \text {mod} \,\, q$. Then, the partial private key $S_i=(s_i,q_i,D_i)$ is returned to the user $U_i$. Each user can verify it by checking whether the equality $s_iP=D_i+q_iP_s$ holds or not.

• SSV The user $U_i$, selects a random $x_{i}\in _R \mathbb {Z}_q^{*}$ as his secret value and compute $Y_i=x_iP$.

• SPrK$U_i$ sets $SK_i=(x_i,s_i)$ as his/her full private key.

• SPuK$U_i$ sets $PK_i=(Y_i,q_i,D_i)$ as his/her public key.

• DSign Suppose that a signer $U_a$ wants to create a signature on a message m for a designated verifier $U_v$. The signer selects random values $w,r\in _R \mathbb {Z}_q^{*}$ and computes:

  $$\begin{aligned}&l=w+x_a, \quad K=ls_a(D_v+q_vP_s),\quad U=H_3(m,K),\\&R=rP-U=(r_x,r_y),\quad V=(r+w)Y_v,\\&Z=r_yx_aY_v, \quad h=H_2(U,R,Z,V). \end{aligned}$$

  Then returns $\sigma =(l,R,h)$ to $U_v$.

• DVer Upon receiving $\sigma =(l,R,h)$, $U_v$ computes:

  $$\begin{aligned}&W=lP-Y_a,\quad K'=ls_v(D_a+q_aP_s),\\&U'=H_3(m,K'),\\&V'=x_v(R+U'+W),\quad Z'=r_yx_vY_a,\\&h'=H_2(U',R,Z',V'). \end{aligned}$$

  If $h'=h$, $U_v$ accepts the signature and returns 1, otherwise rejects it and returns 0.

• TS$U_v$ is able to generate a signature on a message $m'$ which is indistinguishable from that created by $U_a$. In order to simulate a signature on a message $m'$, $U_v$ first selects two random values $l'\in _R \mathbb {Z}_q^{*}$ and $R' \in _R G_1$ and then computes:

  $$\begin{aligned}&W'=l'P-Y_a, \quad K'=l's_v(D_a+q_aP_s),\\&U'=H_3(m',K'),\\&V'=x_v(R'+U'+W'),\quad Z'=r'_yx_vY_a,\\&h'=H_2(U',R',Z',V'). \end{aligned}$$

  Then returns $\sigma '=(l',R',h')$.

5.2 On delegatability of Lin’s scheme

Lin claimed that his scheme is non-delegatable and has tried to prove this claim in Theorem 1 of [17]. However, we show that his scheme is delegatable, as everyone who knows the common secret key of $U_a$ and $U_v$, i.e., $Comm.Key=(s_as_vP,x_ax_vP)$, is able to produce a valid signature $\sigma ^{*}$ on a message m by selecting random values $l^{*},r^{*}\in _R \mathbb {Z}_q^{*}$ and computing:

$$\begin{aligned}&K^{*}=l^{*}s_as_vP,\quad U^{*}=H_3(m,K^{*}),\\&R^{*}=r^{*}P-U^{*}=(r^{*}_x,r^{*}_y)\\&V^{*}=(r^{*}+l^{*})Y_v-x_ax_vP,\quad Z^{*}=r^{*}_yx_ax_vP, \\&h^{*}=H_2(U^{*},R^{*},Z^{*},V^{*}). \end{aligned}$$

It is easy to check that $\sigma ^{*}=(l^{*},R^{*},h^{*})$ is a valid signature since it passes the DVer algorithm successfully as:

$$\begin{aligned}&W=l^{*}P-Y_a,\\&K'=l^{*}s_v(D_a+q_aP_s)=l^{*}s_vs_aP=l^{*}s_as_vP=K^{*},\\&U'=H_3(m,K')=H_3(m,K^{*})=U^{*},\\&V'=x_v(R^{*}+U'+W)=x_v(r^{*}P-U^{*}+U^{*}+l^{*}P-Y_a)\\&\quad =r^{*}x_vP+l^{*}x_vP-x_vx_aP=(r^{*}+l^{*})Y_v-x_ax_vP=V^{*}\\&Z'=r^{*}_yx_vY_a=r^{*}_yx_vx_aP=r^{*}_yx_ax_vP=Z^{*},\\&h'=H_2(U',R^{*},Z',V')=H_2(U^{*},R^{*},Z^{*},V^{*})=h^{*}. \end{aligned}$$

In other words, it is not necessary to know $SK_a=(x_a,s_a)$ (or $SK_v=(x_v,s_v)$) to create a valid signature and the knowledge of only $Comm.Key=(s_as_vP,x_ax_vP)$ is sufficient to generate a valid signature. Note that the signer $U_a$ can compute $Comm.Key=(s_a(D_v+q_vP),x_aY_v)$ and delegate the signing rights to every third party by only revealing Comm.Key to him/her (and of course without revealing $SK_a$). As a result, in contrast to his claim, Lin’s scheme is not located in the class of non-delegatable CL-DVS schemes.

5.3 On unforgeability of Lin’s scheme

Lin also claimed that his scheme is unforgeable against $\mathcal {A}_{I}$ and $\mathcal {A}_{II}$ in the ROM based on CDH assumption and has tried to prove this claim in Theorem 4 of his paper [17]. However, there is an important drawback in the process of the proof of Theorem 4 which makes it unreliable. The drawback is that in the security proof against $\mathcal {A}_{I}$, the public keys of $U_{a^{*}}$ and $U_{v^{*}}$ are assigned as $PK_{a^{*}}=(cP,q_{a^{*}},D_{a^{*}})$ and $PK_{v^{*}}=(dP,q_{v^{*}},D_{v^{*}})$, respectively, where cP and dP are the inputs of the CDH problem which $\mathcal {B}$ is trying to solve it. If these public keys be replaced, then the claims in the following of the proof are no longer hold. However, as discussed in Sect. 4.2.1, the condition of not replacing $PK_{a^{*}}$ (i.e., C3) is not reasonable at all. As a result, the unforgeability against $\mathcal {A}_{I}$ becomes questionable.

6 Our proposed scheme

6.1 The algorithms of our proposal

In this subsection, we propose our CL-DVS scheme based on the ideas of the certificateless signature scheme in [28] which is based on Waters’ identity-based encryption scheme [29]. Generality, identities can be considered of arbitrary lengths and a hash function $H_u:\{0,1\}^{*}\longrightarrow \{0,1\}^{n_u}$ can be used to convert them to the specific length $n_u$. The algorithms of our scheme are as follows:

• Setup On input a security parameter $\lambda$, the KGC selects two multiplicative cyclic groups $G_1$ and $G_2$ of a large prime order p, a random generator g of $G_1$ and a bilinear pairing $e:G_1\times G_1\longrightarrow G_2$. It also selects a random $s\in _R \mathbb {Z}_p^{*}$ and sets $g_1=g^{s}$. Furthermore, it picks random values $g_2,u'\in _R G_1$ and a random vector $\overrightarrow{u}=(u_i)\in _R G_1^{n_u}$, where $u_i \in _R G_1$, for $i=1,\ldots ,n_u$, then computes $T=e(g_1,g_2)$ and $T'=e(g_1,g)$. It also chooses two collision-resistant hash functions $H_u:\{0,1\}^{*}\longrightarrow \{0,1\}^{n_u}$ and $H:\{0,1\}^{*}\times G_1^{8}\longrightarrow \mathbb {Z}_p^{*}$. The public system parameters are $params=\{G_1,G_2,p,e,g,g_1,g_2,u',\overrightarrow{u},T,T',H_u,H\}$, and the master secret key is $msk=g^{{s}^2}$.

• PPKE On input an identity $ID_U$, the KGC calculates $H_u(ID_U)$. Let u[i] denotes the ith bit of $H_u(ID_U)$ and $\mathcal {U}_{U}=\{i|u[i]=1,i=1,\ldots ,n_u\}$. The KGC randomly selects $r_{U}\in _R \mathbb {Z}_p^{*}$ and computes $d_{U}$, as follows:

  $$\begin{aligned} d_{U}=(d_{U,1},d_{U,2})=\left( g^{s^2}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i \right) ^{r_{U}},g^{r_{U}}\right) . \end{aligned}$$

• SSV The user with identity $ID_U$ selects a random $x_{U}\in _R \mathbb {Z}_p^{*}$ as his secret value.

• SPrK The user with identity $ID_U$ picks a random $r'_{U}\in _R \mathbb {Z}_p^{*}$ and computes his private key as follows:

  $$\begin{aligned} SK_{U}&=(SK_{U,1},SK_{U,2})\\&=\left( d_{U,1}^{x_{U}^2}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r'_{U}},d_{U,2}^{x_{U}^2}g^{r'_U}\right) \\&=\left( g^{s^2x_{U}^2}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r_{U}x_{U}^2+r'_U},g^{r_{U}x_{U}^2+r'_U}\right) \end{aligned}$$

• SPuK The user with identity $ID_U$ computes his public key as follows:

  $$\begin{aligned} PK_{U}=(PK_{U,1},PK_{U,2},PK_{U,3})=\left( g_1^{x_{U}},g_2^{\frac{1}{x_{U}}}, g^{\frac{1}{x_{U}}}\right) . \end{aligned}$$

  Then the user publishes $PK_U$ without requiring it to be certified.

• DSign Suppose that a signer with identity $ID_S$, wants to create a signature on a message m for a designated verifier with identity $ID_V$. The signer selects a random $r_m\in _R \mathbb {Z}_p^{*}$ and executes the following steps:

  • 1. Checks whether $e(PK_{V,1},PK_{V,2})=T$ and $e(PK_{V,1},PK_{V,3})=T'$ hold or not. If one of the equalities does not hold, aborts and outputs $\perp$.

  • 2. Sets $\sigma _1=SK_{S,2}$.

  • 3. Sets $\sigma _2=g^{r_m}$.

  • 4. Computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$.

  • 5. Sets $\sigma _3=e(SK_{S,1}PK_{S,2}^{hr_m},PK_{V,3})$.

  • 6. Outputs $\sigma =(\sigma _1,\sigma _2,\sigma _3)$.

• DVer Upon receiving $(m,\sigma )$ from the signer, the designated verifier checks the validity of $\sigma =(\sigma _1,\sigma _2,\sigma _3)$ as follows:

  • 1. Checks whether $e(PK_{S,1},PK_{S,2})=T$ and $e(PK_{S,1},PK_{S,3})=T'$ hold or not. If one of the equalities does not hold, aborts and outputs $\perp$.

  • 2. Computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$.

  • 3. Verifies the following equality:

    $$\begin{aligned}&\sigma _3=(e(PK_{S,1},PK_{S,1}).e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,\sigma _1\right) \nonumber \\&\quad .e(PK_{S,2}^h,\sigma _2))^{\frac{1}{x_V}}. \end{aligned}$$

    (1)

    If Eq. (1) holds, the verifier accepts the signature and outputs 1, otherwise rejects it and outputs 0.

• TS The verifier is able to generate a signature on m which is indistinguishable from that created by the real signer as follows:

  • 1. Sets $\sigma _1=SK_{S,2}$. Note that the verifier can obtain $SK_{S,2}$ from the previously signed messages by the signer.

  • 2. Selects a random $r_m\in _R \mathbb {Z}_p^{*}$ and computes $\sigma _2=g^{r_m}$.

  • 3. Computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$.

  • 4. Computes:

    $$\begin{aligned}&\sigma _3=(e(PK_{S,1},PK_{S,1}).e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,\sigma _1\right) \\&\quad .e(PK_{S,2}^h,\sigma _2))^{\frac{1}{x_V}}. \end{aligned}$$

  Then returns $\sigma =(\sigma _1,\sigma _2,\sigma _3)$.

6.2 Some considerations

Note that the DVer algorithm is defined similarly in all proposed CL-DVS schemes in [9,10,11,12,13,14,15,16,17, 19] as it takes params, a message/DVS pair $(m,\sigma )$, $ID_S$, $PK_S$, $ID_V$ and $SK_V$ as input and outputs 1 if $\sigma$ is valid and 0, otherwise. However, it is necessary for a strong DVS (not DVS) that DVer takes $SK_V$ as input. In our proposed scheme (which is a DVS), the verifier can execute the DVer algorithm with only his secret value $x_V$, i.e., $SK_V$ is not required to be an input of the DVer algorithm.

We consider the set of oracles that can be accessed by $\mathcal {A}_I$ and $\mathcal {A}_{II}$ as $\mathcal {O}_{I}=\{\mathcal {O}_{d},\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{RPK},\mathcal {O}_{S},\mathcal {O}_{V}\}$ and $\mathcal {O}_{II}=\{\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{S},\mathcal {O}_{V}\}$, respectively. As our proof is in the standard model, we do not consider $\mathcal {O}_{H}$, and as our scheme is based on SPrK2, we only consider $\mathcal {O}_{SK}$ without requiring to simulate $\mathcal {O}_{x}$ (See Sect. 4.1).

We say that $\mathcal {A}_I$ wins Game 1 if $\sigma ^{*}$ is a valid signature on $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$ and meanwhile $\sigma ^{*}$ is not obtained from the $\mathcal {O}_{DSign}$ oracle. Furthermore:

• $ID_{S^{*}}$ has not been submitted to $\mathcal {O}_{d}$ and $\mathcal {O}_{SK}$.

• $ID_{V^{*}}$ has not been submitted to $\mathcal {O}_{RPK}$.

The first condition is considered to prevent $\mathcal {A}_I$ from obtaining $SK_{S^{*}}$. Note that as only $x_{V^{*}}$ (not $SK_{V^{*}}$) is used in the TS algorithm, there is not any reason to prevent $\mathcal {A}_I$ from obtaining $SK_{V^{*}}$. Moreover, the second case is C4 which is a reasonable condition as discussed in Sect. 4.2.1.

We say that $\mathcal {A}_{II}$ wins Game 2 if $\sigma ^{*}$ is a valid signature on $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$ and meanwhile $\sigma ^{*}$ is not obtained from the $\mathcal {O}_{DSign}$ oracle. Furthermore:

• $ID_{S^{*}}$ has not been submitted to $\mathcal {O}_{SK}$.

This condition is considered to prevent $\mathcal {A}_{II}$ from obtaining $SK_{S^{*}}$.

According to the above descriptions, we use the following definition for proving the unforgeability of our scheme in Sect. 7.2:

Definition 1

A CL-DVS scheme is $(\varepsilon ,t,q_d,q_{sk},q_{pk},q_{r},q_s,q_v)$-EUF-CM&IDA if no adversaries ($\mathcal {A}_{I}$ and $\mathcal {A}_{II}$) running in time at most t, making at most $q_{d}$ PPKE queries from $\mathcal {O}_{d}$ ($q_{d}=0$ for $\mathcal {A}_{II}$), $q_{sk}$ SPrK queries from $\mathcal {O}_{SK}$, $q_{pk}$ SPuK queries from $\mathcal {O}_{PK}$, $q_{r}$ Replace-Public-Key queries from $\mathcal {O}_{RPK}$ ($q_{r}=0$ for $\mathcal {A}_{II}$), $q_s$ DSign queries from $\mathcal {O}_{S}$ and $q_v$ DVer queries from $\mathcal {O}_{V}$, wins Game 1 and Game 2 with probability at least $\varepsilon$.

7 Security analysis of the proposed scheme

7.1 Correctness

The correctness of the proposed scheme can be easily verified as:

$$\begin{aligned}&\sigma _3 = e(SK_{S,1}PK_{S,2}^{hr_m},PK_{V,3})\\&\quad =e\left( g^{s^2x_S^2}\left( u'\prod _{i\in \mathcal {U}_{S}}u_i\right) ^{r_Sx_S^2+r'_{S}}PK_{S,2}^{hr_m},g^{\frac{1}{x_{V}}}\right) \\&\quad =\left( e(g^{s^2x_S^2},g).e\left( \left( u'\prod _{i\in \mathcal {U}_{S}}u_i\right) ^{r_Sx_S^2+r'_{S}},g\right) .e(PK_{S,2}^{hr_m},g)\right) ^{\frac{1}{x_{V}}}\\&\quad =\left( e(g_1^{x_S},g_1^{x_S}).e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,g^{r_Sx_S^2+r'_{S}}\right) .e(PK_{S,2}^h,g^{r_m})\right) ^{\frac{1}{x_{V}}}\\&\quad =\left( e(PK_{S,1},PK_{S,1}).e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,\sigma _1\right) .e(PK_{S,2}^h,\sigma _2)\right) ^{\frac{1}{x_V}}, \end{aligned}$$

which shows the correctness of Eq. (1).

7.2 Unforgeability

Theorem 1

The proposed scheme is $(\varepsilon ,t,q_d,q_{sk},q_{pk},q_{r},q_s,q_v)$-unforgeable against $\mathcal {A}_{I}$, if the $(\varepsilon ',t')$-$(\mathcal {S}_2,5)$-CBDHE-Set assumption holds in $(G_1,G_2)$, where

$$\begin{aligned}&\varepsilon ' \ge \frac{\varepsilon }{4(q_{d}+q_{sk}+q_s+q_v+1)(n_u+1)},\\&t'\le t+order(((q_{d}+q_{sk}+q_s+q_v)n_u)T_M\\&\qquad +(q_{pk}+q_{d}+q_{sk}+q_s+q_v)T_E+(q_r+q_s+q_v)T_P), \end{aligned}$$

in which $T_M$, $T_E$ and $T_P$ are the time for a multiplication and exponentiation in $G_1$ and a pairing computation, respectively.

Proof

Suppose that there exists a $(\varepsilon ,t,q_d,q_{sk},q_{pk},q_{r},q_s,q_v)$-type I adversary $\mathcal {A}_{I}$, who can break the EUF-CM&IDA in the proposed scheme according to Game 1 and forge a DVS $\sigma ^{*}$ on message $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$. By this assumption, we can construct a simulator $\mathcal {B}$ that can use $\mathcal {A}_{I}$ as a subroutine and solve an instance of a $(\mathcal {S}_2,5)$-CBDHE-Set problem with a probability at least $\varepsilon '$ and in time at most $t'$, which contradicts the $(\varepsilon ',t')$-$(\mathcal {S}_2,5)$-CBDHE-Set assumption in $(G_1,G_2)$.

Consider two multiplicative cyclic groups $G_1$ and $G_2$ of a large prime order p and a random generator g of $G_1$. Let $e:G_1\times G_1\longrightarrow G_2$ be a bilinear pairing. Suppose that $\mathcal {B}$ is given a random $(\mathcal {S}_2,5)$-CBDHE-Set challenge $(g\in G_1,A=g^a\in G_1,B=g^{a^2}\in G_1)$ and is requested to output $e(g,g)^{a^5}\in G_2$. In order to use $\mathcal {A}_{I}$ as a subroutine, $\mathcal {B}$ must simulate the challenger $\mathcal {C}$ and answer all ${\mathcal {A}_I}$’s queries in Game 1, i.e., the queries from the oracles in set $\mathcal {O}_{I}=\{\mathcal {O}_{d},\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{RPK},\mathcal {O}_{S},\mathcal {O}_{V}\}$. In order to respond these queries consistently, $\mathcal {B}$ generates a list $\mathcal {L}=\{(ID_U,d_{U},x_{U},PK_{U},SK_{U},sta_U=0)\}$ which is initially empty. Then $\mathcal {B}$ plays Game 1 with $\mathcal {A}_{I}$ as follows:

Setup Let $l=2(q_{d}+q_{sk}+q_s+q_v+1)$ and assume that $l(n_u+1)<p$. $\mathcal {B}$ chooses $k\in _R \{0,1,\ldots ,n_u\}$ (Note that $0\le kl<p$, as $l(n_u+1)<p$). $\mathcal {B}$ also picks random values $x',x_1,\ldots ,x_{n_u} \in _R \mathbb {Z}_{l}$, $y',y_1,\ldots ,y_{n_u} \in _R \mathbb {Z}_p$, and $z \in _R \mathbb {Z}_p$. These values are kept internal to $\mathcal {B}$. Then $\mathcal {B}$ assigns a set of public parameters as follows:

$$\begin{aligned}&g_1=B=g^{a^2}, \quad \quad \quad \, g_2=g^z,\\&u'=B^{-kl+x'}g^{y'}, \quad \quad u_i=B^{x_i}g^{y_i}\quad (\text {for} \quad i=1,2,\ldots ,n_u). \end{aligned}$$

$\mathcal {B}$ also computes $T=e(g_1,g_2)$ and $T'=e(g_1,g)$, then selects two collision-resistant hash functions $H_u:\{0,1\}^{*}\longrightarrow \{0,1\}^{n_u}$ and $H:\{0,1\}^{*}\times G_1^{8}\longrightarrow \mathbb {Z}_p^{*}$ and gives $params=\{G_1,G_2,p,e,g,g_1,g_2,u',\overrightarrow{u},T,T',H_u,H\}$ to $\mathcal {A}_I$. For simplicity of analysis, define two functions:

$$\begin{aligned} F(U)=x'+\sum _{i\in \mathcal {U}_{U}}x_i-kl \quad \text {and} \quad J(U)=y'+\sum _{i\in \mathcal {U}_{U}}y_i, \end{aligned}$$

where $\mathcal {U}_{U}$ is defined similar to that in the proposed scheme. Then, we have

$$\begin{aligned} u'\prod _{i\in \mathcal {U}_{U}}u_i=B^{F(U)} g^{J(U)}. \end{aligned}$$

Note that by these assignments, $\mathcal {B}$ does not know the master secret key, $msk=g^{a^4}$, and he/she must simulate $\mathcal {C}$ and answer all $\mathcal {A}_I$’s queries in Game 1 without the knowledge of msk. Moreover, note that by the mentioned settings, all distributions are identical to those in the real world from the perspective of $\mathcal {A}_I$.

Queries In this step, $\mathcal {A}_I$ sends polynomially bounded number of queries to the oracles in set $\mathcal {O}_{I}=\{\mathcal {O}_{d},\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{RPK},\mathcal {O}_{S},\mathcal {O}_{V}\}$. $\mathcal {B}$ responds to $\mathcal {A}_I$’s queries by simulating these oracles as follows:

$\mathcal {O}_{d}$. As $\mathcal {A}_I$ issues a partial private key query for an identity $ID_U$ to $\mathcal {O}_{d}$, $\mathcal {B}$ looks up $\mathcal {L}$ to find $d_{U}$ and sends it to $\mathcal {A}_I$. If $d_{U}$ does not exist in $\mathcal {L}$, $\mathcal {B}$ tries to produce $d_{U}$ without the knowledge of msk key as follows:

• If $F(U)=0$ mod p, $\mathcal {B}$ aborts the simulation.

• If $F(U)\ne 0$ mod p, $\mathcal {B}$ picks a random $r_U\in \mathbb {Z}_p^{*}$ and constructs $d_{U}$ as follows:

  $$\begin{aligned} d_{U}&=\left( B^{-\frac{J(U)}{F(U)}}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r_U},B^{-\frac{1}{F(U)}}g^{r_U}\right) \\&=\left( g^{{a}^4}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{\tilde{r}_U},g^{\tilde{r}_U}\right) =(d_{U,1},d_{U,2}), \end{aligned}$$

  where $\tilde{r}_U=r_U-\frac{a^2}{F(U)}$. Then $\mathcal {B}$ sends $d_{U}$ to $\mathcal {A}_I$ and adds it in $\mathcal {L}$.

$\mathcal {O}_{PK}$. As $\mathcal {A}_I$ issues a public key query for an identity $ID_U$ to $\mathcal {O}_{PK}$, $\mathcal {B}$ looks up $\mathcal {L}$ to find $PK_U$ and sends it to $\mathcal {A}_I$. If $PK_U$ does not exist in $\mathcal {L}$, $\mathcal {B}$ picks a random $x_{U}\in _R \mathbb {Z}_p^{*}$ and acts as follows:

• If $F(U)=0$ mod p, $\mathcal {B}$ sets $PK_{U}=(g_1^{x_{U}},g_2^{\frac{1}{x_{U}}},g^{\frac{1}{x_{U}}})$. Note that by this assignment, the real secret value of $ID_U$ is $x_U$, which is known to $\mathcal {B}$.

• If $F(U)\ne 0$ mod p, $\mathcal {B}$ sets $PK_{U}=(A^{\frac{1}{x_{U}}},A^{zx_U},A^{x_U})$. Note that by this assignment, the real secret value of $ID_U$ is $\frac{1}{ax_{U}}$, which is unknown to $\mathcal {B}$.

Then, $\mathcal {B}$ sends $PK_U$ to $\mathcal {A}_I$. Furthermore, $\mathcal {B}$ adds $PK_{U}$ and its corresponding $x_{U}$ in $\mathcal {L}$.

$\mathcal {O}_{RPK}$. Suppose that $\mathcal {A}_I$ requests to replace the public key of an identity $ID_U$, i.e., $PK_U$ with respect to $x_U$ with a new public key $PK'_U=(PK'_{U,1},PK'_{U,2},PK'_{U,3})$ with respect to $x'_U$. $\mathcal {B}$ firstly checks whether $e(PK'_{U,1},PK'_{U,2})=T$ and $e(PK'_{U,1},PK'_{U,3})=T'$ hold or not. If both equalities hold, $\mathcal {B}$ looks up $\mathcal {L}$ to replace $(x_{U},PK_U)$ with $(x'_{U},PK'_U)$ and sets $sta_U=1$. If $(x_{U},PK_U)$ does not exist in $\mathcal {L}$, $\mathcal {B}$ directly sets $(x_{U},PK_{U})=(x'_{U},PK'_{U})$ and $sta_U=1$ in $\mathcal {L}$. Note that $\mathcal {A}_I$ can only replace $PK_U$ with a new correctly constructed $PK'_U=(g_1^{x'_{U}},g_2^{\frac{1}{x'_{U}}},g^{\frac{1}{x'_{U}}})$ as $e(PK'_{U,1},PK'_{U,2})=T$ and $e(PK'_{U,1},PK'_{U,3})=T'$ must be satisfied. So $\mathcal {A}_I$ knows $x'_U$ corresponding to $PK'_U$.

$\mathcal {O}_{SK}$. As $\mathcal {A}_I$ issues a private key query for an identity $ID_U$ to $\mathcal {O}_{SK}$, $\mathcal {B}$ looks up $\mathcal {L}$ to find $SK_U$ and sends it to $\mathcal {A}_I$. If $SK_U$ does not exist in $\mathcal {L}$, $\mathcal {B}$ acts as follows:

• If $F(U)=0$ mod p, $\mathcal {B}$ aborts the simulation.

• If $F(U)\ne 0$ mod p, $\mathcal {B}$ acts as follows:

  • If $sta_U=0$ (i.e., $PK_U$ has not been replaced and hence the real secret value of $ID_U$ is $\frac{1}{ax_{U}}$), $\mathcal {B}$ picks a random $r''_U\in \mathbb {Z}_p^{*}$ and sets:

    $$\begin{aligned} SK_{U}&=\left( B^{\frac{1}{x_U^2}}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r''_U},g^{r''_U}\right) \\&=\left( g^{{a}^4\left( \frac{1}{ax_U}\right) ^2}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r''_U},g^{r''_U}\right) \\&=(SK_{U,1},SK_{U,2}), \end{aligned}$$

    where $r''_U=\tilde{r}_U(\frac{1}{ax_U})^2+r'_U$. Then, $\mathcal {B}$ returns $SK_U$ to $\mathcal {A}_I$ and also stores it in $\mathcal {L}$.

  • If $sta_U=1$ (i.e., $PK_U$ has been replaced with $PK'_U$), $\mathcal {B}$ can retrieve $x_U$ (which is in fact $x'_U$ corresponding to $PK'_U$) from $\mathcal {L}$. Then $\mathcal {B}$ picks $d_U$ from $\mathcal {L}$ if exists, otherwise $\mathcal {B}$ obtain $d_U$ by simulating $\mathcal {O}_{d}$ as described (note that as $F(U)\ne 0$ mod p, $\mathcal {B}$ can simulate $\mathcal {O}_{d}$ without aborting). Finally, $\mathcal {B}$ can obtain $SK_U$ by running the SPrK algorithm, since he knows both $x_{U}$ and $d_U$. So $\mathcal {B}$ generates $SK_U$, returns it to $\mathcal {A}_I$ and also stores it in $\mathcal {L}$.

$\mathcal {O}_{S}$. As $\mathcal {A}_I$ issues a signature query for $(m,ID_S,ID_V)$ to $\mathcal {O}_{S}$, $\mathcal {B}$ searches $\mathcal {L}$ to find $SK_{S}$. If this entry exists in $\mathcal {L}$, $\mathcal {B}$ picks it and creates a signature on m by running the DSign algorithm and returns it to $\mathcal {A}_I$, otherwise $\mathcal {B}$ acts as follows:

• If $F(S)\ne 0$ mod p, $\mathcal {B}$ obtains $SK_S$ by simulating $\mathcal {O}_{SK}$, then creates a signature on m by running the DSign algorithm and returns it to $\mathcal {A}_I$.

• If $F(S)=0$ mod p, $\mathcal {B}$ acts as follows:

  • If $sta_V=1$ (i.e., $PK_V$ has been replaced with $PK'_V$), $\mathcal {B}$ can retrieve $x_V$ (which is in fact $x'_V$ corresponding to $PK'_V$) from $\mathcal {L}$, then creates a signature on m by running the TS algorithm and returns it to $\mathcal {A}_I$.

  • If $sta_V=0$ (i.e., $PK_V$ has not been replaced), $\mathcal {B}$ acts as follows:

    • If $F(V){=}0$ mod p, i.e., $PK_{V}{=}(g_1^{x_{V}},g_2^{\frac{1}{x_{V}}},g^{\frac{1}{x_{V}}})$, $\mathcal {B}$ can retrieve $x_V$ from $\mathcal {L}$, then creates a signature on m by running the TS algorithm and returns it to $\mathcal {A}_I$.

    • If $F(V)\ne 0$ mod p, $\mathcal {B}$ aborts the simulation. (Note that in this case, $PK_{V}{=}(A^{\frac{1}{x_{V}}},A^{zx_V},A^{x_V})$, and $\mathcal {B}$ cannot retrieve the real secret value of $ID_V$, i.e., $\frac{1}{ax_{V}}$.)

$\mathcal {O}_{V}$. As $\mathcal {A}_I$ issues a verification query for $((m,\sigma =(\sigma _1,\sigma _2,\sigma _3)),ID_S,ID_V)$ to $\mathcal {O}_{V}$, $\mathcal {B}$ acts as follows:

• If $sta_V=1$ (i.e., $PK_V$ has been replaced with $PK'_V$), $\mathcal {B}$ can retrieve $x_V$ (which is in fact $x'_V$ corresponding to $PK'_V$) from $\mathcal {L}$, then verifies $\sigma$ by running the DVer algorithm and sends the result to $\mathcal {A}_I$.

• If $sta_V=0$ (i.e., $PK_V$ has not been replaced), $\mathcal {B}$ acts as follows:

  • If $F(V)=0$ mod p, i.e., $PK_{V}=(g_1^{x_{V}},g_2^{\frac{1}{x_{V}}},g^{\frac{1}{x_{V}}})$, $\mathcal {B}$ can retrieve $x_V$ from $\mathcal {L}$, then verifies $\sigma$ by running the DVer algorithm and sends the result to $\mathcal {A}_I$.

  • If $F(V)\ne 0$ mod p, $\mathcal {B}$ cannot retrieve the real secret value of $ID_V$, i.e., $\frac{1}{ax_{V}}$. In this case, $\mathcal {B}$ picks $x_V$. Then, $\mathcal {B}$ acts as follows:

    • If $F(S)\ne 0$ mod p, $\mathcal {B}$ obtains $SK_S$ by simulating $\mathcal {O}_{SK}$. Then, $\mathcal {B}$ acts as follows:

      • If $sta_S=0$, (i.e., $PK_{S}=(A^{\frac{1}{x_{S}}},A^{zx_S},A^{x_S})$ which has not been replaced), $\mathcal {B}$ retrieves $x_S$, computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$ and verifies $\sigma$ by checking the following equation:

        $$\begin{aligned} \sigma _3=e(SK_{S,1},PK_{V,3})e(\sigma _2,B)^{zhx_Sx_V} \end{aligned}$$

      • If $sta_S=1$, (i.e., $PK_S$ has been replaced with $PK'_{S}=(g_1^{x'_{S}},g_2^{\frac{1}{x'_{S}}},g^{\frac{1}{x'_{S}}})$ and $x_S$ has been replaced with $x'_S$), $\mathcal {B}$ retrieves $x_S$ from $\mathcal {L}$, computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$ and verifies $\sigma$ by checking the following equation:

        $$\begin{aligned} \sigma _3=e(SK_{S,1},PK_{V,3})e(\sigma _2,A)^{\frac{zhx_V}{x_S}}. \end{aligned}$$

    • If $F(S)=0$ mod p, $\mathcal {B}$ aborts the simulation.

Forgery After a polynomially bounded number of queries (if $\mathcal {B}$ does not abort), ${\mathcal {A}_{I}}$ outputs a new valid signature $\sigma ^{*}=(\sigma _1^{*},\sigma _2^{*},\sigma _3^{*})$ on message $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$.

At the end of running Game 1 between ${\mathcal {A}_{I}}$ and $\mathcal {B}$, $\mathcal {B}$ acts as follows:

• If $F({S^{*}})\ne 0$ mod p or $F({V^{*}})=0$ mod p, $\mathcal {B}$ aborts.

• If $F({S^{*}})=0$ mod p and $F({V^{*}})\ne 0$ mod p, (and the simulation does not fail in any steps), $\mathcal {B}$ retrieves $x_{{S^{*}}}$ and $x_{{V^{*}}}$ from $\mathcal {L}$ and computes $h=H(m^{*},ID_{S^{*}},ID_{V^{*}},PK_{S^{*}},PK_{V^{*}},\sigma _1^{*},\sigma _2^{*})$. Then $\mathcal {B}$ calculates and outputs:

  $$\begin{aligned} e(g,g)^{a^5}=\left( \frac{\sigma _3^{*}}{e((\sigma _1^{*})^{J({S^{*}})} (\sigma _2^{*})^{\frac{zh^{*}}{{x_{S^{*}}}}},A^{x_{{V^{*}}}})}\right) ^{\frac{1}{x_{{S^{*}}}^2x_{{V^{*}}}}}, \end{aligned}$$

  as the solution to the $(\mathcal {S}_2,5)$-CBDHE-Set problem instance.

Time Analysis Noting the above descriptions, we can see that $\mathcal {B}$ needs a time $t'\le t+order(((q_{d}+q_{sk}+q_s+q_v)n_u)T_M+(q_{pk}+q_{d}+q_{sk}+q_s+q_v)T_E+(q_r+q_s+q_v)T_P)$, for running the game.

Probability Analysis Here, we evaluate the success probability of $\mathcal {B}$ for solving the $(\mathcal {S}_2,5)$-CBDHE-Set problem instance, i.e., $\varepsilon '$. $\mathcal {B}$ can complete the simulation without aborting if all of the following independent events happen:

• $\mathbf E _1$: $F(U)\ne 0$ mod p for all queries from $\mathcal {O}_{d}$ and $\mathcal {O}_{SK}$.

• $\mathbf E _2$: Let $\text {E}_{2,1}$, $\text {E}_{2,2}$, and $\text {E}_{2,3}$ be the events of $F(S)=0$ mod p, $F(V)\ne 0$ mod p, and $sta_V=0$, respectively, for all queries from $\mathcal {O}_{S}$ and $\mathcal {O}_{V}$. Define $\text {E}_2=\overline{\text {E}_{2,1}\bigcap \text {E}_{2,2}\bigcap \text {E}_{2,3}}$.

• $\mathbf E _3$: $F({S^{*}})=0$ mod p and $F({V^{*}})\ne 0$ mod p.

Note that $\text {Pr}[\text {E}_{2,3}]= \frac{1}{2}$. Moreover, it is easy to see that [24]

$$\begin{aligned} \text {Pr}[F(U)=0 \,\, \text {mod} \,\, p]= \frac{1}{l(n_u+1)}. \end{aligned}$$

So we have

$$\begin{aligned} \text {Pr}[\text {E}_1]&=\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_d+q_{sk}},\\ \text {Pr}[\text {E}_2]&=\left( 1-\frac{1}{2}.\left( 1-\frac{1}{l(n_u+1)}\right) . \frac{1}{l(n_u+1)}\right) ^{q_s+q_{v}}\\&\ge \left( 1-\frac{1}{l(n_u+1)}\right) ^{q_s+q_{v}},\\ \text {Pr}[\text {E}_3]&=\left( 1-\frac{1}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)}. \end{aligned}$$

Hence,

$$\begin{aligned} \text {Pr}[\overline{abort}]&\ge \text {Pr}[\text {E}_{1}\bigcap \text {E}_{2}\bigcap \text {E}_{3}]=\text {Pr}[\text {E}_1].\text {Pr}[\text {E}_2].\text {Pr}[\text {E}_3]\nonumber \\&\ge \left( 1-\frac{1}{l(n_u+1)}\right) ^{q_d+q_{sk}}.\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_s+q_{v}}\nonumber \\&\quad .\left( 1-\frac{1}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)} \nonumber \\&=\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_d+q_{sk}+q_s+q_{v}+1}.\frac{1}{l(n_u+1)}\nonumber \\&\ge \left( 1-\frac{q_d+q_ {sk}+q_s+q_{v}+1}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)}\nonumber \\&\ge \left( 1-\frac{q_d+q_{sk}+q_s+q_{v}+1}{l}\right) .\frac{1}{l(n_u+1)}\nonumber \\&=\frac{1}{4(q_{d}+q_{sk}+q_s+q_v+1)(n_u+1)}, \end{aligned}$$

(2)

where the rightmost equality is implied from $l=2(q_{d}+q_{sk}+q_s+q_v+1)$.

Noting Eq. (2) and that $\varepsilon$ is the success probability of $\mathcal {A}_I$ in Game 1, we have

$$\begin{aligned} \varepsilon '\ge \varepsilon .\text {Pr}[\overline{abort}]\ge \frac{\varepsilon }{4(q_{d}+q_{sk}+q_s+q_v+1)(n_u+1)}. \end{aligned}$$

As the final result, if $\mathcal {A}_I$ can win Game 1 with a non-negligible probability $\varepsilon$, then $\mathcal {B}$ can solve an instance of the $(\mathcal {S}_2,5)$-CBDHE-Set problem with a non-negligible probability $\varepsilon '$ and this is a contradiction of the $(\mathcal {S}_2,5)$-CBDHE-Set assumption in complexity theory. $\square$

Theorem 2

The proposed scheme is $(\varepsilon ,t,q_{sk},q_{pk},q_s,q_v)$-unforgeable against ${\mathcal {A}_{II}}$, if the $(\varepsilon ',t')$-$(\mathcal {S}_4,9)$-CBDHE-Set assumption holds in $(G_1,G_2)$, where

$$\begin{aligned}&\varepsilon ' \ge \frac{\varepsilon }{4(q_{sk}+q_s+q_v+1)(n_u+1)},\\&t'\le t+order(((q_{sk}+q_s+q_v)n_u)T_M\\&\quad +(q_{pk}+q_{sk}+q_s+q_v)T_E+(q_s+q_v)T_P), \end{aligned}$$

Proof

Suppose that there exists a $(\varepsilon ,t,q_{sk},q_{pk},q_s,q_v)$-type II adversary $\mathcal {A}_{II}$, who can break the EUF-CM&IDA in the proposed scheme according to Game 2 and forge a DVS $\sigma ^{*}$ on message $m^{*}$ with respect to $ID_{S^{*}}$ and $ID_{V^{*}}$. By this assumption, we can construct a simulator $\mathcal {B}$ that can use $\mathcal {A}_{II}$ as a subroutine and solve an instance of a $(\mathcal {S}_4,9)$-CBDHE-Set problem with a probability at least $\varepsilon '$ and in time at most $t'$, which contradicts the $(\varepsilon ',t')$-$(\mathcal {S}_4,9)$-CBDHE-Set assumption in $(G_1,G_2)$.

Consider two multiplicative cyclic groups $G_1$ and $G_2$ of a large prime order p and a random generator $g=C=f^{a^2}$ of $G_1$. Let $e:G_1\times G_1\longrightarrow G_2$. Suppose that $\mathcal {B}$ is given a random $(\mathcal {S}_4,9)$-CBDHE-Set challenge $(A=f\in G_1,B=f^a\in G_1,C=f^{a^2}\in G_1,D=f^{a^3}\in G_1,E=f^{a^4}\in G_1)$ and is requested to output $e(f,f)^{a^9}\in G_2$. In order to use ${\mathcal {A}_{II}}$ as a subroutine, $\mathcal {B}$ must simulate the challenger $\mathcal {C}$ and answer all $\mathcal {A}_{II}$’s queries from $\mathcal {O}_{II}=\{\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{S},\mathcal {O}_{V}\}$. In order to respond these queries consistently, $\mathcal {B}$ generates a list $\mathcal {L}=\{(ID_U,x_{U},PK_{U},SK_{U})\}$ which is initially empty. Then $\mathcal {B}$ plays Game 2 with $\mathcal {A}_{II}$ as follows:

Setup Let $l=2(q_{sk}+q_s+q_v+1)$ and assume that $l(n_u+1)<p$. $\mathcal {B}$ selects a random $s\in \mathbb {Z}_p^{*}$ and sets $g_1=g^{s}=C^{s}$. Then $\mathcal {B}$ selects the values $k\in _R\{0,1,\ldots ,n_u\}$, $x',x_1,\ldots ,x_{n_u} \in _R \mathbb {Z}_{l}$, $y',y_1,\ldots ,y_{n_u} \in _R \mathbb {Z}_p$, and $z \in _R \mathbb {Z}_p^{*}$, and assigns:

$$\begin{aligned}&g=C=f^{a^2}, \quad \quad \quad \quad g_1=g^{s}=C^{s},\quad \quad \quad \quad g_2=g^{z}\\&u'=B^{-kl+x'}C^{y'}, \quad \quad \,\, u_i=B^{x_i}C^{y_i}\quad (\text {for} \quad i=1,2,\ldots ,n_u). \end{aligned}$$

$\mathcal {B}$ also computes $T=e(g_1,g_2)$ and $T'=e(g_1,g)$, then selects two collision-resistant hash functions $H_u:\{0,1\}^{*}\longrightarrow \{0,1\}^{n_u}$ and $H:\{0,1\}^{*}\times G_1^{8}\longrightarrow \mathbb {Z}_p^{*}$ and gives $params=\{G_1,G_2,p,e,g,g_1,g_2,u',\overrightarrow{u},T,T',H_u,H\}$ to $\mathcal {A}_{II}$. $\mathcal {B}$ also computes two functions F(U) and J(U) similar to those in the proof of Theorem 1 and sends them to $\mathcal {A}_{II}$. By these assignments, we have

$$\begin{aligned} u'\prod _{i\in \mathcal {U}_{U}}u_i=B^{F(U)}g^{J(U)}. \end{aligned}$$

Note that by the mentioned settings in this step, all distributions are identical to those in the real world from the perspective of $\mathcal {A}_{II}$. Also, remember that in Game 2 (in contrast to Game 1), $\mathcal {B}$ knows the master secret key, $msk=g^{s^2}$ and must simulate $\mathcal {C}$ and answer all ${\mathcal {A}_{II}}$’s queries by this fact.

Queries In this step, $\mathcal {A}_{II}$ has access to the oracles in set $\mathcal {O}_{II}=\{\mathcal {O}_{PK},\mathcal {O}_{SK},\mathcal {O}_{S},\mathcal {O}_{V}\}$. $\mathcal {B}$ responds to ${\mathcal {A}_{II}}$’ s queries by simulating these oracles as follows:

$\mathcal {O}_{PK}$. As $\mathcal {A}_{II}$ sends a public key query for an identity $ID_U$ to $\mathcal {O}_{PK}$, $\mathcal {B}$ checks whether such key exists in $\mathcal {L}$. If so, $\mathcal {B}$ returns this public key to $\mathcal {A}_{II}$. Otherwise, $\mathcal {B}$ picks a random $x_{U}\in _R \mathbb {Z}_p^{*}$ and acts as follows:

• If $F(U)=0$ mod p, $\mathcal {B}$ sets $PK_{U}=(E^{sx_{U}},A^{\frac{z}{x_{U}}},A^{\frac{1}{x_{U}}})$. Note that by this assignment, the real secret value of $ID_U$ is $a^2x_U$, which is known to $\mathcal {B}$.

• If $F(U)\ne 0$ mod p, $\mathcal {B}$ sets $PK_{U}=(B^{\frac{s}{x_{U}}},D^{zx_U},D^{x_U})$. Note that by this assignment, the real secret value of $ID_U$ is $\frac{1}{ax_{U}}$, which is unknown to $\mathcal {B}$.

Then $\mathcal {B}$ sends $PK_U$ to $\mathcal {A}_{II}$. Furthermore, $\mathcal {B}$ adds $PK_{U}$ and its corresponding $x_{U}$ in $\mathcal {L}$.

$\mathcal {O}_{SK}$. As $\mathcal {A}_{II}$ sends a private key query for an identity $ID_U$ to $\mathcal {O}_{SK}$, $\mathcal {B}$ checks whether such key exists in $\mathcal {L}$. If so, $\mathcal {B}$ returns this private key to $\mathcal {A}_{II}$. Otherwise $\mathcal {B}$ acts as follows:

• If $F(U)=0$ mod p, $\mathcal {B}$ aborts the simulation.

• If $F(U)\ne 0$ mod p, $\mathcal {B}$ checks whether $(x_{U},Pk_{U})$ exists in $\mathcal {L}$. If so, $\mathcal {B}$ picks it, otherwise $\mathcal {B}$ produces $(x_{U},Pk_{U})$ by simulating $\mathcal {O}_{PK}$ (Note that in as $F(U)\ne 0$ mod p, the real secret value of $ID_U$ is $\frac{1}{ax_{U}}$). Then $\mathcal {B}$ selects a random $r''_U\in _R \mathbb {Z}_p^{*}$ and assigns the private key as:

  $$\begin{aligned} SK_{U}&=\left( B^{-\frac{J(U)}{F(U)}\left( \frac{s^2}{x_U^2}\right) }\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{r''_U},B^{-\frac{s^2}{x_U^2F(U)}}g^{r''_U}\right) \\&=\left( g^{s^2\left( \frac{1}{ax_{U}}\right) ^2}\left( u'\prod _{i\in \mathcal {U}_{U}}u_i\right) ^{\tilde{r}''_U},g^{\tilde{r}''_U}\right) \\&=(SK_{U,1},SK_{U,2}), \end{aligned}$$

  where $\tilde{r}''_U=r''_U-\frac{s^2}{ax_U^2F(U)}$. Then $\mathcal {B}$ returns $SK_U$ to $\mathcal {A}_{II}$ and also adds it in $\mathcal {L}$.

$\mathcal {O}_{S}$. As $\mathcal {A}_{II}$ sends a signing query for $(m,ID_S,ID_V)$, $\mathcal {B}$ searches $\mathcal {L}$ to find $SK_S$. If this entry exists, $\mathcal {B}$ picks it and creates a DVS $\sigma$ on message m by running the DSign algorithm and sends it to $\mathcal {A}_{II}$. Otherwise, $\mathcal {B}$ acts as follows:

• If $F(S)=0$ mod p, $\mathcal {B}$ aborts the simulation.

• If $F(S)\ne 0$ mod p, $\mathcal {B}$ obtains $SK_S$ by simulating $\mathcal {O}_{SK}$, then creates a DVS $\sigma$ on message m by running the DSign algorithm and sends it to $\mathcal {A}_{II}$.

$\mathcal {O}_{V}$. As $\mathcal {A}_{II}$ sends a verification query for $(\sigma =(\sigma _1,\sigma _2,\sigma _3),ID_S,ID_V)$, $\mathcal {B}$ acts as follows:

• If $F(S)=0$ mod p, $\mathcal {B}$ aborts the simulation.

• If $F(S)\ne 0$ mod p (and so $PK_{S}=(B^{\frac{s}{x_{S}}},D^{zx_S},D^{x_S})$, $\mathcal {B}$ obtains $SK_S$ by simulating $\mathcal {O}_{SK}$. Then $\mathcal {B}$ computes $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$, retrieves $x_S$ from $\mathcal {L}$, and acts as follows:

  • If $F(V)=0$ mod p, i.e., $PK_{V}=(E^{sx_{V}},A^{\frac{z}{x_{V}}},A^{\frac{1}{x_{V}}})$, $\mathcal {B}$ retrieves $x_V$ from $\mathcal {L}$ and verifies $\sigma$ by checking the following equation:

    $$\begin{aligned} \sigma _3=e(SK_{S,1},PK_{V,3})e(\sigma _2,B)^{\frac{zhx_S}{x_V}}. \end{aligned}$$

  • If $F(V)\ne 0$ mod p, i.e., $PK_{V}=(B^{\frac{s}{x_{V}}},D^{zx_V},D^{x_V})$, $\mathcal {B}$$\mathcal {B}$ retrieves $x_V$ from $\mathcal {L}$ and verifies $\sigma$ by checking the following equation:

    $$\begin{aligned} \sigma _3=e(SK_{S,1},PK_{V,3})e(\sigma _2,E)^{zhx_Sx_V}. \end{aligned}$$

Forgery After a polynomially bounded number of queries (if $\mathcal {B}$ does not abort), ${\mathcal {A}_{II}}$ outputs a new valid DVS $\sigma ^{*}=(\sigma _1^{*},\sigma _2^{*},\sigma _3^{*})$ on message $m^{*}$ for $ID_{S^{*}}$ and $ID_{V^{*}}$.

At the end of running Game 2 between ${\mathcal {A}_{II}}$ and $\mathcal {B}$, $\mathcal {B}$ acts as follows:

• If $F({S^{*}})\ne 0$ mod p or $F({V^{*}})=0$ mod p, $\mathcal {B}$ aborts.

• If $F({S^{*}})=0$ mod p and $F({V^{*}})\ne 0$ mod p, (and the simulation does not fail in any steps), $\mathcal {B}$ retrieves $x_{{S^{*}}}$ and $x_{{V^{*}}}$ from $\mathcal {L}$ and computes $h=H(m^{*},ID_{S^{*}},ID_{V^{*}},PK_{S^{*}},PK_{V^{*}},\sigma _1^{*},\sigma _2^{*})$. Then $\mathcal {B}$ calculates and outputs:

  $$\begin{aligned} e(f,f)^{a^9}=\left( \frac{\sigma _3^{*}}{e((\sigma _1^{*})^{J({S^{*}})}, D^{x_{{V^{*}}}})e(\sigma _2^{*},B^{\frac{zh^{*}x_{V^{*}}}{{x_{S^{*}}}}})}\right) ^{\frac{1}{s^2x_{{S^{*}}}^2x_{{V^{*}}}}}, \end{aligned}$$

  as the solution to the $(\mathcal {S}_4,9)$-CBDHE-Set problem instance.

Time Analysis Noting the above descriptions, we can see that $\mathcal {B}$ needs a time $t'\le t+order(((q_{sk}+q_s+q_v)n_u)T_M+(q_{pk}+q_{sk}+q_s+q_v)T_E+(q_s+q_v)T_P)$, for running the game.

Probability Analysis Here, we evaluate the success probability of $\mathcal {B}$ for solving the $(\mathcal {S}_4,9)$-CBDHE-Set problem instance, i.e., $\varepsilon '$. $\mathcal {B}$ can complete the simulation without aborting if all of the following independent events happen:

• $\mathbf E _1$: $F(U)\ne 0$ mod p for all queries from $\mathcal {O}_{SK}$.

• $\mathbf E _2$: $F(S)\ne 0$ mod p for all queries from $\mathcal {O}_{S}$ and $\mathcal {O}_{V}$.

• $\mathbf E _3$: $F({S^{*}})=0$ mod p and $F({V^{*}})\ne 0$ mod p.

Noting $\text {Pr}[F(U)=0 \,\, \text {mod} \,\, p]= \frac{1}{l(n_u+1)}$ [24], we have

$$\begin{aligned} \text {Pr}[\text {E}_1]&=\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_{sk}},\\ \text {Pr}[\text {E}_2]&=\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_s+q_{v}},\\ \text {Pr}[\text {E}_3]&=\left( 1-\frac{1}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)}. \end{aligned}$$

Hence,

$$\begin{aligned} \text {Pr}[\overline{abort}]&\ge \text {Pr}[\text {E}_{1}\bigcap \text {E}_{2}\bigcap \text {E}_{3}]=\text {Pr}[\text {E}_1].\text {Pr}[\text {E}_2].\text {Pr}[\text {E}_3] \nonumber \\&\ge \left( 1-\frac{1}{l(n_u+1)}\right) ^{q_{sk}}.\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_s+q_{v}} \nonumber \\&\quad .\left( 1-\frac{1}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)} \nonumber \\&=\left( 1-\frac{1}{l(n_u+1)}\right) ^{q_{sk}+q_s+q_{v}+1}.\frac{1}{l(n_u+1)} \nonumber \\&\ge \left( 1-\frac{{q_{sk}+q_s+q_{v}+1}}{l(n_u+1)}\right) .\frac{1}{l(n_u+1)} \nonumber \\&\ge \left( 1-\frac{{q_{sk}+q_s+q_{v}+1}}{l}\right) .\frac{1}{l(n_u+1)} \nonumber \\&= \frac{1}{4(q_{sk}+q_s+q_v+1)(n_u+1)} \end{aligned}$$

(3)

where the rightmost equality is implied from $l=2(q_{sk}+q_s+q_v+1)$.

Noting Eq. (3) and that $\varepsilon$ is the success probability of $\mathcal {A}_{II}$ in Game 2, we have:

$$\begin{aligned} \varepsilon '\ge \varepsilon .\text {Pr}[\overline{abort}]\ge \frac{\varepsilon }{4(q_{sk}+q_s+q_v+1)(n_u+1)}. \end{aligned}$$

As the final result, if $\mathcal {A}_{II}$ can win Game 2 with a non-negligible probability $\varepsilon$, then $\mathcal {B}$ can solve an instance of the $(\mathcal {S}_4,9)$-CBDHE-Set problem with a non-negligible probability $\varepsilon '$ and this is a contradiction of the $(\mathcal {S}_4,9)$-CBDHE-Set assumption in complexity theory. $\square$

Theorem 3

The proposed scheme is EUF-CM&IDA (according to Definition 1) in the standard model under the $(\mathcal {S}_4,9)$-CBDHE-Set assumption.

Proof

The proof is directly implied from Theorems 1 and 2. $\square$

7.3 Non-transferability

Theorem 4

The proposed CL-DVS scheme is unconditionally non-transferable.

Proof

Suppose that $\sigma$ is a DVS on message m with respect to $ID_S$ and $ID_V$ which is created by the original signer (by the DSign algorithm) and $\sigma '$ is a DVS on m with respect to $ID_S$ and $ID_V$ which is produced by the designated verifier (by the TS algorithm).

In order to generate $\sigma$, the signer, with the private key $SK_S$, selects a random value $r_0\in _R \mathbb {Z}_p^{*}$ and sets:

$$\begin{aligned} (\sigma _1,\sigma _2,\sigma _3)=(SK_{S,2},g^{r_0},e(SK_{S,1}PK_{S,2}^{hr_0},PK_{V,3})), \end{aligned}$$

where $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$.

In order to generate $\sigma '$, the designated verifier, with the secret value $x_V$, picks a random value $r_1\in _R \mathbb {Z}_p^{*}$ and sets:

$$\begin{aligned}&(\sigma '_1,\sigma '_2,\sigma '_3)=\left( SK_{S,2},g^{r_1},(e(PK_{S,1},PK_{S,1})\right. \\&\quad \left. .e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,\sigma '_1\right) . e(PK_{S,2}^{h'},\sigma '_2))^{\frac{1}{x_V}}\right) , \end{aligned}$$

where $h'=H(m,ID_S,ID_V,PK_S,PK_V,\sigma '_1,\sigma '_2)$.

It is easy to see that $\sigma$ and $\sigma '$ have the same distributions and hence they are indistinguishable. Suppose that a challenger $\mathcal {C}$ selects a random value $r^{*} \in _R \mathbb {Z}_p^{*}$, picks a bit $b\in _R \{0,1\}$ by flipping a fair coin and creates a signature $\sigma ^{*}=(\sigma ^{*}_1,\sigma ^{*}_2,\sigma ^{*}_3)$ as follows:

• If $b=0$, $\mathcal {C}$ sets:

  $$\begin{aligned} (\sigma ^{*}_1,\sigma ^{*}_2,\sigma ^{*}_3)=(SK_{S,2},g^{r^{*}}, e(SK_{S,1}PK_{S,2}^{h^{*}r^{*}},PK_{V,3})), \end{aligned}$$

• If $b=1$, $\mathcal {C}$ sets:

  $$\begin{aligned}&(\sigma ^{*}_1,\sigma ^{*}_2,\sigma ^{*}_3)=\left( SK_{S,2},g^{r^{*}}, (e(PK_{S,1},PK_{S,1})\right. \\&\quad \left. .e\left( u'\prod _{i\in \mathcal {U}_{S}}u_i,\sigma ^{*}_1\right) . e\left( PK_{S,2}^{h^{*}},\sigma ^{*}_2)\right) ^{\frac{1}{x_V}}\right) , \end{aligned}$$

where $h^{*}=H(m,ID_S,ID_V,PK_S,PK_V,\sigma ^{*}_1,\sigma ^{*}_2)$. We have

$$\begin{aligned}&\text {Pr}[\sigma ^{*}=\sigma ]=\text {Pr}[r^{*}=r_0]=\frac{1}{p-1},\\&\text {Pr}[\sigma ^{*}=\sigma ']=\text {Pr}[r^{*}=r_1]=\frac{1}{p-1}. \end{aligned}$$

Therefore, the distributions of $\sigma$ and $\sigma '$ are identical and a distinguisher $\mathcal {D}$ cannot distinguish whether the signature is created by the signer or the designated verifier. Hence, the signature is unconditionally non-transferable. $\square$

Remark 4

As mentioned in Remark 3, our proposal is not placed in the category of non-delegatable CL-DVS schemes, since the signer can delegate his/her signing rights to every third party by providing $Comm.Key=e(SK_{S,1},PK_{V,3})$ to him/her. Note that everyone who knows $Comm.Key=e(SK_{S,1},PK_{V,3})$ can produce a valid DVS by selecting a random value $r\in _R \mathbb {Z}_p^{*}$ and setting:

$$\begin{aligned}&(\sigma _1,\sigma _2,\sigma _3)\\&\quad =(SK_{S,2},g^{r},e(SK_{S,1},PK_{V,3})e (PK_{S,2}^{hr},PK_{V,3})), \end{aligned}$$

where $h=H(m,ID_S,ID_V,PK_S,PK_V,\sigma _1,\sigma _2)$. Note that $SK_{S,2}$ can be easily obtained from the previously signed messages from S to V.

Table 3 Comparisons between CL-DVS schemes

8 Comparison

To the best of our knowledge, only nine CL-DVS schemes have been proposed in the literature to date [9,10,11,12,13,14,15,16,17]. In Table 3, a comparison among the existing CL-DVS schemes with our proposal is provided. As mentioned in Sect. 4, among all CL-DVS schemes in [9,10,11,12,13,14,15,16,17], there are issues in their security proofs, as outlined below:

• In the proof of the scheme in [9], EUF-CM&IDA (which is well known in CL-PKC) is not considered. Furthermore, the scheme is vulnerable against $\mathcal {A}_{II}$ according to the proposed attack in [19].

• In the proof of the scheme in [10], EUF-CM&IDA is not considered.

• In the proof of the scheme in [11], oracles are not simulated, even EUF-CMA is not considered. Moreover, probability analysis is not provided.

• In the proof of the schemes in [12, 13], probability analysis is not provided.

• In the proof of the scheme in [14], probability analysis is not provided. Moreover, the scheme is vulnerable against $\mathcal {A}_{II}$ and key-compromise attack according to the proposed attacks in [20, 21].

• In the proof of the scheme in [15], the oracle $\mathcal {O}_V$ is not simulated.

• In the proof of the scheme in [16], probability analysis is not provided. Moreover, the scheme is vulnerable against $\mathcal {A}_{I}$ according to the proposed attack in [18].

• In the proof of the scheme in [17], the unreasonable condition C3 makes the proof unreliable (See Sect. 4.2.1).

As a result, our scheme is not only the first scheme with reliable security proofs, but also the only scheme in the standard model. We should note that the computational cost of our proposal increases due to the need to provide additional security properties in the standard model. Nevertheless, we also note that most of these computations can be computed off-line (i.e., can be pre-computed before running the DSign and DVer algorithms), as shown in Table 3.

9 Conclusion

In this paper, we provided a discussion on the proposed certificateless designated verifier signature (CL-DVS) schemes and showed that the security proofs of none of them are reliable. Furthermore, we concentrate on the recently proposed CL-SDVS scheme (IEEE Access 2018) and showed that this scheme is delegatable in contrast to its author’s claim. Moreover, we showed a drawback in the security proof of this scheme which makes it unreliable. Finally, we proposed the first CL-DVS scheme in the standard model with reliable security proofs. We proved the unforgeability of our scheme against the key replacement attacker ($\mathcal {A}_{I}$) and the malicious KGC attacker ($\mathcal {A}_{II}$) based on $(\mathcal {S}_2,5)$-CBDHE-Set and $(\mathcal {S}_4,9)$-CBDHE-Set assumptions, respectively. The security proof of our proposal does not suffer from the drawbacks in the proofs of existing CL-DVS schemes.