1 Introduction
Identity-based Cryptography (IBC). In 1984, Shamir (1984) proposed the concept of identity-based PKC (IBC) for reducing the requirements on the public key infrastructure. In IBC, the public key for one entity is its well-known identity information, such as the email address and the full name. The private key for this entity is generated by one trusted party called Private Key Generater (PKG), usually being the signature on the identity information. With this approach, the certification of public keys becomes implicit. However, IBC suffers from the main drawback of being inherently key escrowed, since PKG can generate the private key of any entity.
Certificate-based Cryptography (CBC). Motivated by avoiding the problem of third party queries in PKC, Gentry proposed the new concept of certificate-based encryption (CBE) by combining public key encryption and identity based encryption. Following the idea of CBE, Kang et al. (2004) proposed the concept of certificate based-signature (CBS). This certificate has all of the functionality of a conventional PKI certificate – e.g. it can be used explicitly as proof of current certification – but it can also be used as part of the user decryption/signing key, which is composed of the user-generated private key and the certificate. As a result, CBC achieves two main advantages. On the one hand, unlike IBC, there is no key escrow for CBC, since CA does not know the user-generated private key. On the other hand, the encrypter (or signature verifier) does not need to verify the certificate, because the ciphertext (or signature) can not be decrypted (or generated) unless the certificate exists. This allows CBC to eliminate third party queries on certificate status (Gentry, 2003). By refining basic CBE/CBS through the use of subset covers, an exceptionally efficient PKI can be constructed (Gentry, 2003).
Certificateless cryptography (CLC). Similarly motivated by combining merits of the traditional PKC and IBC, independently from the work of CBC, the concept of certificateless encryption (CLE) and certificateless signature (CLS) were introduced by Al-Riyami and Paterson (2003). In CLC, each entity has two secrets: a secret value $\mathit{SV}$ chosen by the entity and a partial private key $\mathit{PPK}$ generated by a third party called Private Key Generater (PKG). The full private key is the output of a function by taking $\mathit{SV}$ and $\mathit{PPK}$ as the input, and hence can be only known by the user. On the one hand, unlike IBC, CLC does not suffer from key escrow, since PKG does not have access to the user’s secret value $\mathit{SV}$. CLC does not require the use of certificates to guarantee the authenticity of public key. The two concepts of CBC and CLC are similar. The main difference is the generation of the partial secret key in CLC (it is called certificate in CBC). In CLC the PKG does not require the user’s public key for the generation of the partial secret key, while in CBC the CA does require the user’s public key for the generation of the certificate. Additionally, the trust level of CBC is 3, while the trust level of CLC is 2 (Liu et al., 2007). All the above three kinds of public key cryptographic primitives have the considerable advantages in key managements which make them potentially suitable for many applications such as wireless networks (Guo et al., 2014; Xie and Wang, 2014; Shen et al., 2015) where key management will be additional burden for restricted resources.
1.1 Related Works
Although CBC and CLC were developed independently, both of them can be conceptually seen as intermediates between traditional PKC and IBC, seeking to simplify the management of certificates while avoiding the key escrow problem in IBC. So a natural question to establish the connection of two concepts arose in the theoretical cryptography field. In 2005, Al-Riyami and Paterson (2005) presented one generic conversion from CLE to CBE and claimed the provable security of this generic construction of CBE. Shortly later, Kang and Park (2005) pointed out that this generic conversion from CLE to CBE has a critical flaw in the security proof. Recently, Wu et al. (2009) proposed a new generic conversion from CLS to CBS, and a generic conversion from CLE to CBE (Wu et al., 2012). These two generic conversions have to depend on the cryptographic hash function which is taken as a random oracle (Canetti et al., 2004) in the security proof. In addition to the generic results of CBS, there are also some concrete CBS schemes proposed in Kang et al. (2004), Liu et al. (2008, 2011), Wu et al. (2009, 2012), Li et al. (2010, 2012). In current research of cryptography, there are much more results for certificateless cryptography than certificate-based cryptography.
1.2 Motivations
From the perspective of theoretical cryptography, it is very interesting to investigate the general relationship between certificate-based signatures and certificateless signatures. As mentioned in Wu et al. (2012), those two cryptographic primitives are quite closely related. In fact, four similarities in certificateless signatures and certificate-based signatures are presented in Wu et al. (2012). However, the state-of-the-art result in Wu et al. (2012) is not satisfactory enough in the viewpoint of theory, since the undesirable primitive “random oracle” (Bellare and Rogaway, 1993) is needed in this framework:
In the field of provable secure cryptography, researchers usually try to construct cryptographic schemes in the standard model instead of the random oracle model. In contrast, it is a natural and intuitive task in theory to wipe out “Random Oracle”, or to get the most concise framework:
From the perspective of cryptographic practice, it is also worthwhile to study this most concise framework. In fact, there are much more research works on CLS schemes than those in CBS schemes. Hence, the study on generic construction of CBS from CLS can help us to obtain many concrete CBS schemes from existing CLS schemes with almost no price. Among those constructed in this way, some CBS schemes may have better properties than existing ones.
1.3 Contributions
A new security model for CLS is developed. It captures some new attacks which have never been mentioned in literature. For more details, please refer to Section 2 where two remarks aim to explain its originality. From the viewpoint of basic theory, this further development of security model is an essential refinement for certificateless cryptography theory. From the viewpoint of applications, it is the key technique helping us to prove secure our generic conversion of CBS schemes from CLS schemes.
The most intuitive generic conversion of CLS schemes from CBS schemes is “revived”. Compared with the Wu et al.’s (2009) generic conversion from CLS to CBS, our generic conversion is as intuitive as possible, and as concise as possible. Although it is so intuitive, concise and reasonable, this conversion framework can not be adopted by previous works in cryptography, until the formal security proof is completed in this paper. In terms of cryptographic theory, we provide the formal security proof for the intuitive observation on close relation between CLS signatures and CBS signatures.
Many concrete CBS schemes can be constructed from existing CLS schemes by applying the generic framework. One existing CLS scheme is proved secure in our new security model. With this proof as an example, we also listed other CLS schemes which also can be proved secure in the new security model. Hence, many CBS signature schemes can be constructed.
1.4 Organization
This paper is organized as follows. Section 2 reviews the syntax definition of CLS and proposes the new security model for CLS. Section 3 briefly reviews the definition and security model for CBS in one more concise framework. Section 4 presents our new generic construction of CBS from CLS and its security proof. Section 5 compares our result with the state-of-the-art one proposed in Wu et al. (2012). Section 6 presents a concrete CBS signature scheme as an application example of our generic conversion. Some other CLS schemes which can be similarly proved secure are listed. At last, Section 7 draws the conclusion.
2 Certificateless Signature
We use the notation $\mathsf{ID}$ and $\mathit{ID}$ to denote the identity information in the certificateless system and certificate-based system respectively. We put the prefix $\mathit{CL}.$ to specify that this is in the certificateless system and $\mathit{CB}$ to specify that this is in the certificate-based system. We use the notation
to denote that the query $\mathit{query}$ has never been submitted to the oracle O, and the notation
to denote that the answer $\mathit{answer}$ has been returned by the oracle O.
Definition 1.
A certificateless signature scheme consists of the following six algorithms.
-
(1) CL.Setup(${1^{k}})\to (\mathit{CL}.\mathit{msk},\mathit{CL}.\mathit{param})$. It takes ${1^{k}}$ as input where k is the security parameter, and returns the master private key $\mathit{CL}.\mathit{msk}$ and the parameter $\mathit{CL}.\mathit{param}$ which is shared in the system.
-
(2) CL.ExtractPPK$(\mathit{CL}.\mathit{msk},\mathit{CL}.\mathit{param},\mathsf{ID})\to {D_{\mathsf{ID}}}$. It takes the master private key $\mathit{CL}.\mathit{msk}$, the system parameter $\mathit{CL}.\mathit{param}$ and the identity $\mathsf{ID}$ as input, and returns the partial private key ${D_{\mathsf{ID}}}$.
-
(3) CL.SetSV$(\mathit{CL}.\mathit{param})\to {X_{\mathsf{ID}}}$. It takes as input the system parameter $\mathit{CL}.\mathit{param}$, and outputs a secret value ${X_{\mathsf{ID}}}$.
-
(4) CL.SetPK($\mathit{CL}.\mathit{param},{X_{\mathsf{ID}}})\to ({\mathit{CL}.\mathit{PK}_{\mathsf{ID}}})$. It takes as input the system parameter $\mathit{CL}.\mathit{param}$, and this identity’s secret value ${X_{\mathsf{ID}}}$, and outputs the public key ${\mathit{CL}.\mathit{PK}_{\mathsf{ID}}}$.
-
(5) CL.Sign$(\mathit{CL}.\mathit{param},{D_{\mathsf{ID}}},{X_{\mathsf{ID}}},m)\to \mathit{CL}.\sigma $. It takes as input the system parameter $\mathit{CL}.\mathit{param}$, the partial private key ${D_{\mathsf{ID}}}$, the secret value ${X_{\mathsf{ID}}}$ and the message m, and outputs the signature $\mathit{CL}.\sigma $.
-
(6) CL.Verify$(\mathit{CL}.\mathit{param},\mathsf{ID},{\mathit{CL}.\mathit{PK}_{\mathsf{ID}}},m,\mathit{CL}.\sigma )\to b\in \{0,1\}$. It takes as input the system parameter $\mathit{CL}.\mathit{param}$, an identity $\mathsf{ID}$, this identity’s public key ${\mathit{CL}.\mathit{PK}_{\mathsf{ID}}}$ and a message/signature pair $(m,\mathit{CL}.\sigma )$, and outputs 1 if the signature is correct, or 0 otherwise.
The following definition has some essentially different points from other ones including that in Huang et al. (2011). Two remarks on these basic differences will be presented during the definition. To get more succinct security definition than others, we put four kinds of adversary models together in one unified framework. Additionally, in Section 6, we will show that many existing CLS signature schemes can be proved secure in our new security model and present 6 examples.
Definition 2.
A CLS scheme is CL-EUF-CMCI secure against a certain kind of adversary
\[ \mathcal{A}\in \big\{\text{CL.Normal-}{\mathcal{A}^{I}},\text{CL.Super-}{\mathcal{A}^{I}},\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}\big\},\]
if no polynomially bounded adversary $\mathcal{A}$ has a non-negligible success probability in the following CLS game. In the following,
will be called normal Type I adversary, super Type I adversary, normal Type II adversary, and super Type II adversary respectively.(1) Initial: the challenger runs the algorithm CL.Setup, returns $\mathit{CL}.\mathit{Params}$ and the auxiliary information $\mathit{aux}\in \{\mathit{nil},\mathit{CL}.\mathit{msk}\}$ to the attacker $\mathcal{A}$ ($\mathit{nil}$ means nothing), where
\[\begin{array}{l@{\hskip4.0pt}l}\mathit{aux}=\mathit{nil},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CL.Normal-}{\mathcal{A}^{I}},\text{CL.Super-}{\mathcal{A}^{I}}\big\},\\ {} \mathit{aux}=\mathit{CL}.\mathit{msk},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}\big\}.\end{array}\]
(2) Queries: in this phase, $\mathcal{A}$ can adaptively make requests to a few oracles among the following ones.
-
(i) ${O^{\mathit{CL}.\mathit{CreateU}}}(\mathsf{ID})\to {\mathit{CL}.\mathit{PK}_{\mathsf{ID}}}$. This oracle receives an input $\mathsf{ID}$ and outputs this original public key of the identity $\mathsf{ID}$.
-
(ii) ${O^{\mathit{CL}.\mathit{ReplacePK}}}(\mathsf{ID},\mathit{CL}.\mathit{PK})\to \varnothing $. For a public key replacement query $(\mathsf{ID},\mathit{CL}.\mathit{PK})$, it sets $\mathit{CL}.\mathit{PK}$ as the current public key.
-
(iii) ${O^{\mathit{CL}.\mathit{SecretV}}}(\mathit{CL}.\mathit{PK})\to X$. If $\mathit{CL}.\mathit{PK}$ is the original public key of a ceratin identity $\mathsf{ID}$ (i.e. $\mathit{CL}.\mathit{PK}$ has been returned from the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$), this oracle returns the secret value X corresponding to $\mathit{CL}.\mathit{PK}$. Otherwise, it refuses this query.
-
(iv) ${O^{\mathit{CL}.\mathit{PartialPK}}}(\mathsf{ID},\mathit{CL}.\mathit{PK})\to {D_{\mathsf{ID}}}$. For a partial private key query $\mathsf{ID}$, this oracle runs the algorithm CL.ExtractPPK and outputs the result ${D_{\mathsf{ID}}}$.
-
(v) ${O^{\mathit{CL}.\mathit{NSign}}}(\mathsf{ID},m)\to \mathit{CL}.\sigma $. If which means that the current public key $\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ has been provided by the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$, it outputs a valid signature $\mathit{CL}.\sigma $ of m under the current public key $\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ of the identity $\mathsf{ID}$. Otherwise, it refuses the query.
Remark 1.
Originally, “normal” is used to mean that one signing query is normal (or reasonable) for the challenger which knows both the current secret value and partial private key for this query. To make one signing oracle query “normal”, all previous definition models require that the current public key be the original one of the current identity. However, this requirement is only sufficient for that the challenger knows the current secret value, but not necessary. In fact, the sufficient and necessary condition for “normal” signing queries should be that the current public key has been generated by the challenger, or formally the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$. For example, the adversary gets Alice’s public key $p{k_{A}}$ and Bob’s public key $p{k_{B}}$ from the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$, then requires Alice’s public key to take the value of $p{k_{B}}$ through the oracle ${O^{\mathit{CL}.\mathit{ReplacePK}}}$, and finally queries the signature corresponding to Alice’s identity and the replaced (not original) public key. In this example, although Alice’s public key has been replaced, the challenger still knows the current secret value and hence this signing query should be called “normal”. In fact, our definition for “normal” captures this example, while previous security models leave it out.
Every attack model $\mathcal{A}$ has its own set ${\mathcal{O}_{\mathcal{A}}}$ of allowed oracles. In particular, with ${\mathcal{O}^{\prime }}=\{{O^{\mathit{CL}.\mathit{CreateUser}}},{O^{\mathit{CL}.\mathit{ReplacePK}}},{O^{\mathit{CL}.\mathit{SecretV}}}\}$ being commonly allowed,
\[\begin{array}{l@{\hskip4.0pt}l}{\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CL}.\mathit{NSign}}},{O^{\mathit{CL}.\mathit{PartialPK}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CL.Normal-}{\mathcal{A}^{I}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CL}.\mathit{SSign}}},{O^{\mathit{CL}.\mathit{PartialPK}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CL.Super-}{\mathcal{A}^{I}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CL}.\mathit{NSign}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CL}.\mathit{SSign}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}.\end{array}\]
(3) Output: After all queries, $\mathcal{A}$ outputs a forgery $({\mathsf{ID}^{\ast }},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }})$. Let $\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}$ be the current public key of ${\mathsf{ID}^{\ast }}$. $\mathcal{A}$ is said to win the game if the forgery satisfies the following restrictions to ensure that the successful forgery is nontrivial. It is well-known that the basic security requirement for CLS is that both the secret value and the partial private key are the two indispensable factors for generating a CLS signature. In other words, any forgery generated by the attacker who knows at most one of these two indispensable factors should be accepted as successful.(i) For $\mathcal{A}\in \{\text{CL.Normal-}{\mathcal{A}^{I}},\text{CL.Super-}{\mathcal{A}^{I}},\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}\}$, it is commonly required that
\[ 1=\mathsf{CL}.\mathsf{Verify}\big(\mathit{CL}.\mathit{mpk},\text{CL.param},{\mathsf{ID}^{\ast }},\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }}\big),\]
and
where
\[\begin{array}{l@{\hskip4.0pt}l}{O^{\mathit{CL}.\mathit{Sign}}}={O^{\mathit{CL}.\mathit{NSign}}},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CL.Normal-}{\mathcal{A}^{I}},\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}}\big\},\\ {} {O^{\mathit{CL}.\mathit{Sign}}}={O^{\mathit{CL}.\mathit{SSign}}},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CL.Super-}{\mathcal{A}^{I}},\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}\big\}.\end{array}\]
Here, we use the notation ↛ to denote that the query $({\mathsf{ID}^{\ast }},{m^{\ast }})$ has never been provided to the oracle ${O^{\mathit{Sign}}}$. This restriction ensures that the signature is valid and not trivially obtained from the signing oracle.(ii) For $\mathcal{A}\in \{\text{CL.Normal-}{\mathcal{A}^{I}},\text{CL.Super-}{\mathcal{A}^{I}}\}$, additionally, it is required that
This restriction ensures that the target partial private key is not known by $\mathcal{A}$.
(iii) For $\mathcal{A}\in \{\text{CL.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CL.Super-}{\mathcal{A}^{\mathit{II}}}\}$, additionally, it is required that
\[ \mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\nrightarrow {O^{\mathit{CL}.\mathit{SecretV}}},\]
and
\[ \mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\gets {O^{\mathit{CL}.\mathit{CreateU}}},\]
where $\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\gets {O^{\mathit{CL}.\mathit{CreateU}}}$ means that $\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}$ is provided by the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$. Remark 2.
Fundamentally speaking, the original purpose for this restriction is to ensure that the target secret value is not trivially known by Type II adversary. For this purpose, the type II adversary is prohibited from generating the target public key by himself. In fact, previous security definitions require that the target public key must be the original one for the target identity, while our definition only requires that the current public key must come from the challenger, or formally the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$. For example, the adversary gets Alice’s public key $p{k_{A}}$ and Bob’s public key $p{k_{B}}$ from the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$, then requires Alice’s public key to take the value of $p{k_{B}}$ through the oracle ${O^{\mathit{CL}.\mathit{ReplacePK}}}$, and finally forges the signature corresponding to Alice’s identity and her replaced (not original) public key. In this case, although Alice’s public key has been replaced, the adversary still does not know the current secret value and hence this signing forgery should be seen as successful. In fact, our definition formally captures this example, while previous security models leave it out. In fact, this remark for “successful” forgery is somewhat like that for “normal” signing query.
3 Certificate-Based Signature
Definition 3.
A Certificate-Based Signature Scheme (CBS) consists of five algorithms as follows.
-
(i) $\mathsf{CB}.\mathsf{Setup}({1^{k}})\to (\mathit{CB}.\mathit{msk},\mathit{CB}.\mathit{param})$. It takes as input the security parameter ${1^{k}}$ and returns the certifier’s master secret key $\mathit{CB}.\mathit{msk}$ and the system parameter $\mathit{CB}.\mathit{param}$ that includes the description of a string space Γ, which can be any subset of ${\{0,1\}^{\ast }}$.
-
(ii) $\mathsf{CB}.\mathsf{GenUK}(\mathit{CB}.\mathit{param})\to ({\mathit{CB}.\mathit{PK}_{\mathit{ID}}},{\mathit{CB}.\mathit{SK}_{\mathit{ID}}})$. It takes input the system parameter $\mathit{CB}.\mathit{param}$, and outputs the secet/public key pair $({\mathit{SK}_{\mathit{ID}}},{\mathit{PK}_{\mathit{ID}}})$ for a certain entity $\mathit{ID}$.
-
(iii) $\mathsf{CB}.\mathsf{Cert}(\mathit{CB}.\mathit{msk},\mathit{CB}.\mathit{param},\mathit{ID},{\mathit{CB}.\mathit{PK}_{\mathit{ID}}})\to {\mathit{cert}_{\mathit{ID}}}$. It takes as input the master secret key $\mathit{CB}.\mathit{msk}$, the system parameter $\mathit{CB}.\mathit{param}$, the identity $\mathit{ID}$ and its public key ${\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$, and outputs the certificate ${\mathit{cert}_{\mathit{ID}}}$.
-
(iv) $\mathsf{CB}.\mathsf{Sign}(\mathit{CB}.\mathit{param},\mathit{ID},{\mathit{CB}.\mathit{PK}_{\mathit{ID}}},{\mathit{cert}_{\mathit{ID}}},{\mathit{CB}.\mathit{SK}_{\mathit{ID}}},m)\to \mathit{CB}.\sigma $. It takes as input the system parameter $\mathit{CB}.\mathit{param}$, the identity $\mathit{ID}$, the public key $\mathit{CB}.\mathit{PK}$, the certificate ${\mathit{cert}_{\mathit{ID}}}$, the secret key ${\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$ and the message m, and outputs the signature $\mathit{CB}.\sigma $.
-
(v) $\mathsf{CB}.\mathsf{Verify}(\mathit{CB}.\mathit{param},\mathit{ID},{\mathit{CB}.\mathit{PK}_{\mathit{ID}}},m,\mathit{CB}.\sigma )\to b\in \{0,1\}$. It takes as input the system parameter $\mathit{CB}.\mathit{param}$, an identity $\mathit{ID}$, this identity’s public key ${\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$ and a message/signature pair $(m,\mathit{CB}.\sigma )$, and outputs 1 if the signature is correct, or 0 otherwise.
Definition 4.
A CBS scheme is CB-EUF-CMCI secure against a certain kind of adversary
\[ \mathcal{A}\in \big\{\text{CB.Normal-}{\mathcal{A}^{I}},\text{CB.Super-}{\mathcal{A}^{I}},\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}\big\},\]
if no polynomially bounded adversary $\mathcal{A}$ has a non-negligible success probability in the following CBS game. In this definition,
will be called normal Type I adversary, super Type I adversary, normal Type II adversary, and super Type II adversary respectively.(1) Initial: the challenger runs the algorithm CB.Setup, returns $\mathit{CB}.\mathit{Params}$ and the auxiliary information $\mathit{aux}\in \{\mathit{nil},\mathit{CB}.\mathit{msk}\}$ to the attack $\mathcal{A}$ ($\mathit{nil}$ means nothing), where
\[\begin{array}{l@{\hskip4.0pt}l}\mathit{aux}=\mathit{nil},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CB.Normal-}{\mathcal{A}^{I}},\text{CB.Super-}{\mathcal{A}^{I}}\big\},\\ {} \mathit{aux}=\mathit{CB}.\mathit{msk},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}\big\}.\end{array}\]
(2) Queries: in this phase, $\mathcal{A}$ can adaptively make requests to a few oracles among the following ones.
-
(i) ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})\to {\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$. This oracle receives an input $\mathit{ID}$ and outputs this original public key of the identity $\mathit{ID}$.
-
(ii) ${O^{\mathit{CB}.\mathit{ReplacePK}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to \varnothing $. For a public key replacement query $(\mathit{ID},\mathit{CB}.\mathit{PK})$, it sets $\mathit{CB}.\mathit{PK}$ as the current public key of $\mathit{ID}$.
-
(iii) ${O^{\mathit{CB}.\mathit{Corrupt}}}(\mathit{ID})\to {\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$. If $\mathit{ID}$ has been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, this oracle returns the secret key ${\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$ corresponding to $\mathit{ID}$’s original public key. Otherwise, it first makes the oracle query ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})$ and then the oracle query ${O^{\mathit{CB}.\mathit{Corrupt}}}(\mathit{ID})$.
-
(iv) ${O^{\mathit{CB}.\mathit{Cert}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to {\mathit{cert}_{\mathit{ID}}}$. For this certification query, this oracle gets the result ${\mathit{cert}_{\mathit{ID}}}$ by running the algorithm CB.Cert and outputs it.
-
(v) ${O^{\mathit{CB}.\mathit{NSign}}}(\mathit{ID},m)\to \mathit{CB}.\sigma $. If $\mathit{ID}$ has been submitted to ${O^{\mathit{CB}.\mathit{CreateU}}}$, it outputs a valid signature $\mathit{CB}.\sigma $ of m under the original public key ${\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$ of the identity $\mathit{ID}$. Otherwise, it refuses the query.
-
(vi) ${O^{\mathit{CB}.\mathit{SSign}}}(\mathit{ID},m)\to \mathit{CB}.\sigma $. For a super signing query $(\mathit{ID},m)$, it outputs a valid signature $\mathit{CB}.\sigma $ of m under the current public key $\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ of the identity $\mathit{ID}$.
Every attack model $\mathcal{A}$ has its own set ${\mathcal{O}_{\mathcal{A}}}$ of allowed oracles. In particular, with ${\mathcal{O}^{\prime }}=\{{O^{\mathit{CB}.\mathit{CreateUser}}},{O^{\mathit{CB}.\mathit{ReplacePK}}},{O^{\mathit{CB}.\mathit{Corrupt}}}\}$ being commonly allowed,
\[\begin{array}{l@{\hskip4.0pt}l}{\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CB}.\mathit{NSign}}},{O^{\mathit{CB}.\mathit{Cert}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CB.Normal-}{\mathcal{A}^{I}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CB}.\mathit{SSign}}},{O^{\mathit{CB}.\mathit{Cert}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CB.Super-}{\mathcal{A}^{I}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CB}.\mathit{NSign}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}},\\ {} {\mathcal{O}_{\mathcal{A}}}={\mathcal{O}^{\prime }}\cup \big\{{O^{\mathit{CB}.\mathit{SSign}}}\big\},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}=\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}.\end{array}\]
(3) Output: after all queries, $\mathcal{A}$ outputs a forgery $({\mathit{ID}^{\ast }},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }})$. Let $\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$ be the current public key of ${\mathit{ID}^{\ast }}$. $\mathcal{A}$ is said to win the game if this forgery satisfies the following requirements.
-
(i) For $\mathcal{A}\in \{\text{CB.Normal-}{\mathcal{A}^{I}},\text{CB.Super-}{\mathcal{A}^{I}},\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}\}$, it is commonly required that\[ 1=\mathsf{CB}.\mathsf{Verify}\big(\mathit{CB}.\mathit{mpk},\mathit{CB}.\mathit{param},{\mathit{ID}^{\ast }},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }}\big),\]and where\[\begin{array}{l@{\hskip4.0pt}l}{O^{C\text{B.Sign}}}={O^{\mathit{CB}.\mathit{NSign}}},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CB.Normal-}{\mathcal{A}^{I}},\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}}\big\},\\ {} {O^{C\text{B.Sign}}}={O^{\mathit{CB}.\mathit{SSign}}},\hspace{1em}& \text{for}\hspace{2.5pt}\mathcal{A}\in \big\{\text{CB.Super-}{\mathcal{A}^{I}},\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}\big\}.\end{array}\]
-
(iii) For $\mathcal{A}\in \{\text{CB.Normal-}{\mathcal{A}^{\mathit{II}}},\text{CB.Super-}{\mathcal{A}^{\mathit{II}}}\}$, additionally, it is required that and
4 Generic Construction CLS-2-CBS and Security Proof
Let ${\Pi ^{\mathit{CL}}}$ be a CLS scheme
\[ {\Pi ^{\mathit{CL}}}=(\mathsf{CL}.\mathsf{Setup},\mathsf{CL}.\mathsf{SetSV},\mathsf{CL}.\mathsf{SetPK},\mathsf{CL}.\mathsf{ExtractPPK},\mathsf{CL}.\mathsf{Sign},\mathsf{CL}.\mathsf{Verify}),\]
with algorithms as specified in Definition 1. Then a CBS scheme
\[ {\Pi ^{\mathit{CL}}}=(\mathsf{CB}.\mathsf{Setup},\mathsf{CB}.\mathsf{GenUK},\mathsf{CB}.\mathsf{Cert},\mathsf{CB}.\mathsf{Sign},\mathsf{CB}.\mathsf{Verify})\]
is defined as follows. Let Γ be the identity information space for ${\Pi ^{\mathit{CB}}}$, $\mathcal{PKCB}$ be the public key space for ${\Pi ^{\mathit{CB}}}$ and $\mathcal{IDCL}$ denotes the space of identities for ${\Pi ^{\mathit{CL}}}$. Without loss of generality, we assume that $\mathcal{IDCL}=\Gamma \times \mathcal{PKCB}$.(1) CB.Setup. On input a security parameter ${1^{k}}$, first run
\[ (\mathit{CL}.\mathit{msk},\mathit{CL}.\mathit{param})\gets \mathsf{CL}.\mathsf{Setup}\big({1^{k}}\big).\]
Then set $\mathit{CB}.\mathit{msk}=\mathit{CL}.\mathit{msk}$. Define $\mathit{CB}.\mathit{param}$ by extending $\mathit{CL}.\mathit{param}$ to include some other relative information. The output is $(\mathit{CB}.\mathit{msk},\mathit{CB}.\mathit{param})$.(2) CB.GenUK. On input $\mathit{CB}.\mathit{param}$, first extract $\mathit{CL}.\mathit{param}$ from $\mathit{CB}.\mathit{param}$. Run
\[\begin{array}{r@{\hskip4.0pt}c@{\hskip4.0pt}l}X& \gets & \mathsf{CL}.\mathsf{SetSV}(\mathit{CL}.\mathit{param}),\\ {} \mathit{CL}.\mathit{PK}& \gets & \mathsf{CL}.\mathsf{Set}\mathsf{PK}(\mathit{CL}.\mathit{param},X).\end{array}\]
The output is $(\mathit{CB}.\mathit{PK},\mathit{CB}.\mathit{SK})=(\mathit{CL}.\mathit{PK},X)$.(3) CB.Cert. On input $\mathit{CB}.\mathit{msk},\mathit{CB}.\mathit{param},\mathit{ID},{\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$, first extract $\mathit{CL}.\mathit{param}$ from $\mathit{CB}.\mathit{param}$. Set the $\mathsf{ID}=\mathit{ID}||{\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$ and $\mathit{CL}.\mathit{msk}=\mathit{CB}.\mathit{msk}$. The output is
(4) CB.Sign. On input $\mathit{CB}.\mathit{param}$, ${\mathit{cert}_{\mathit{ID}}}$, ${\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$, m, first extract $\mathit{CL}.\mathit{param}$ from $\mathit{CB}.\mathit{param}$. Then set $\mathsf{ID}=\mathit{ID}||{\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$, ${\mathit{CL}.\mathit{PK}_{\mathsf{ID}}}={\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$, ${D_{\mathsf{ID}}}={\mathit{cert}_{\mathit{ID}}}$, ${X_{\mathsf{ID}}}={\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$. The output is
(5) CB.Verify. On input $\mathit{CB}.\mathit{param},\mathit{ID},{\mathit{CB}.\mathit{PK}_{\mathit{ID}}},m,\mathit{CB}.\sigma $, extract $\mathit{CL}.\mathit{param}$ from $\mathit{CB}.\mathit{param}$. Set $\mathsf{ID}=\mathit{ID}||{\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$, ${\mathit{CL}.\mathit{PK}_{\mathit{ID}}}={\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$ and $\mathit{CL}.\sigma =\mathit{CB}.\sigma $. The output is
The following four theorems deal with the four kinds of adversaries respectively. As will be seen, all these security reductions are perfectly tight and depend on no random oracles. These two reduction features show that both concepts of CBS and CLS are very closely related to each other.
Theorem 1.
Suppose that ${\mathcal{A}^{I}}$ is a super Type I adversary against ${\Pi ^{\mathit{CB}}}$ with success probability ϵ and running time t. Then there is a super Type I adversary ${\mathcal{B}^{I}}$ against ${\Pi ^{\mathit{CL}}}$ with success probability ϵ and running time $O(t)$.
Proof.
Let $\mathcal{C}$ denote the ${\Pi ^{\mathit{CL}}}$ challenger against ${\mathcal{B}^{I}}$. ${\mathcal{B}^{I}}$ mounts a Type I attack on ${\Pi ^{\mathit{CL}}}$ by simulating the challenger for ${\mathcal{A}^{I}}$ and using help from ${\mathcal{A}^{I}}$ as follows.
Initial phase for CBS game. ${\mathcal{B}^{I}}$ obtains from $\mathcal{C}$ the system parameter of ${\Pi ^{\mathit{CL}}}$ and extends it into the system parameter $\mathit{CB}.\mathit{param}$ of ${\Pi ^{\mathit{CB}}}$ as done in $\mathsf{CB}.\mathsf{Setup}$ of ${\Pi ^{\mathit{CB}}}$. ${\mathcal{B}^{I}}$ supplies $\mathit{CB}.\mathit{param}$ to ${\mathcal{A}^{I}}$.
Queries Phase for CBS game. When ${\mathcal{A}^{I}}$ enters the Queries phase for the CBS game, ${\mathcal{B}^{I}}$ accordingly enters the Queries phase of the CLS game. For the oracle queries from ${\mathcal{A}^{I}}$, ${\mathcal{B}^{I}}$ handles these queries as follows.
(1) ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})\to {\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$. If the query $\mathit{ID}$ has been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, it will directly return the previous answer which is recorded in the list L. Otherwise, it does as follows. ${\mathcal{B}^{I}}$ chooses a random identity ${\mathsf{ID}^{\prime }}$ and obtains its original public key $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ through the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$. It sets $\mathsf{ID}=\mathit{ID}||{\mathit{CB}.\mathit{PK}_{{\mathsf{ID}^{\prime }}}}$ and requires the oracle ${O^{\mathit{CL}.\mathit{ReplacePK}}}$ to change the public key of $\mathsf{ID}$ into $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$. In this case, the CBS original public key of ID is the CLS original public key of ${\mathsf{ID}^{\prime }}$. In other words, every original public key for ${\Pi ^{\mathit{CB}}}$ is related with a certain original public key for ${\Pi ^{\mathit{CL}}}$.
Additionally, to record the above operations for future use, ${\mathcal{B}^{I}}$ sets the original public key
\[ \mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}\]
and the current public key
and adds the tuple
to the initially empty list L.(2) ${O^{\mathit{CB}.\mathit{ReplacePK}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to \varnothing $. If $\mathit{ID}$ has not been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, ${\mathcal{B}^{I}}$ first makes the query ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})$ by himself before the following operations. Otherwise, it directly does the following. ${\mathcal{B}^{I}}$ sets $\mathsf{ID}=\mathit{ID}||\mathit{CB}.\mathit{PK}$, and sequentially makes two oracle queries ${O^{\mathit{CL}.\mathit{CreateU}}}(\mathsf{ID})$ and ${O^{\mathit{CL}.\mathit{ReplacePK}}}$ $(\mathsf{ID},\mathit{CB}.\mathit{PK})$ to change the public key value of $\mathsf{ID}$ into $\mathit{CB}.\mathit{PK}$.
Additionally, to record the above operation, ${\mathcal{B}^{I}}$ searches the relative tuple
\[ \big(\mathit{ID},{\mathsf{ID}^{\prime }},\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}},\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}\big),\]
and then changes the value of $\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ into $\mathit{CB}.\mathit{PK}$.(3) ${O^{\mathit{CB}.\mathit{Corrupt}}}(\mathit{ID})\to {\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$. Without loss of generality, we assume that $\mathit{ID}$ has been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$. ${\mathcal{B}^{I}}$ searches the corresponding tuple
\[ \big(\mathit{ID},{\mathsf{ID}^{\prime }},\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}},\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}\big)\]
in the list L. Then it makes the oracle query ${O^{\mathit{CL}.\mathit{SecretV}}}(\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}})$ and relays this answer to the attacker ${\mathcal{A}^{I}}$. Here note $\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$.(4) ${O^{\mathit{CB}.\mathit{Cert}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to {\mathit{cert}_{\mathit{ID}}}$. Without loss of generality, we assume that the current public key $\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}=\mathit{CB}.\mathit{PK}$ in the corresponding tuple
\[ \big(\mathit{ID},{\mathsf{ID}^{\prime }},\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}},\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}\big)\]
of the list L. ${\mathcal{B}^{I}}$ sets $\mathsf{ID}=\mathit{ID}||\mathit{CB}.\mathit{PK}$, makes the oracle query ${O^{\mathit{CL}.\mathit{PartialPK}}}(\mathsf{ID})$, and then relays the returned partial private key ${D_{\mathsf{ID}}}$ as the certificate for ${\mathcal{A}^{I}}$.(5) ${O^{\mathit{CB}.\mathit{SSign}}}(\mathit{ID},m)\to \mathit{CB}.\sigma $. For a query $(\mathit{ID},m)$, this oracle browses the list L for the corresponding tuple
\[ \big(\mathit{ID},{\mathsf{ID}^{\prime }},\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}},\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}\big).\]
Then it sets $\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$, makes the signing oracle query ${O^{\mathit{CL}.\mathit{SSign}}}(\mathsf{ID},m)$ and relays this answer to ${\mathcal{A}^{I}}$.
Output for CBS game. Now the attacker ${\mathcal{A}^{I}}$ returns its forgery $({\mathit{ID}^{\ast }},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }})$. Without loss of generality, we assume that ${\mathcal{A}^{I}}$ has made the oracle query ${O^{\mathit{CB}.\mathit{CreateU}}}$ or the replacing public key oracle query for ${\mathit{ID}^{\ast }}$. ${\mathcal{B}^{I}}$ browses the list L for the the corresponding tuple
\[ \big({\mathit{ID}^{\ast }},{\mathsf{ID}^{\prime \ast }},\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}\big),\]
and returns $({\mathsf{ID}^{\ast }},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }})$ to its challenger $\mathcal{C}$, where
Analysis. First, from the relations of ${\Pi ^{\mathit{CB}}}$ and ${\Pi ^{\mathit{CL}}}$, it can be easily or trivially seen that ${\mathcal{B}^{I}}$ perfectly simulates the game settings for ${\mathcal{A}^{I}}$ in the two phases of Initial and Queries. Second, if the forgery $({\mathit{ID}^{\ast }},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }})$ is successful, i.e. this forgery satisfies the three additions:
\[\begin{array}{r@{\hskip4.0pt}c@{\hskip4.0pt}l}\mathsf{CB}.\mathsf{Verify}\big(\mathit{CB}.\mathit{param},{\mathit{ID}^{\ast }},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},m\ast ,\mathit{CB}.{\sigma ^{\ast }}\big)& =& 1,\\ {} \big({\mathit{ID}^{\ast }},{m^{\ast }}\big)& \nrightarrow & {O^{\mathit{CB}.\mathit{SSign}}},\\ {} \big({\mathit{ID}^{\ast }},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}\big)& \nrightarrow & {O^{\mathit{CB}.\mathit{Cert}}},\end{array}\]
then, by checking these two groups of three restrictions one by one (the above and the below), it easily follows that $({\mathsf{ID}^{\ast }},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }})$ is also successful, i.e. this forgery satisfies that
\[\begin{array}{r@{\hskip4.0pt}c@{\hskip4.0pt}l}\mathsf{CL}.\mathsf{Verify}\big(\mathit{CL}.\mathit{param},{\mathsf{ID}^{\ast }},\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }}\big)& =& 1,\\ {} \big({\mathsf{ID}^{\ast }},{m^{\ast }}\big)& \nrightarrow & {O^{\mathit{CL}.\mathit{SSign}}},\\ {} {\mathsf{ID}^{\ast }}& \nrightarrow & {O^{\mathit{CL}.\mathit{PartialPK}}}.\end{array}\]
Hence, the success probability of ${\mathcal{B}^{I}}$ is same to that of ${\mathcal{A}^{I}}$. Additionally, since what ${\mathcal{B}^{I}}$ mainly does in reduction is just issuing some relative queries to $\mathcal{C}$, it is obvious that the time of ${\mathcal{B}^{I}}$ is almost equal to the time t of ${\mathcal{A}^{I}}$. Hence we say that the running time of ${\mathcal{B}^{I}}$ is $O(t)$. □Theorem 2.
Suppose that ${\mathcal{A}^{\mathit{II}}}$ is a super Type II adversary against ${\Pi ^{\mathit{CB}}}$ with success probability ϵ and running time t. Then there is a super Type II adversary ${\mathcal{B}^{\mathit{II}}}$ against ${\Pi ^{\mathit{CL}}}$ with success probability ϵ and $O(t)$.
Proof.
Let $\mathcal{C}$ denote a ${\Pi ^{\mathit{CL}}}$ challenger against Type II adversary ${\mathcal{B}^{\mathit{II}}}$. ${\mathcal{B}^{\mathit{II}}}$ mounts a Type II attack on ${\Pi ^{\mathit{CL}}}$ using help from ${\mathcal{A}^{\mathit{II}}}$ as follows.
Initial for CBS game. How ${\mathcal{B}^{\mathit{II}}}$ communicates with ${\mathcal{A}^{\mathit{II}}}$ is the same to how ${\mathcal{B}^{I}}$ communicates with ${\mathcal{A}^{I}}$ in the above proof for Theorem 1, except that ${\mathcal{B}^{\mathit{II}}}$ additionally gets the master private key $\mathit{CL}.\mathit{msk}$ and relays it to ${\mathcal{A}^{\mathit{II}}}$ as the master key $\mathit{CB}.\mathit{msk}$ for ${\Pi ^{\mathit{CB}}}$.
Queries for CBS game. How ${\mathcal{B}^{\mathit{II}}}$ answers these queries from ${\mathcal{A}^{\mathit{II}}}$ is the same to how ${\mathcal{B}^{I}}$ simulates the oracles for ${\mathcal{A}^{I}}$ in the above proof for Theorem 1, except that ${\mathcal{A}^{\mathit{II}}}$ does not query the oracle ${O^{\mathit{CB}.\mathit{Cert}}}$.
Output for CBS game. How ${\mathcal{B}^{\mathit{II}}}$ generates the forged signature is the same to how ${\mathcal{B}^{I}}$ generates the forged signature in the above proof for Theorem 1. Of course, the forged signatures from ${\mathcal{B}^{I}}$ and ${\mathcal{B}^{\mathit{II}}}$ satisfy different conditions.
Analysis. This analysis can immediately follow from the analysis in the above proof of Theorem 1. Here, we only deal with the somewhat difficult part of the analysis. In particular, we will show how to get
\[ \mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\nrightarrow {O^{\mathit{CL}.\mathit{SecretV}}},\hspace{1em}\text{and}\hspace{1em}\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\gets {O^{\mathit{CL}.\mathit{CreateU}}},\]
from
\[ {\mathit{ID}^{\ast }}\nrightarrow {O^{\mathit{CB}.\mathit{Corrupt}}},\hspace{1em}\text{and}\hspace{1em}\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}={O^{\mathit{CB}.\mathit{CreateU}}}\big({\mathit{ID}^{\ast }}\big),\]
where
\[ {\mathsf{ID}^{\ast }}={\mathit{ID}^{\ast }}||\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},\hspace{2em}\mathit{CL}.{\sigma ^{\ast }}=\mathit{CB}.{\sigma ^{\ast }}.\]
By checking the simulation of the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$ by ${\mathcal{B}^{\mathit{II}}}$ for ${\mathcal{A}^{\mathit{II}}}$ (same to those in the proof of Theorem 1), the equation $\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}={O^{\mathit{CB}.\mathit{CreateU}}}({\mathit{ID}^{\ast }})$ means that the original public key $\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$ is equal to the current public key $\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$, i.e. that
\[ \mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}=\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}.\]
By checking the simulation of oracles ${O^{\mathit{CB}.\mathit{CreateU}}}$ and ${O^{\mathit{CB}.\mathit{ReplacePK}}}$, it can be seen that the CLS current public key $\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ of $\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ is always equal to the CBS current public key $\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ of $\mathit{ID}$. In particular, for ${\mathsf{ID}^{\ast }}={\mathit{ID}^{\ast }}||\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$, we have
\[ \mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}=\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}.\]
Let the tuple $({\mathit{ID}^{\ast }},{\mathsf{ID}^{\prime \ast }},\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}})$ be the corresponding record in L. Then by checking the simulation of the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$ again, it can be seen that the CBS original public key $\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$ is equal to the CLS original public key $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}$ of ${\mathsf{ID}^{\prime \ast }}$, i.e. that
\[ \mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}.\]
By the above three equations, we can get
\[ \mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}.\]
Hence, from
\[ \mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}={O^{\mathit{CB}.\mathit{CreateU}}}\big({\mathit{ID}^{\ast }}\big),\]
we can get that
\[ \mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}\gets {O^{\mathit{CL}.\mathit{CreateU}}}.\]
By checking the oracle simulation process provided by ${\mathcal{B}^{\mathit{II}}}$ to ${\mathcal{A}^{\mathit{II}}}$ (same to those in the proof of Theorem 1), it can be seen that ${O^{\mathit{CL}.\mathit{SecretV}}}(\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}})$ is queried by ${\mathcal{B}^{\mathit{II}}}$ only when ${O^{\mathit{CB}.\mathit{Corrupt}}}({\mathit{ID}^{\ast }})$ is queried by ${\mathcal{A}^{\mathit{II}}}$. Then by the just proved equation $\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}$, we prove that ${O^{\mathit{CL}.\mathit{SecretV}}}$ $(\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}})$ is queried by ${\mathcal{B}^{\mathit{II}}}$ only when ${O^{\mathit{CB}.\mathit{Corrupt}}}({\mathit{ID}^{\ast }})$ is queried by ${\mathcal{A}^{\mathit{II}}}$. In other words, from
we can get
□Theorem 3.
Suppose that ${\mathcal{A}^{I}}$ is a normal Type I adversary against ${\Pi ^{\mathit{CB}}}$ with success probability ϵ and running time t. Then there is a normal Type I adversary ${\mathcal{B}^{I}}$ against ${\Pi ^{\mathit{CL}}}$ with success probability ϵ and running time $O(t)$.
Proof.
The proof for Theorem 3 is the same to that for Theorem 1, except the difference that the CBS normal signing oracle is simulated depending on the CLS normal signing oracle in this proof for Theorem 3, while the CBS super signing oracle is simulated depending on the CLS super signing oracle in this proof for Theorem 1. Now show how to simulate the CBS normal signing oracle using the CLS normal signing oracle.
For a normal signing query ${O^{\mathit{CB}.\mathit{NSign}}}(\mathit{ID},m)$, browse the list L for the corresponding tuple
\[ \big(\mathit{ID},{\mathsf{ID}^{\prime }},\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}},\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}\big).\]
Set $\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ and make the signing oracle query ${O^{\mathit{CL}.\mathit{NSign}}}(\mathsf{ID},m)$ and relay this answer to ${\mathcal{A}^{I}}$. By checking the simulation of the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, it can be seen that the original CBS public key $\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}}$ of $\mathit{ID}$ is the original CLS public key $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ of ${\mathsf{ID}^{\prime }}$, and the original CLS public key $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ of ${\mathsf{ID}^{\prime }}$ is the current CLS public key $\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ of $\mathsf{ID}$. Hence, the query $(\mathsf{ID},m)$ will not be rejected by the oracle ${O^{\mathit{CL}.\mathit{NSign}}}$. Hence, this proof can immediately follow Theorem 1. □Theorem 4.
Suppose that ${\mathcal{A}^{I}}$ is a normal Type II adversary against ${\Pi ^{\mathit{CB}}}$ with success probability ϵ and running time t. Then there is a normal Type II adversary ${\mathcal{B}^{I}}$ against ${\Pi ^{\mathit{CL}}}$ with success probability ϵ and running time $O(t)$.
Proof.
The proof for Theorem 4 is the same to that for Theorem 2, except for the difference that the CBS normal signing oracle is simulated depending on the CLS normal signing oracle in this proof for Theorem 4, while the CBS super signing oracle is simulated depending on the CLS super signing oracle in this proof for Theorem 2. Additionally, in the proof of Theorem 3, we have showed how to simulate the CBS normal signing oracle by using the CLS normal signing oracle. Hence, this proof can immediately follow Theorem 2 and Theorem 3. □
5 Comparison Between CLS-2-CBS with Wu et al.’s Result
-
(1) Our generic construction is very similar to that of Wu et al. (2009). In particular, if we replace with\[ \mathsf{ID}=\mathrm{H}(\mathit{ID}||{\mathrm{CB}.\mathrm{PK}_{\mathit{ID}}}),\hspace{1em}\text{where}\hspace{2.5pt}H\hspace{2.5pt}\text{is a hash function},\]then our construction will become identical with Wu et al.’s (2009) construction.
-
(2) Our security proof is in the standard model. Contrastingly, the security proof in Wu et al. (2009) relies the assumption that the hash function in $\mathsf{ID}=\mathrm{H}(\mathit{ID}||{\mathit{CB}.\mathit{PK}_{\mathit{ID}}})$ is a random oracle. As a result, our method can convert a CLS scheme secure in the standard model into a CBS scheme secure in the standard model. However, through Wu et al.’s method, the resulting CBS scheme is only secure in the random oracle model. Of course, the standard model is preferable over the random oracle model in security proof Canetti et al. (2004).
-
(3) We emphasize the theoretical significance of our generic construction. Roughly speaking, by our result, the cryptographic primitive of CBS can be obtained from the single primitive of CLS. However, by Wu et al.’s result, the primitive of CBS can not be obtained from the single primitive of CLS, since the random oracle is additionally needed.
-
(4) To support our generic conversion, the new CLS security model is developed by introducing one nontrivial attack never mentioned before. This new definition succeeds in more elaborately capturing the security notion of CLS. Notably, this new security is inherently preserved in many existing CLS schemes. In other words, our contribution in this respect is that we point out, formalize, and apply this subtle property to refine the close relation between CLS and CBS.
6 Application Example – One Concrete CBS scheme
Let ${\mathbb{G}_{1}}$ and ${\mathbb{G}_{2}}$ be two groups of prime order q and let P be a generator of ${\mathbb{G}_{1}}$, where ${\mathbb{G}_{1}}$ is additively represented and ${\mathbb{G}_{2}}$ is multiplicatively represented. A map $e:{\mathbb{G}_{1}}\times {\mathbb{G}_{1}}\to {\mathbb{G}_{2}}$ is said to be a bilinear pairing, if the following three conditions hold: (1) e is bilinear, i.e. $e(aP,bP)=e{(P,P)^{ab}}$ for all $a,b\in {\mathbb{Z}_{q}^{\ast }}$; (2) e is non-degenerate, i.e. $e(P,P)\ne 1$, where 1 is the identity of ${\mathbb{G}_{2}}$; (3) e is efficiently computable.
The CDH problem: given P, $aP$, $bP$ with uniformly random choices of $a,b\in {\mathbb{Z}_{q}}$, output $abP$. An algorithm $\mathcal{A}$ has success probability ϵ in solving the CDH problem, if
The CDH problem is said to be $(t,\epsilon )$-intractable if there is no algorithm to solve this problem with time less than t and success probability greater than ϵ.
The following scheme is constructed from the second CLS scheme in Huang et al. (2011) through the generic conversion $\mathit{CLS}$-2-$\mathit{CBS}$.
-
(i) $\mathsf{Setup}({1^{k}})\to (\mathit{msk},\mathit{params})$. This algorithm is run by the authority CA. Let ${\mathbb{G}_{1}}$ and ${\mathbb{G}_{2}}$ be two groups of prime order q, P be a generator of ${\mathbb{G}_{1}}$, and $e:{\mathbb{G}_{1}}\times {\mathbb{G}_{1}}\to {\mathbb{G}_{2}}$ be a bilinear pairing. It specifies two hash functions ${H_{0}},{H_{1}}:{\{0,1\}^{\ast }}\to {\mathbb{G}_{1}^{\ast }}$. Let Γ be the set of identity information. It chooses the master key $\mathit{msk}=s$ uniformly at random from ${\mathbb{Z}_{q}}$ and computes the public key $\mathit{mpk}=sP$. The system parameter is
-
(ii) $\mathsf{GenUK}(\mathit{params})\to ({\mathit{PK}_{\mathit{ID}}},{\mathit{SK}_{\mathit{ID}}})$. It selects a random ${\mathit{SK}_{\mathit{ID}}}\in {Z_{q}}$, computes ${\mathit{PK}_{\mathit{ID}}}={\mathit{SK}_{\mathit{ID}}}P$ and outputs ${\mathit{SK}_{\mathit{ID}}},{\mathit{PK}_{\mathit{ID}}}$ as $\mathit{ID}$’s secret/public key pair.
-
(iii) $\mathsf{Cert}(\mathit{CB}.\mathit{msk},\mathit{params},\mathit{ID},{\mathit{PK}_{\mathit{ID}}})\to \mathit{cert}$. It sets ${\mathit{cert}_{\mathit{ID}}}=s{H_{0}}(\mathit{ID}||{\mathit{PK}_{\mathit{ID}}})$.
-
(iv) $\mathsf{Sign}(\mathit{params},\mathit{ID},{\mathit{cert}_{\mathit{ID}}},{\mathit{PK}_{\mathit{ID}}},{\mathit{SK}_{\mathit{ID}}},m)\to \sigma $. For a message m, the user $\mathit{ID}$ computes the signature $\sigma =(u,v,W)$, where
-
(v) $\mathsf{Verify}(\mathit{params},\mathit{ID},{\mathit{PK}_{\mathit{ID}}},m,\sigma )\to b$. Given a message/signature pair $(m,\sigma =(u,v,W))$, user $\mathit{ID}$’s public key ${\mathit{PK}_{\mathit{ID}}}$, anyone can check whether If the equality holds, output 1; otherwise, output 0.
Lemma 1.
The second certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a super Type I adversary.
Proof.
The proof directly follows the observation that (1) the security definition against a super Type I adversary in Huang et al. (2011) is essentially the same as that of ours, except some notation differences. □
Lemma 2.
The second certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a super Type II adversary.
Proof.
First, compare the security definition against a super Type II adversary in Huang et al. (2011) and that of ours.
Next revisit the security proof (for Theorem 4.4) in Huang et al. (2011):
-
(1) Observe the difference: Huang’s definition in Huang et al. (2011) requires that the attacked identity’s public key be the original one, while our definition allows that the attacked identity’s public key can be the replaced one under the constraint condition that this public key must be the other identity’s original public key. In other words, for our definition, the attacker can replace Alice’s public key with Bob’s original public key, and then attack Alice with this replaced public key.
-
(2) Observe the common purpose of these restrictions: in both definitions, the super type II adversary does not know the attacked identity’s current secret value. All in all, facing the same purpose of keeping the target secret value secret from the adversary, our definition tries to make less restrictions while the restriction in Huang’s definition goes too far.
-
(3) Observe the key point of probability analysis (for Theorem 4.4 in Huang et al. (2011)): only if the target public key comes from the challenger and the corresponding secret value is never queried, this security proof always conducts well. In other words, for the proof of Huang et al. (2011), what matters is not that the target public key is “original”, but that the corresponding secret key is not known by this adversary.
At last, following the above observations, we can easily obtain the security proof for Lemma 2, by slightly adapting the security proof for Theorem 4.4 in Huang et al. (2011): in addition to some trivial modifications, change (1) the condition equation “${\mathit{ID}^{\ast }}={\mathit{ID}_{\pi }}$” into “${\mathit{ID}^{\ast }}$’s current public key $={\mathit{ID}_{\pi }}$’s original public key” and (2) “${\mathcal{A}_{II}}$ is not allowed to replace this user’s public key” into “${\mathcal{A}_{II}}$ is not allowed to query the secret value corresponding to this user’s current public key”. Hence, we can omit the detailed proof. □
Theorem 5.
The above CBS scheme is secure (in the random oracle model) against CB.Super-${\mathcal{A}^{I}}$ and CB.Super-${\mathcal{A}^{\mathit{II}}}$, assuming that CDH problem is hard in ${\mathbb{G}_{1}}$.
Remark 3.
Just as the proof of Lemmas 1 and 2, we can similarly prove that many existing certificateless signature schemes are secure in our new security model, by slightly modifying their original proof. In fact, by revisiting the two remarks during Definition 2 in Section 2 and the three observations in Lemma 2, we can conclude that how to get these proofs is almost trivial. In other words, for a normal signing query, the common basic reason why both the original proof and the modified proof conduct well is not that the public key has been replaced, but that the current secret value is not known by the challenger; for a signature forgery, the common basic reason why both the original proof and the modified proof conducts is not that the public key has been replaced, but that the current secret value is not known by the adversary. Hence, these almost trivial modifications and the proof in our new security model for existing CLS schemes can be omitted here. Some examples among them are as follows.
-
(1) The first certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a normal Type I adversary and a super Type II adversary;
-
(2) The certificateless scheme in Huang et al. (2005) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary;
-
(3) The certificateless scheme in Choi et al. (2011) is CL-EUF-CMCI secure against a super Type I adversary and a super Type II adversary;
-
(4) The certificateless scheme in Zhang et al. (2007) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.
-
(5) The certificateless scheme based on RSA in Zhang and Mao (2012) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.
-
(6) The certificateless scheme in Pang et al. (2015) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.
All the above certificateless signature schemes can be used to construct certificate-based signature schemes through the generic framework. For example, based on the state-of-the-art CLS signature scheme secure in the standard model (Pang et al., 2015), we can construct one CBS scheme in the standard model which is almost the same to the the state-of-the-art CBS scheme recently proposed by Lu and Li (2015). Hence, we omit the trivial scheme description. In particular, both of them can be seen as the extension of the famous Waters signature scheme (Waters, 2005).
Now we simply present the efficiency comparisons between the Lu-Li CBS scheme and our CBS scheme generically constructed from Pang et al.’s CLS scheme. First, because both of them are constructed based on the Waters signature scheme, there is almost no difference in the first three algorithms for setup, user key generation and the certification generation of both CBS schemes, except some notational differences. Second, for the signing algorithms, both CBS schemes have the same signature size, i.e. 3 group elements. To generate a signature, our CBS scheme needs 7 exponentiations in the bilinear group, while the Lu-Li CBS scheme needs 6 exponentiations. Third, to verify a signature, both CBS schemes need 3 pairing computations. Here note that group exponentiations and parings are the main computation for generating and verifying a signature respectively. Hence, we can see that the CBS scheme constructed using our generic framework in the standard model is almost as efficient as the Lu-Li CBS scheme in terms of signature size and computation complexity.
7 Conclusion
In this paper, we proposed a new provably secure generic conversion from CLS to CBS. To analyse its security, we redefined the security model for CLS by formalizing some important but previously ignored properties. This new security definition is the main reason why our new conversion can be provably secure in the standard model. As an example, we constructed a new provably secure certificate-based signature scheme by applying this new generic method. These results formally showed that the two conceptions of CBS and CLS (CBC and CLC) are very closely related to each other.
