# Efficient Certificate-Based Signcryption Secure against Public Key Replacement Attacks and Insider Attacks

Authors: Yang Lu; Jiguo Li
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Signcryption is a useful cryptographic primitive that achieves confidentiality and authentication in an efficient manner. As an extension of signcryption in certificate-based cryptography, certificate-based signcryption preserves the merits of certificate-based cryptography and signcryption simultaneously. In this paper, we present an improved security model of certificate-based signcryption that covers both public key replacement attack and insider security. We show that an existing certificate-based signcryption scheme is insecure in our model. We also propose a new certificate-based signcryption scheme that achieves security against both public key replacement attacks and insider attacks. We prove in the random oracle model that the proposed scheme is chosen-ciphertext secure and existentially unforgeable. Performance analysis shows that the proposed scheme outperforms all the previous certificate-based signcryption schemes in the literature.


---

## Body

## 1. Introduction

Public key cryptography (PKC) is an important technique to realize network and information security. In traditional PKC, a public key infrastructure (PKI) is used to provide an assurance to the users about the relationship between a public key and the holder of the corresponding private key by certificates. However, the need for PKI-supported certificates is considered the main difficulty in the deployment and management of traditional PKC. To simplify the management of the certificates, Shamir [1] introduced the concept of identity-based cryptography (IBC) in which the public key of each user is derived directly from his identity, such as an IP address or an e-mail address, and the corresponding private key is generated by a trusted third party called private key generator (PKG). The main practical benefit of IBC lies in the reduction of need for public key certificates. However, if the KGC becomes dishonest, it can impersonate any user using its knowledge of the user’s private key. This is due to the key escrow problem inherent in IBC. In addition, private keys must be sent to the users over secure channels, so private key distribution in IBC becomes a very daunting task.To fill the gap between traditional PKC and IBC, Al-Riyami and Paterson [2] proposed a new paradigm called certificateless public key cryptography (CL-PKC) in Asiacrypt 2003. CL-PKC eliminates the key escrow problem inherent in IBC. At the same time, it preserves the advantage of IBC which is the absence of certificates and their heavy management overhead. In CL-PKC, a trusted third party called key generating center (KGC) is involved in the process of issuing a partial secret key for each user. The user independently generates its public/private key pair and combines the partial secret key from the KGC with its private key to generate the actual decryption key. By way of contrast to the PKG in IBC, the KGC does not have access to the user’s decryption key. Therefore, CL-PKC solves the key escrow problem. However, as partial secret keys must be sent to the users over secure channels, CL-PKC suffers from the distribution problem.In Eurocrypt 2003, Gentry [3] introduced the notion of certificate-based cryptography (CBC). CBC provides an implicit certification mechanism for a traditional PKI and allows for a periodical update of certificate status. As in traditional PKC, each user in CBC generates his own public/private key pair and requests a certificate from a trusted third party called certifier. The certificate will be pushed only to the owner of the public/private key pair and act as a partial decryption key or a partial signing key. This additional functionality provides an efficient implicit certificate mechanism. For example, in the encryption scenario, a receiver needs both his private key and certificate to decrypt a ciphertext sent to him, while the message sender need not be concerned about the certificate revocation problem. The feature of implicit certification allows us to eliminate third-party queries for the certificate status and simply the public key revocation problem so that CBC does not need infrastructures like CRL and OCSP. Therefore, CBC can be used to construct an efficient PKI requiring fewer infrastructures than the traditional one. Although CBC may be inefficient when a certifier has a large number of users, this problem can be overcome by usingsubset covers[3]. Furthermore, there are no key escrow problem (since the certifier does not know the private keys of users) and key distribution problem (since the certificates need not be kept secret) in CBC.Table1 summarizes the comparison of the above cryptosystems.Table 1
Properties of the related public key cryptosystems.
Do not require trusted third party
Implicit certificates
Key escrow  free
Key distribution free
Traditional PKC
×
×
✓
✓
IBC
×
✓
×
×
CL-PKC
×
✓
✓
×
CBC
×
✓
✓
✓Since its advent, CBC has attracted great interest in the research community and many schemes have been proposed, including many encryption schemes (e.g., [4–10]) and signature schemes (e.g., [11–16]). As an extension of the signcryption [17] in CBC, Li et al. [18] introduced the concept of certificate-based signcryption (CBSC) that provides the functionalities of encryption and signature simultaneously. As far as we know, there exist three CBSC schemes in the literature so far. In [18], Li et al. proposed the first CBSC scheme based on Chen and Malone-Lee’s identity-based signcryption scheme [19]. However, they did not give a formal proof of their security claim. A subsequent paper by Luo et al. [20] proposed the second CBSC scheme alone with a security model of CBSC. Recently, Li et al. [21] proposed a publicly verifiable CBSC scheme that is provably secure in the random oracle model.Our Motivations and Contributions. In this paper, we focus on the construction of a CBSC scheme that resists both the public key replacement attacks and the insider attacks.Public key replacement attack was first introduced into CL-PKC by Al-Riyami and Paterson [2]. In this attack, an adversary who can replace a user’s public key with a value of its choice dupes any other third parties to encrypt messages or verify signatures using a false public key. It seems that this attack does not have effect on CBC since a certifier is employed for issuing a certificate for each user. Unfortunately, some previous research works [13, 16, 22] have demonstrated that it does. In CBC, the certifier does issue the certificates. However, as introduced above, CBC adopts the implicit certificate mechanism so that only the owner of a certificate needs to check the validity of his certificate and others need not be concerned about the status of his certificate. Thus, a malicious user is able to launch the public key replacement attack against an ill-designed certificate-based cryptographic scheme. We observe that Luo et al.’s CBSC scheme [20] is insecure under this attack. The concrete attack can be found in Section 4 of this paper.Insider security [23] refers to the security against the attacks made by the insider (i.e., the sender or the receiver). It requires that, even if a sender’s private key is compromised, an attacker should not be able to designcrypt the message generated by the sender and, even with a receiver’s private key, an attacker should not be able to forge a valid signcryption as if generated by the same sender. In contrast to outsider security [23] that refers to the security against the attacks made by the outsider (i.e., any third party except the sender and the receiver), insider security can provide the stronger security for signcryption schemes [24, 25]. Therefore, it has been accepted as a necessary security requirement for a signcryption scheme to achieve. However, none of the previous constructions of CBSC [18, 20, 21] has considered insider security. The previous security models of CBSC [20, 21] only cover the case where the CBSC scheme is attacked by the outsiders. Actually, the public key replacement attack presented in Section 4 also shows that Luo et al.’s CBSC scheme [20] fails in providing insider security.The main contributions of this paper are as follows.(1)
We extend previous works by proposing an improved security model for CBSC that accurately models both the public key replacement attacks and the insider attacks. We show that Luo et al.’s CBSC scheme [20] is insecure in our security model.(2)
We develop a new CBSC scheme and formally prove its security in our improved security model. In the random oracle, we prove that the proposed scheme is chosen-ciphertext secure and existentially unforgeable. To the best of our knowledge, it is the first signcryption scheme that achieves security under both the public key replacement attacks and the insider attacks in the certificate-based cryptographic setting. Furthermore, compared with the previous CBSC schemes, our scheme enjoys better performance, especially in the computation efficiency.Paper Organization. The rest of this paper is organized as follows. In the next section, we briefly review some preliminaries required in this paper. In Section 3, we present an improved security model of CBSC. In Section 4, we show that Luo et al.’s CBSC scheme is insecure in our security model. The proposed CBSC scheme is described and analyzed in Section 5. Finally, we draw our conclusions in Section 6.


## 2. Preliminaries

Letk be a security parameter and p a k-bit prime number. Let G be an additive cyclic group of prime order p and GT a multiplicative cyclic group of the same order, and let P be a generator of G. A bilinear pairing is a map e:G×G→GT satisfying the following properties.(i)
Bilinearity: for allP1, P2∈G, and all a, b∈Zp*, we have e(aP1,bP2)=e(P1,P2)ab.(ii)
Nondegeneracy:e(P,P)≠1.(iii)
Computability: for allP1, P2∈G, e(P1,P2) can be efficiently computed.The security of our CBSC scheme is based on the following hard problems.Definition 1.
The computational Diffie-Hellman (CDH) problem inG is, given a tuple (P,aP,bP)∈G3 for unknown a, b∈Zp*, to compute abP∈G.Definition 2 (see [26]).
The bilinear Diffie-Hellman (BDH) problem in(G,GT) is, given a tuple (P,aP,bP,cP)∈G4 for unknown a,b,c∈Zp*, to compute e(P,P)abc∈GT.Definition 3 (see [27]).
The collusion attack algorithm withq-traitors (q-CAA) problem in G is given a tuple (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq)∈Gq+2×(Zp*)q for unknown α∈Zp*, to compute (ω*+α)-1P for some value ω*∉{ω1,…,ωq}.Definition 4 (see [28]).
The modified bilinear Diffie-Hellman inversion forq-values (q-mBDHI) problem in G is given a tuple (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq)∈Gq+2×(Zp*)q for unknown α∈Zp*, to compute e(P,P)(ω*+α)-1 for some value ω*∈Zp*-{ω1,…,ωq}.


## 3. Improved Security Model for CBSC Schemes

In this section, we present an improved security model for CBSC that covers both public key replacement attack and insider security. Below, we first briefly review the definition of CBSC.Formally, a CBSC scheme is specified by the following five algorithms.(i)
Setup(k): on input a security parameter k∈Z+, this algorithm generates a master key msk and a list of public parameters params. This algorithm is performed by a certifier. After the algorithm is performed, the certifier publishes params and keeps msk secret.(ii)
UserKeyGen(params): on input the public parameters params, this algorithm generates a private key and public key pair (SKU,PKU) for a user with identity idU.(iii)
CertGen(params,msk,idU,PKU): on input the public parameters params, the master key msk, a user’s identity idU, and public key PKU, this algorithm generates a certificate CertU. This algorithm is performed by a certifier. After this algorithm is performed, the certifier sends the certificate CertU to the user idU via an open channel.(iv)
Signcrypt(params,M,idS,PKS,SKS,CertS,idR,PKR): on input the public parameters params, a sender’s identity idS, public key PKS, private key SKS and certificate CertS, a receiver’s identity idR, and public key PKR, this algorithm generates a ciphertext σ.(v)
Designcrypt(params,σ,idR,PKR,SKR,CertR,idS,PKS): on input the public parameters params, a ciphertext σ, the receiver’s identity idR, public key PKR, private key SKR and certificate CertR, the sender’s identity idS, and public key PKS, this algorithm outputs either a plaintext M or a special symbol ⊥ indicating a designcryption failure.As introduced in [3], the adversaries against a certificate-based cryptographic scheme should be divided into two types: Type I and Type II. Type I adversary (denoted by AI) models an uncertified user while Type II adversary (denoted by AII) models an honest-but-curious certifier who is equipped with the master key. In order to capture public key replacement attack, the Type I adversary AI in our CBSC security model is allowed to replace any user’s public key. Note that the Type II adversary AII should not be allowed to make public key replacement attacks; otherwise, it may trivially break the security of a CBSC scheme using a man-in-the-middle attack.A CBSC scheme should satisfy both confidentiality (i.e., indistinguishability against adaptive chosen-ciphertext attacks (IND-CBSC-CCA2)) and unforgeability (i.e., existential unforgeability against adaptive chosen-messages attacks (EUF-CBSC-CMA)).The confidentiality security of a CBSC scheme is defined via the following two games: “IND-CBSC-CCA2 Game-I” and “IND-CBSC-CCA2 Game-II,” in which a Type I adversary AI and a Type II adversary AII interact with a challenger, respectively.IND-CBSC-CCA2 Game-I.This game is played between AI and a challenger.Setup. The challenger runs the algorithmSetup(k) to generate msk and params. It then returns params to AI and keeps msk to itself.Phase 1. In this phase, AI makes requests to the following oracles adaptively.(i)
OCreateUser: on input an identity idU, if idU has already been created; the challenger outputs the current public key PKU associated with idU. Otherwise, it performs the algorithmUserKeyGen(params) to generate a private/public key pair (SKU,PKU), inserts (idU,PKU,SKU) into a list, and outputs PKU. In this case, idU is said to be created. We assume that other oracles defined below only respond to an identity which has been created.(ii)
OReplacePublicKey: on input an identity idU and a value PKU′, the challenger replaces the current public key of the identity idU with PKU′. Note that the current value of a user’s public key is used by the challenger in any computations or responses to AI’s requests. This oracle models the ability of a Type I adversary to convince a legitimate user to use a false public key and thus enables our security model to capture the public key replacement attacks attempted by the Type I adversary AI.(iii)
OGenerateCertificate: on input an identity idU, the challenger responds with a certificateCertU by running the algorithmCertGen(params,msk,idU,PKU).(iv)
OExtractPrivateKey: on input an identity idU, the challenger responds with a private key SKU. Here, AI is disallowed to query this oracle on any identity for which the public key has been replaced. This restriction is imposed due to the fact that it is unreasonable to expect the challenger to be able to provide a private key of a user for which it does not know the private key.(v)
OSigncryption: on input a message M, a sender’s identity idS, and a receiver’s identity idR, the challenger responds with σ=Signcrypt(params,M,idS,PKS,SKS,CertS,idR,PKR). Note that it is possible that the challenger is not aware of the sender’s private key if the associated public key has been replaced. In this case, we require AI to provide it. In addition, we do not consider attacks targeting ciphertexts where the identities of the sender and receiver are the same. So, we disallow queries where idS=idR.(vi)
ODesigncryption: on input a ciphertext σ, a sender’s identity idS, and a receiver’s identity idR, the challenger responds with the result ofDesigncrypt(params,σ,idR,PKR,SKR,CertR,idS,PKS). Note that it is possible that the challenger is not aware of the receiver’s private key if the associated public key has been replaced. In this case, we require AI to provide it. Again, we disallow queries where idS=idR.Challenge. Once AI decides that Phase 1 is over, it outputs two equal-length messages (M0,M1) and two distinct identities (idS*,idR*). The challenger picks a random bit b, computes σ*=Signcrypt(params,Mb,idS*,PKS*,SKS*,CertS*,idR*,PKR*), and returns σ* as the challenge ciphertext to AI.Phase 2. In this phase, AI continues to issues queries as in Phase 1.Guess. Finally, AI outputs a guess b′∈{0,1}. We say that AI wins the game if b=b′ and the following conditions are simultaneously satisfied: (1)AI cannot query OGenerateCertificate on the identity idR* at any point; (2)AI cannot query OExtractPrivateKey on an identity if the corresponding public key has been replaced; (3) in Phase 2, AI cannot query ODesigncryption on (σ*,idS*,idR*) unless the public key of the sender idS* or that of the receiver idR* has been replaced after the challenge was issued. We define AI’s advantage in this game to be 2|Pr{b=b′}-1/2|.IND-CBSC-CCA2 Game-II.This game is played between AII and a challenger.Setup. The challenger runs the algorithmSetup(k) to generate msk and params. It then returns params and msk to AII.Phase 1. In this phase, AII adaptively asks a polynomial bounded number of queries as inIND-CBSC-CCA2 Game-I. The only restriction is that AII cannot replace public keys of any users. In addition, AII need not make any queries to OGenerateCertificate since it can compute the certificates for any identities by itself with the master key msk.Challenge. Once AII decides that Phase 1 is over, it outputs two equal-length messages (M0,M1) and two distinct identities (idS*,idR*). The challenger picks a random bit b, computes σ*=Signcrypt(params,Mb,idS*,PKS*,SKS*,CertS*,idR*,PKR*), and returns σ* as the challenge ciphertext to AII.Phase 2. In this phase, AII continues to issue queries as in Phase 1.Guess. Finally, AII outputs a guess b′∈{0,1}. We say that AII wins the game if b=b′ and the following two conditions are both satisfied: (1)AII cannot query OExtractPrivateKey on the identity idR* at any point; (2)AII cannot query ODesigncryption on (σ*,idS*,idR*) in Phase 2. We define AII’s advantage in this game to be 2|Pr{b=b′}-1/2|.Definition 5.
A CBSC scheme is said to be IND-CBSC-CCA2 secure if no probabilistic polynomial time (PPT) adversary has nonnegligible advantage in the above two games.Remark 6.
The oracleOReplacePublicKey defined in the gameIND-CBSC-CCA2 Game-I models the ability of a Type I adversary to convince a legitimate user to use a false public key. It enables our security model to capture the public key replacement attacks attempted by the Type I adversary AI.Remark 7.
The adversary in the above definition of message confidentiality is allowed to be challenged on a ciphertext generated using a corrupted sender’s private key and certificate. This condition corresponds to the stringent requirement of insider security for confidentiality of signcryption [23]. This means that our security model ensures that the confidentiality of signcryption is preserved even if a sender’s private key is corrupted.The unforgeability security of a CBSC scheme is defined via the following two games: “EUF-CBSC-CMA Game-I” and “EUF-CBSC-CMA Game-II,” in which a Type I adversary AI and a Type II adversary AII interact with a challenger, respectively.EUF-CBSC-CMA Game-I.This game is played between AI and a challenger.Setup. The challenger runs the algorithmSetup(k) to generate msk and params. It then returns params to AI and keeps msk to itself.Query. In this phase, AI can adaptively ask a polynomial bounded number of queries as in the gameIND-CBSC-CCA2 Game-I.Forge. Finally, AI outputs a forgery (σ*,idS*,idR*). We say that AI wins the game if the result ofDesigncrypt(params,σ*,idR*,PKR*,SKR*,CertR*,idS*,PKS*) is not the ⊥ symbol and the following conditions are simultaneously satisfied: (1)AI cannot query OGenerateCertificate on the identity idS* at any point; (2)AI cannot query OExtractPrivateKey on an identity if the corresponding public key has been replaced; (3)σ* is not the output of any OSigncryption query on (M*,idS*,idR*), where M* is a message. We define AI’s advantage in this game to be the probability that it wins the game.EUF-CBSC-CMA Game-II.This game is played between AII and a challenger.Setup. The challenger runs the algorithmSetup(k) to generate msk and params. It then returns params and msk to AII.Query. In this phase, AII can adaptively ask a polynomial bounded number of queries as in the gameIND-CBSC-CCA2 Game-II.Forge. Finally, AII outputs a forgery (σ*, idS*, idR*). We say that AII wins the game if the result ofDesigncrypt(params,σ*,idR*,PKR*,SKR*,CertR*,idS*,PKS*) is not the ⊥ symbol and the following conditions are simultaneously satisfied: (1)AII cannot query OExtractPrivateKey on the identity idS*; (2)σ* is not the output of any OSigncryption query on (M*, idS*, idR*), where M* is a message. We define AII’s advantage in this game to be the probability that it wins the game.Definition 8.
A CBSC scheme is said to be EUF-CBSC-CMA secure if no PPT adversary has nonnegligible advantage in the above two games.Remark 9.
The adversary in the above definition of signature unforgeability may output a ciphertext generated using a corrupted receiver’s private key and certificate. Again, this condition corresponds to the stringent requirement of insider security for unforgeability of signcryption [23]. Hence, our security model also ensures that the unforgeability of signcryption is preserved even if a receiver’s private key is corrupted.


## 4. Cryptanalysis of Luo et al.’s CBSC Scheme

In this section, we give the review and attack of Luo et al.’s CBSC scheme [20].


### 4.1. Review of Luo et al.’s CBSC Scheme

Luo et al.’s CBSC scheme consists of the following six algorithms.(i)
Setup: given a security parameter k, the certifier performs as follows: generate two cyclic groups G and GT of prime order p such that there exists a bilinear pairing map e:G×G→GT; select a random element s∈Zp* and a random generator P∈G, and compute Ppub=sP; select four hash functions H1:{0,1}n×G→G, H2:{0,1}n×G×G→G, H3:G×G×{0,1}n→Zp*, and H4:GT→{0,1}n; set the public parameters params={p,G,GT,e,n,P,Ppub,H1,H2,H3,H4} and the master key msk=s.(ii)
UserKeyGen: given params, a user with identity idU∈{0,1}n chooses a random xU∈Zp* as his private key SKU and then computes his public key PKU=xUP.(iii)
CertGen: to generate a certificate for the user with identity idU and public key PKU, the certifier computes QU=H1(idU,PKU) and outputs the certificate CertU=sQU.(iv)
Sender Signcrypt: to send a message M∈{0,1}n to the receiver idR, the sender idS does the following: randomly choose r∈Zp* and compute R=rP and T=H2(idS,PKS,R); compute h=H3(R,S,M) and V=r-1(CertS+SKS·T+h·Ppub); compute W=e(PKS,PKR)r and then C=M⊕H4(W); set the ciphertext σ=(C,R,V).(v)
Receiver Decrypt: when receiving a ciphertext σ=(C,R,V) from the sender idS, the receiver idR does the following: compute M=C⊕H4(W) where W=e(R,SKR·PKS); forward the message M and signature (R,V) to the algorithmReceiver Verify.(vi)
Receiver Verify: to verify the sender idS’s signature (R,V) on the message M, the receiver idR does the following: compute S=H2(idS,PKS,R) and h=H3(R,S,M); check whether e(R,V)=e(Ppub,QS)e(PKS,S)e(P,Ppub)h. If the check holds, output M; otherwise, output ⊥.


### 4.2. Attack on Luo et al.’s CBSC Scheme

A Type I adversary who is capable of replacing any user’s public key can forge a valid signcryption on any messageM from idS to idR by performing the following steps.(1)
Replace the senderidS’s public key with PKS′=xS′Ppub, where xS′ is a random value chosen from Zp*.(2)
Choose a random valuer′∈Zp* and compute R′=r′Ppub and T′=H2(idS,PKS′,R′).(3)
Choose a random messageM∈{0,1}n and compute V′=r′-1(QS+xS′T′+h′P), where QS=H1(idS,PKS′) and h′=H3(R′,T′,M).(4)
Randomly chooseC′∈{0,1}n and set σ′=(C′,R′,V′) as the signcryption of the message M. Note that if the adversary has corrupted the receiver idR’s private key SKR, it can compute C′=M⊕H4(W′), where W′=e(R′,SKR,PKS′).The ciphertextσ′=(C′,R′,V′) passes the verification test as shown below:
(1)e(Ppub,QS)e(PKS′,T′)e(P,Ppub)h′=e(Ppub,QS+xS′T′+h′P)=e(r′Ppub,r′-1(QS+xS′T′+h′P))=e(R′,V′).This proves that the forged signcryption is valid.Note that Luo et al.’s scheme also doses not resist insider attacks since the adversary can forge a valid signcryption using the corrupted receiveridR’s private key in the step (4).


## 4.1. Review of Luo et al.’s CBSC Scheme

Luo et al.’s CBSC scheme consists of the following six algorithms.(i)
Setup: given a security parameter k, the certifier performs as follows: generate two cyclic groups G and GT of prime order p such that there exists a bilinear pairing map e:G×G→GT; select a random element s∈Zp* and a random generator P∈G, and compute Ppub=sP; select four hash functions H1:{0,1}n×G→G, H2:{0,1}n×G×G→G, H3:G×G×{0,1}n→Zp*, and H4:GT→{0,1}n; set the public parameters params={p,G,GT,e,n,P,Ppub,H1,H2,H3,H4} and the master key msk=s.(ii)
UserKeyGen: given params, a user with identity idU∈{0,1}n chooses a random xU∈Zp* as his private key SKU and then computes his public key PKU=xUP.(iii)
CertGen: to generate a certificate for the user with identity idU and public key PKU, the certifier computes QU=H1(idU,PKU) and outputs the certificate CertU=sQU.(iv)
Sender Signcrypt: to send a message M∈{0,1}n to the receiver idR, the sender idS does the following: randomly choose r∈Zp* and compute R=rP and T=H2(idS,PKS,R); compute h=H3(R,S,M) and V=r-1(CertS+SKS·T+h·Ppub); compute W=e(PKS,PKR)r and then C=M⊕H4(W); set the ciphertext σ=(C,R,V).(v)
Receiver Decrypt: when receiving a ciphertext σ=(C,R,V) from the sender idS, the receiver idR does the following: compute M=C⊕H4(W) where W=e(R,SKR·PKS); forward the message M and signature (R,V) to the algorithmReceiver Verify.(vi)
Receiver Verify: to verify the sender idS’s signature (R,V) on the message M, the receiver idR does the following: compute S=H2(idS,PKS,R) and h=H3(R,S,M); check whether e(R,V)=e(Ppub,QS)e(PKS,S)e(P,Ppub)h. If the check holds, output M; otherwise, output ⊥.


## 4.2. Attack on Luo et al.’s CBSC Scheme

A Type I adversary who is capable of replacing any user’s public key can forge a valid signcryption on any messageM from idS to idR by performing the following steps.(1)
Replace the senderidS’s public key with PKS′=xS′Ppub, where xS′ is a random value chosen from Zp*.(2)
Choose a random valuer′∈Zp* and compute R′=r′Ppub and T′=H2(idS,PKS′,R′).(3)
Choose a random messageM∈{0,1}n and compute V′=r′-1(QS+xS′T′+h′P), where QS=H1(idS,PKS′) and h′=H3(R′,T′,M).(4)
Randomly chooseC′∈{0,1}n and set σ′=(C′,R′,V′) as the signcryption of the message M. Note that if the adversary has corrupted the receiver idR’s private key SKR, it can compute C′=M⊕H4(W′), where W′=e(R′,SKR,PKS′).The ciphertextσ′=(C′,R′,V′) passes the verification test as shown below:
(1)e(Ppub,QS)e(PKS′,T′)e(P,Ppub)h′=e(Ppub,QS+xS′T′+h′P)=e(r′Ppub,r′-1(QS+xS′T′+h′P))=e(R′,V′).This proves that the forged signcryption is valid.Note that Luo et al.’s scheme also doses not resist insider attacks since the adversary can forge a valid signcryption using the corrupted receiveridR’s private key in the step (4).


## 5. Our Proposed CBSC Scheme

### 5.1. Description of the Scheme

Our CBSC scheme is constructed from the certificate-based encryption scheme proposed by Lu et al. [8]. It consists of the following five algorithms.(i)
Setup(k): given a security parameter k, the certifier performs the following: generate two cyclic groups G and GT of a k-bit prime order p such that there exists a bilinear pairing map e:G×G→GT; choose two random generators P, Q∈G and compute g=e(P,Q); choose a random element α∈Zp* and set Ppub=αP; select three hash functions H1:{0,1}*×GT→Zp*, H2:GT×GT→{0,1}n and H3:{0,1}*→Zp*, where n is the bit-length of the message to be signcrypted; set the public parameters params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3} and the master key msk=α.(ii)
UserKeyGen(params): given params, a user with identity idU∈{0,1}* chooses a random xU∈Zp* as his private key SKU and then computes his public key PKU=gxU.(iii)
CertGen(params,msk,idU,PKU): to generate a certificate for a user with identity idU and public key PKU, the certifier computes CertU=(H1(idU,PKU)+α)-1Q. The user idU can check the validness of the certificate CertU by verifying whether e(H1(idU,PKU)P+Ppub,CertU)=g.(iv)
Signcrypt(params,M,idS,PKS,SKS,CertS,idR,PKR): to send a message M∈{0,1}n to the receiver idR, the sender idS does the following: randomly choose r∈Zp* and compute R1=gr and R2=(PKR)r; compute U=r(H1(idR,PKR)P+Ppub) and C=M⊕H2(R1,R2); compute V=(h·SKS+r)·CertS, where h=H3(M,U,R1,R2,idS,PKS,idR,PKR); set the ciphertext σ=(C,U,V).(v)
Designcrypt(params,σ,idR,PKR,SKR,CertR,idS,PKS): to designcrypt a ciphertext σ=(C,U,V) from the sender idS, the receiver idR does the following: compute R1=e(U,CertR) and R2=e(U,CertR)SKR; compute M=C⊕H2(R1,R2) and then check whether e(H1(idS,PKS)P+Ppub,V)(PKS)-h=R1, where h=H3(M,U,R1,R2,idS,PKS,idR,PKR). If the check holds, output M; otherwise, output ⊥.The consistency of our scheme can be easily verified by the following equalities:(1)
e(U,CertR)=e(r(H1(idR,PKR)P+Ppub), (H1(idR,PKR)+α)-1Q)=e(P,Q)r=gr;(2)
e(U,CertR)SKR=(gr)SKR=(PKR)r;(3)
(2)e(H1(idS,PKS)P+Ppub,V)(PKS)-h=e((H1(idS,PKS)+α)-1P,(h·SKS+r)·CertS)·(PKS)-h=e(P,(h·SKS+r)Q)·(PKS)-h=e(P,Q)r=R1.


### 5.2. Security Proof

Theorem 10.
The CBSC scheme above is IND-CBSC-CCA2 secure under the hardness of the q-mBDHI and BDH problems in the random oracle model.This theorem can be proved by combining the following two lemmas.Lemma 11.
If a Type I adversaryAI has advantage ε against our CBSC scheme when asking at most qcu to OCreateUser queries, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3, then there exists an algorithm B to solve the (q1-1)-mBDHI problem with advantage
(3)ε′≥εq1(q2+2q3+2qsc)(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).Proof.
Assume thatB is given a random q-mBDHI instance (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq), where q=q1-1. B interacts with AI as follows.
In the setup phase,B randomly chooses t∈Zp* and sets Ppub=αP, Q=tP, and g=e(P,Q). Furthermore, it randomly chooses a value ω*∈Zp* such that ω*∉{ω1,…,ωq} and an index θ∈[1,q1]. Then, B startsIND-CBSC-CCA2 Game-I by supplying AI with params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B.  AI can make queries on these random oracles at any time during the game. Note that the corresponding master key is msk=α which is unknown to B.
Now,B starts to respond to various queries as follows:
H
1
Queries. We assume that q1 queries to H1 are distinct. B maintains a listH1List of tuples 〈idi,PKi,h1,i,Certi〉. On input (idi,PKi), B does the following.(1)
If (idi, PKi) already appears onH1List in a tuple 〈idi,PKi,h1,i,Certi〉, then B returns h1,i to AI.(2)
Else if the query is on theθth distinct (idθ, PKθ), then B inserts 〈idθ,PKθ,ω*,⊥〉 intoH1List and returns h1,θ=ω* to AI. Note that the certificate for the identity idθ is Certθ=t(ω*+α)-1P which is unknown to B.(3)
ElseB sets h1,i to be ωj(j∈[1,q]) which has not been used and computes Certi=t(ωj+α)-1P. It then inserts 〈idi,PKi,h1,i,Certi〉 intoH1List and returns h1,i.
H
2
Queries.
B maintains a listH2Listof tuples 〈R1,R2,h2〉. On input (R1, R2), B does the following. (1)
If (R1, R2) already appears onH2List in a tuple 〈R1,R2,h2〉, B returns h2 to AI.(2)
Otherwise, it returns a randomh2∈{0,1}n and inserts 〈R1,R2,h2〉 intoH2List.
H
3
Queries. B maintains a listH3List of tuples 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉. On input (M,U,R1,R2,idS,PKS,idR,PKR), B does the following. (1)
If(M,U,R1,R2,idS,PKS,idR,PKR) already appears onH3List in a tuple 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉, B returns h3 to AI.(2)
Otherwise, it returns a randomh3∈Zp* to AI. To anticipate possible subsequent queries to ODesigncryption, it additionally simulates the random oracle H2 on its own to obtain h2=H2(R1,R2) and then inserts 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C=M⊕h2〉 intoH3List.
O
C
r
e
a
t
e
U
s
e
r
Queries. B maintains a listKeyList of tuples 〈idi,PKi,SKi,flagi〉 which is initially empty. On input (idi), B does the following. (1)
Ifidi already appears onKeyList in a tuple 〈idi,PKi,SKi,flagi〉, B returns PKi to AI directly.(2)
Otherwise,B randomly chooses xi∈Zp* as the private key SKi for the identity idi and computes the corresponding public key as PKi=gxi. It then inserts 〈idi,PKi,SKi,0〉 intoKeyList and returns PKi to AI.
O
R
e
p
l
a
c
e
P
u
b
l
i
c
K
e
y
r
Queries. On input (idi,PKi′), B searches idi inKeyList to find a tuple 〈idi,PKi,SKi,flagi〉 and updates the tuple with 〈idi,PKi′,SKi,1〉.
O
E
x
t
r
a
c
t
P
r
i
v
a
t
e
K
e
y
Queries. On input (idi), B searches idi inKeyList to find a tuple 〈idi,PKi,SKi,flagi〉. If flagi=0, it returns SKi to AI; otherwise, it rejects this query.
O
G
e
n
e
r
a
t
e
C
e
r
t
i
f
i
c
a
t
e
Queries. On input (idi), B does the following. (1)
If (idi, PKi) = (idθ, PKθ), then B aborts.(2)
Otherwise,B searches idi inH1List to find a tuple 〈idi,PKi,h1,i,Certi〉 and then returns Certi to AI. IfH1List does not contain such a tuple, B queries H1 on (idi, PKi) first.
O
S
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (M, idS, idR), B performs as follows.(1)
If(idS,PKS)≠(idθ,PKθ), B can answer the query according to the specification of the algorithmSigncrypt since it knows the sender idS’s private key and certificate.(2)
Otherwise,B randomly chooses r, h3∈Zp*, h2∈{0,1}n and sets U=r(H1(idθ,PKθ)P+Ppub)-h3SKθ(H1(idR,PKR)P+Ppub), V=rCertR, C=M⊕h2, R1=e(U,CertR), and R2=e(U,CertR)SKR, respectively. It is easy to verify that e(H1(idθ,PKθ)P+Ppub,V)·(PKθ)-h3=e(U,CertR). Then, B inserts 〈R1,R2,h2〉 and 〈M,U,R1,R2,idθ,PKθ,idR,PKR,h3,C〉 intoH2List andH3List,respectively, and returns the ciphertext σ=(C,U,V) to AI. Note that B fails ifH2List orH3List is already defined in the corresponding value, but this only happens with probability smaller than (q2+2q3+2qsc)/2k.
O
D
e
s
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (σ=(C,U,V), idS, idR), B does the following.(1)
If(idR,PKR)≠(idθ,PKθ), B can answer the query according to the specification of the algorithmDesigncrypt since it knows the receiver idR’s private key and certificate.(2)
Otherwise,B searches inH3List for all tuples of the form 〈M,U,R1,R2,idS,PKS,idθ,PKθ,h3,C〉. If no such tuple is found, then σ is rejected. Otherwise, each one of them is further examined. For a tuple 〈M,U,R1,R2,idS,PKS,idθ,PKθ,h3,C〉, B first checks whether e(H1(idS,PKS)P+Ppub,V)·(PKS)-h3=R1. If the tuple passes the verification, then B returns M in this tuple to AI. If no such tuple is found, σ is rejected. Note that a valid ciphertext is rejected with probability smaller than qdsc/2k across the whole game.
In the challenge phase,AI outputs (M0,M1,idS*,idR*), on which it wants to be challenged. If (idR*,PKR*)≠(idθ,PKθ), then B aborts. Otherwise, B randomly chooses C*∈{0,1}n, r*∈Zp*, and V*∈G, computes U*=r*P, and returns σ*=(C*,U*,V*) to AI as the challenge ciphertext. Observe that the decryption of C* is C*⊕H2(e(U*,Certθ), e(U*,Certθ)SKθ).
In the guess phase,AI outputs a bit which is ignored by B. Note that AI cannot recognize that σ* is not a valid ciphertext unless it queries H2 on (e(U*,Certθ), e(U*,Certθ)SKθ) or H3 on (Mb,U*,(e(U*,Certθ),e(U*,Certθ)SKθ),idS*,PKS*,idθ,PKθ), where b∈{0,1}. Standard arguments can show that a successful AI is very likely to query H2 on (e(U*,Certθ), e(U*,Certθ)SKθ) or H3 on (Mb,U*,(e(U*,Certθ),e(U*,Certθ)SKθ),idS*,PKS*,idθ,PKθ) if the simulation is indistinguishable from a real attack environment. To produce a result, B picks a random tuple 〈R1,R2,h2〉 or 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉 fromH2List orH3List. With probability 1/(q2+2q3+2qsc) (asH2List,H3List contain at most q2+q3+qsc,q3+qsc tuples, resp.), the chosen tuple will contain the value R1=e(U*,Certθ). Because e(U*,Certθ)=e(r*P,t(ω*+α)-1P)=e(P,P)tr*(ω*+α)-1, B returns T=R1(tr*)-1as the solution to the given q-mBDHI problem.
We now deriveB’s advantage in solving the q-mBDHI problem. From the above construction, the simulation fails if any of the following events occurs: (1) E1: in the challenge phase, B aborts because (idR*,PKR*)≠(idθ,PKθ); (2)E2: AI makes an OGenerateCertificate query on (idθ,PKθ); (3)E3: B aborts in answer one of AI’s OSigncryption queries because of a collision on H2 or H3; (4)E4: B rejects a valid ciphertext at some point of the game.
We clearly have thatPr[¬E1]=1/q1 and ¬E1 implies ¬E2. We also already observed that Pr[E3]≤(q2+2q3+2qsc)/2k and Pr[E4]≤qdsc/2k. Thus, we have that
(4)Pr[¬E1∧¬E2∧¬E3∧¬E4]≥1q1(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).
SinceB selects the correct tuple fromH2List orH3List with probability 1/(q2+2q3+2qsc), we obtain the announced bound on B’s advantage in solving the q-mBDHI problem.Lemma 12.
If a Type II adversaryAII has advantage ε against our CBSC scheme when asking at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3, then there exists an algorithm B to solve the BDH problem with advantage
(5)ε′≥εqcu(q2+2q3+2qsc)(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).Proof.
Assume thatB is given a BDH instance (P,aP,bP,cP), where a,b,c are three random elements from Zp*. B interacts with AII as follows.
In the setup phase,B randomly chooses α∈Zp*, sets Q=aP, and computes Ppub=αP and g=e(P,Q). Furthermore, it randomly chooses an index θ with 1≤θ≤qcu. Then, B startsIND-CBSC-CCA2 Game-II by supplying AII with msk=α and params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B. AII can make queries on these random oracles at any time during the game.
Now,B starts to respond various queries as follows.
H
1
Queries. B maintains a listH1List of tuples 〈idi,PKi,h1,i〉. On input (idi,PKi), B does the following: if (idi,PKi) already appears onH1List in a tuple 〈idi,PKi,h1,i〉, then B returns h1,i to AII; otherwise, it returns a random h1,i∈Zp* and inserts 〈idi,PKi,h1,i〉 intoH1List.
H
2
Queries. B responds as in the proof of Lemma 11.
H
3
Queries. B responds as in the proof of Lemma 11.
O
C
r
e
a
t
e
U
s
e
r
Queries. B maintains a list` of tuples 〈idi,PKi,SKi〉. On input (idi), B does the following: (1) if idi already appears onKeyList in a tuple 〈idi,PKi,SKi〉, B returns PKi to AII. (2) Else if idi=idθ, B returns PKθ=e(bP,Q)=e(bP,aP) to AII and inserts 〈idθ,PKθ,⊥〉 intoKeyList. Note that the private key for the identity idθ is b which is unknown to B. (3) Else B randomly chooses xi∈Zp* as the private key SKi for the identity idi and computes the corresponding public key as PKi=gxi. It then inserts 〈idi,PKi,SKi〉 intoKeyList and returns PKi to AII.
O
E
x
t
r
a
c
t
P
r
i
v
a
t
e
K
e
y
Queries. On receiving such a query on idi, B does the following: if idi=idθ, then B aborts; otherwise, B searches idi inKeyList to find the tuple 〈idi,PKi,SKi〉 and returns SKi to AII.
O
S
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (M,idS,idR), B does the following: if idS≠idθ, B can answer the query according to the specification of theSigncrypt algorithm since it knows the sender idS’s private key and certificate. Otherwise, B randomly chooses r,h3∈Zp*, h2∈{0,1}n and computes U=r(H1(idθ,PKθ)P+Ppub)−h3(H1(idR,PKR)bP+αbP), V=rCertR, C=M⊕h2, R1=e(U,CertR), and R2=e(U,CertR)SKR, respectively. It is easy to verify that e(H1(idθ,PKθ)P+Ppub,V)·(PKθ)-h3=e(U,CertR). It then inserts 〈R1,R2,h2〉 and 〈M,U,R1,R2,idθ,PKθ,idR,PKR,h3,C〉 intoH2List andH3List, respectively, and returns the ciphertext σ=(C,U,V) to AII. Note that B fails ifH2List orH3List is already defined in the corresponding value, but this only happens with probability smaller than (q2+2q3+2qsc)/2k.
O
D
e
s
i
g
n
c
r
y
p
t
i
o
n
Queries. B responds as in the proof of Lemma 11.
In the challenge phase,AII outputs (M0,M1,idS*,idR*), on which it wants to be challenged. If idR*≠idθ, then B aborts. Otherwise, B randomly chooses C*∈{0,1}n, V*∈G, computes U*=(H1(idθ,PKθ)+α)cP, and returns σ*=(C*,U*,V*) to AII as the challenge ciphertext. Observe that the decryption of C* is C*⊕H2(e(U*,Certθ),e(U*,Certθ)SKθ).
In the guess phase,AII outputs a bit, which is ignored by B. Note that AII cannot recognize that σ* is not a valid ciphertext unless it queries H2 on (e(U*,Certθ),e(U*,Certθ)SKθ) or H3 on (Mβ,U*,e(U*,Certθ),e(U*,Certθ)SKθ,idS*,PKS*,idθ,PKθ), where β∈{0,1}. Standard arguments can show that a successful AII is very likely to query H2 on (e(U*,Certθ),e(U*,Certθ)SKθ) or H3 on (Mβ,U*,e(U*,Certθ),e(U*,Certθ)SKθ,idS*,PKS*,idθ,PKθ) if the simulation is indistinguishable from a real attack environment. To produce a result, B picks a random tuple 〈R1,R2,h2〉 or 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉 fromH2List orH3List. With probability 1/(q2+2q3+2qsc) (asH2List,H3List contain at most q2+q3+qsc, q3+qsc tuples, resp.), the chosen tuple will contain the right element R2=e(U*,Certθ)SKθ=e(P,P)abc. B then returns R2 as the solution to the given BDH problem.
We now deriveB’s advantage in solving the BDH problem. From the above construction, the simulation fails if any of the following events occurs: (1)E1: in the challenge phase, B aborts because idR*≠idθ; (2)E2: AII makes an OExtractPrivateKey query on idθ; (3)E3: B aborts in answer AII’s OSigncryption query because of a collision on H2 or H3; (4)E4: B rejects a valid ciphertext at some point of the game.
We clearly have thatPr[¬E1]=1/qcu and ¬E1 implies ¬E2. We also already observed that Pr[E3]≤(q2+2q3+2qsc)/2k and Pr[E4]≤qdsc/2k. Thus, we have that
(6)Pr[¬E1∧¬E2∧¬E3∧¬E4]≥1qcu(1-qscq2+2q3+2qsc2k)(1-qdsc2k).
SinceB selects the correct tuple fromH2List orH3List with probability 1/(q2+2q3+2qsc), we obtain the announced bound on B’s advantage in solving the BDH problem.Theorem 13.
The CBSC scheme above is EUF-CBSC-CMA secure under the hardness of the q-CAA and CDH problems in the random oracle model.This theorem can be proved by combining the following two lemmas.Lemma 14.
If a Type I adversaryAI asks at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3 and produces a valid forgery with probability ε≥10(qsc+1)(qsc+q3)/2k, then there exists an algorithm B to solve the (q1-1)-CAA problem with advantage ε′≥1/(9q1).Proof.
Assume thatB is given a q-CAA instance (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq), where q=q1-1. B interacts with AI as follows.
In the setup phase,B randomly chooses t∈Zp*, sets Ppub=αP, and computes Q=tP and g=e(P,Q). Furthermore, it randomly chooses a value ω*∈Zp* such that ω*∉{ω1,…,ωq} and an index θ∈[1,q1]. Then, B startsEUF-CBSC-CMA Game-I by supplying AI with params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B. Note that the corresponding master key is msk=α which is unknown to B.
In the query phase,B responds to various oracle queries as in the proof of Lemma 11.
Finally, in the forge phaseAI outputs a valid forgery (σ*=(C*,U*,V*),idS*,idR*) with probability ε≥10(qsc+1)(qsc+q3)/2k [29]. If (idS*,PKS*)≠(idθ,PKθ), B aborts. Otherwise, having the knowledge of SKR* and CertR*, B runs the algorithm Designcrypt(params, σ*, idR*, PKR*, SKR*, CertR*, idθ, PKθ) to obtain the message M* and then simulates the random oracle H3 on its own to obtain h3*=H3(M*,U*,e(U*,CertR*),e(U*,CertR*)SKR*,idθ,PKθ,idR*,PKR*). Using the oracle replay technique [29], B replays AI with the same random tape but with the different hash value h3*′(≠h3*) to generate one more valid ciphertext σ*′=(C*,U*,V*′) such that V*′≠V*. Since σ*=(C*,U*,V*) and σ*′=(C*,U*,V*′) are both valid ciphertexts for the same message M* and the randomness r*, we obtain the following relations:
(7)V*-V*′=(h3*SKθ+r*)Certθ-(h3*′SKθ+r*)Certθ=(h3*-h3*′)SKθCertθ.
BecauseCertθ=t(ω*+α)-1P, B can compute (ω*+α)-1P=[t(h3*-h3*′)SKθ]-1(V*-V*′) as the solution to the given q-CAA problem.
We now deriveB’s advantage in solving the q-CAA problem. From the above construction, the simulation fails after AI outputs a valid forgery if any of the following events occurs: (1)E1: in the forge phase, B aborts because (idS*,PKS*)≠(idθ,PKθ); (2)E2: B fails in using the oracle replay technique to generate one more valid ciphertext.
Clearly,Pr[¬E1]=1/q1. Moreover, from the forking lemma [29], we know that Pr[¬E2]≥1/9. Thus, we have that if AI produces a forgery, then B will succeed in solving the q-CAA problem with probability ε′=Pr[¬E1∧¬E2]≥1/(9q1).Lemma 15.
If a Type II adversaryAII asks at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to  ODesigncryption, and qi queries to random oracles H1~H3 and produces a valid forgery with probability ε≥10(qsc+1)(qsc+q3)/2k, then there exists an algorithm B to solve the CDH problem with advantage ε′≥1/(9qcu).Proof.
Assume thatB is given a random CDH instance (P,aP,bP) where a,b are two random elements from Zp*. B interacts with AII as follows.
In the setup phase,B randomly chooses α∈Zp*, sets Q=aP, and computes Ppub=αP and g=e(P,Q). Furthermore, it randomly chooses an index θ with 1≤θ≤qcu. Then, B startsEUF-CBSC-CMA Game-II by supplying AII with msk=α and params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B.
In the query phase,B responds to various oracle queries as in the proof of Lemma 12.
Finally, in the forge phaseAI outputs a valid forgery (σ*=(C*,U*,V*),idS*,idR*) with probability ε≥10(qsc+1)(qsc+q3)/2k [29]. If idS*≠idθ, then B aborts. Otherwise, having the knowledge of SKR* and CertR*, B runs the algorithm Designcrypt(params,σ*,idR*,PKR*,SKR*,CertR*,idθ,PKθ) to obtain the message M* and then simulates the random oracle H3 on its own to obtain h3*=H3(M*,U*,e(U*,CertR*),e(U*,CertR*)SKR*, idθ,PKθ,idR*,PKR*). Using the oracle replay technique [29], B replays AII with the same random tape but with the different hash value h3*′(≠h3*) to generate one more valid ciphertext σ*′=(C*,U*,V*′) such that V*′≠V*. Since σ*=(C*,U*,V*) and σ*′=(C*,U*,V*′) are both valid ciphertexts for the same message M* and randomness r*, we obtain the following relations:
(8)V*-V*′=(h3*SKθ+r*)Certθ-(h3*′SKθ+r*)Certθ=(h3*-h3*′)SKθ(H1(idθ,PKθ)+α)-1Q.
Then, we have the following relations:(9)e(H1(idθ,PKθ)P+αP,V*-V*′)=e(P,(h3*-h3*′)SKθQ).
BecauseQ=aP and SKθ=b, B can compute abP=SKθQ=(h3*-h3*′)-1(H1(idθ,PKθ)+α)(V*-V*′) as the solution to the given CDH problem.
We now deriveB’s advantage in solving the CDH problem. From the above construction, the simulation fails if any of the following events occurs: (1)E1: in the forge phase, B aborts because idS*≠idθ; (2)E2: B fails in using the oracle replay technique to generate one more valid ciphertext. Clearly, Pr[¬E1]=1/qcu. From the forking lemma [29], we know that Pr[¬E2]≥1/9. Thus, we have that if AII produces a valid forgery, then B will succeed in solving the CDH problem with probability ε′=Pr[¬E1∧¬E2]≥1/(9qcu).


### 5.3. Performance

To evaluate the performance of our new CBSC scheme, we compare our scheme with the previous CBSC schemes in terms of the computational cost and the communicational cost.In the computational cost comparison, we consider four major operations: pairing, exponentiation inGT, scalar multiplication in G, and hash. Among these operations, the pairing is considered as the heaviest time-consuming one in spite of the recent advances in the implementation technique. For simplicity, we denote these operations by p,e,m, and h, respectively. In the communicational cost comparison, ciphertext overhead represents the difference (in bits) between the ciphertext length and the message length, |id| denotes the bit-length of user’s identity, and |G| and |Zp| denote the bit-length of an element in G and Zp, respectively. Without considering precomputation, the performances of the compared CBSC schemes are listed in Table 2.Table 2
Performance of the CBSC schemes.
Schemes
Signcryption cost
Designcryption cost
Ciphertext overhead
Ours
2
e
+
3
m
+
3
h
2
p
+
2
e
+
1
m
+
3
h
2
|
G
|
[18]
1
p
+
1
e
+
4
m
+
3
h
3
p
+
1
e
+
1
m
+
3
h
2
|
G
|
[20]
1
p
+
5
m
+
4
h
4
p
+
2
m
+
3
h
3
|
G
|
+
|
id
|
[21]
2
p
+
4
e
+
3
m
+
3
h
3
p
+
4
e
+
3
h
2
|
G
|
+
2
|
Z
p
|The efficiency of a pairing-based cryptosystem always depends on the chosen curve. Boyen [30] computes estimated relative timings for all atomic asymmetric operations (exponentiations and pairings) and representation sizes for group elements when instantiated in supersingular curves with 80-bit security (SS/80) and MNT curves with 80-bit security (MNT/80). In Table 3, we recall the data from [30].Table 3
Timings needed to perform atomic operations and representation of group elements in bits.
Curves
Relative timings(1 unit = 1 scalar multiplication in G)
Representation  sizes (bits)
m
e
p
|
G
|
|
G
T
|
MNT/80
1
36
150
171
1026
SS/80
1
4
20
512
1024To make a much clearer comparison, Table4 gives the concrete values of the computational cost and the communicational cost for the compared CBE schemes according to the data in Table 3. As the hash operation is much more efficient than the multiplication in the group G, the costs of the hash operations are ignored.Table 4
Performance comparison of the CBSC schemes.
Schemes
Signcryption cost
Designcryption cost
Ciphertext overhead
MNT/80
Ours
75
373
342
[18]
187
487
342
[20]
155
602
513
+
|
id
|
[21]
447
594
2390
SS/80
Ours
11
49
1024
[18]
28
65
1024
[20]
25
82
1536
+
|
id
|
[21]
59
76
3072In our proposed CBSC scheme, theSigncrypt algorithm does not require computing any time-consuming pairings. It only needs to compute two exponentiations in GT, three scalar multiplications in G and three hashes in each signcryption operation. TheDesigncrypt algorithm needs to compute two pairings, two exponentiations in GT, one scalar multiplication in G, and three hashes to designcrypt a ciphertext. From Tables 2 and 4, we can see that our scheme is more efficient than the previous CBSC scheme, especially in the computational efficiency. Actually, the computational performance of our scheme can be further optimized when H1(idU,PKU)P+Ppub can be precomputed. Such a precomputation enables us to additionally reduce one scalar multiplication computation in G and one hash computation in both theSigncrypt algorithm and theDesigncrypt algorithm. In addition and most importantly, it is believed that our scheme is the first signcryption scheme in the certificate-based cryptographic setting that achieves security against both the public key replacement attacks and the insider attacks.


## 5.1. Description of the Scheme

Our CBSC scheme is constructed from the certificate-based encryption scheme proposed by Lu et al. [8]. It consists of the following five algorithms.(i)
Setup(k): given a security parameter k, the certifier performs the following: generate two cyclic groups G and GT of a k-bit prime order p such that there exists a bilinear pairing map e:G×G→GT; choose two random generators P, Q∈G and compute g=e(P,Q); choose a random element α∈Zp* and set Ppub=αP; select three hash functions H1:{0,1}*×GT→Zp*, H2:GT×GT→{0,1}n and H3:{0,1}*→Zp*, where n is the bit-length of the message to be signcrypted; set the public parameters params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3} and the master key msk=α.(ii)
UserKeyGen(params): given params, a user with identity idU∈{0,1}* chooses a random xU∈Zp* as his private key SKU and then computes his public key PKU=gxU.(iii)
CertGen(params,msk,idU,PKU): to generate a certificate for a user with identity idU and public key PKU, the certifier computes CertU=(H1(idU,PKU)+α)-1Q. The user idU can check the validness of the certificate CertU by verifying whether e(H1(idU,PKU)P+Ppub,CertU)=g.(iv)
Signcrypt(params,M,idS,PKS,SKS,CertS,idR,PKR): to send a message M∈{0,1}n to the receiver idR, the sender idS does the following: randomly choose r∈Zp* and compute R1=gr and R2=(PKR)r; compute U=r(H1(idR,PKR)P+Ppub) and C=M⊕H2(R1,R2); compute V=(h·SKS+r)·CertS, where h=H3(M,U,R1,R2,idS,PKS,idR,PKR); set the ciphertext σ=(C,U,V).(v)
Designcrypt(params,σ,idR,PKR,SKR,CertR,idS,PKS): to designcrypt a ciphertext σ=(C,U,V) from the sender idS, the receiver idR does the following: compute R1=e(U,CertR) and R2=e(U,CertR)SKR; compute M=C⊕H2(R1,R2) and then check whether e(H1(idS,PKS)P+Ppub,V)(PKS)-h=R1, where h=H3(M,U,R1,R2,idS,PKS,idR,PKR). If the check holds, output M; otherwise, output ⊥.The consistency of our scheme can be easily verified by the following equalities:(1)
e(U,CertR)=e(r(H1(idR,PKR)P+Ppub), (H1(idR,PKR)+α)-1Q)=e(P,Q)r=gr;(2)
e(U,CertR)SKR=(gr)SKR=(PKR)r;(3)
(2)e(H1(idS,PKS)P+Ppub,V)(PKS)-h=e((H1(idS,PKS)+α)-1P,(h·SKS+r)·CertS)·(PKS)-h=e(P,(h·SKS+r)Q)·(PKS)-h=e(P,Q)r=R1.


## 5.2. Security Proof

Theorem 10.
The CBSC scheme above is IND-CBSC-CCA2 secure under the hardness of the q-mBDHI and BDH problems in the random oracle model.This theorem can be proved by combining the following two lemmas.Lemma 11.
If a Type I adversaryAI has advantage ε against our CBSC scheme when asking at most qcu to OCreateUser queries, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3, then there exists an algorithm B to solve the (q1-1)-mBDHI problem with advantage
(3)ε′≥εq1(q2+2q3+2qsc)(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).Proof.
Assume thatB is given a random q-mBDHI instance (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq), where q=q1-1. B interacts with AI as follows.
In the setup phase,B randomly chooses t∈Zp* and sets Ppub=αP, Q=tP, and g=e(P,Q). Furthermore, it randomly chooses a value ω*∈Zp* such that ω*∉{ω1,…,ωq} and an index θ∈[1,q1]. Then, B startsIND-CBSC-CCA2 Game-I by supplying AI with params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B.  AI can make queries on these random oracles at any time during the game. Note that the corresponding master key is msk=α which is unknown to B.
Now,B starts to respond to various queries as follows:
H
1
Queries. We assume that q1 queries to H1 are distinct. B maintains a listH1List of tuples 〈idi,PKi,h1,i,Certi〉. On input (idi,PKi), B does the following.(1)
If (idi, PKi) already appears onH1List in a tuple 〈idi,PKi,h1,i,Certi〉, then B returns h1,i to AI.(2)
Else if the query is on theθth distinct (idθ, PKθ), then B inserts 〈idθ,PKθ,ω*,⊥〉 intoH1List and returns h1,θ=ω* to AI. Note that the certificate for the identity idθ is Certθ=t(ω*+α)-1P which is unknown to B.(3)
ElseB sets h1,i to be ωj(j∈[1,q]) which has not been used and computes Certi=t(ωj+α)-1P. It then inserts 〈idi,PKi,h1,i,Certi〉 intoH1List and returns h1,i.
H
2
Queries.
B maintains a listH2Listof tuples 〈R1,R2,h2〉. On input (R1, R2), B does the following. (1)
If (R1, R2) already appears onH2List in a tuple 〈R1,R2,h2〉, B returns h2 to AI.(2)
Otherwise, it returns a randomh2∈{0,1}n and inserts 〈R1,R2,h2〉 intoH2List.
H
3
Queries. B maintains a listH3List of tuples 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉. On input (M,U,R1,R2,idS,PKS,idR,PKR), B does the following. (1)
If(M,U,R1,R2,idS,PKS,idR,PKR) already appears onH3List in a tuple 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉, B returns h3 to AI.(2)
Otherwise, it returns a randomh3∈Zp* to AI. To anticipate possible subsequent queries to ODesigncryption, it additionally simulates the random oracle H2 on its own to obtain h2=H2(R1,R2) and then inserts 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C=M⊕h2〉 intoH3List.
O
C
r
e
a
t
e
U
s
e
r
Queries. B maintains a listKeyList of tuples 〈idi,PKi,SKi,flagi〉 which is initially empty. On input (idi), B does the following. (1)
Ifidi already appears onKeyList in a tuple 〈idi,PKi,SKi,flagi〉, B returns PKi to AI directly.(2)
Otherwise,B randomly chooses xi∈Zp* as the private key SKi for the identity idi and computes the corresponding public key as PKi=gxi. It then inserts 〈idi,PKi,SKi,0〉 intoKeyList and returns PKi to AI.
O
R
e
p
l
a
c
e
P
u
b
l
i
c
K
e
y
r
Queries. On input (idi,PKi′), B searches idi inKeyList to find a tuple 〈idi,PKi,SKi,flagi〉 and updates the tuple with 〈idi,PKi′,SKi,1〉.
O
E
x
t
r
a
c
t
P
r
i
v
a
t
e
K
e
y
Queries. On input (idi), B searches idi inKeyList to find a tuple 〈idi,PKi,SKi,flagi〉. If flagi=0, it returns SKi to AI; otherwise, it rejects this query.
O
G
e
n
e
r
a
t
e
C
e
r
t
i
f
i
c
a
t
e
Queries. On input (idi), B does the following. (1)
If (idi, PKi) = (idθ, PKθ), then B aborts.(2)
Otherwise,B searches idi inH1List to find a tuple 〈idi,PKi,h1,i,Certi〉 and then returns Certi to AI. IfH1List does not contain such a tuple, B queries H1 on (idi, PKi) first.
O
S
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (M, idS, idR), B performs as follows.(1)
If(idS,PKS)≠(idθ,PKθ), B can answer the query according to the specification of the algorithmSigncrypt since it knows the sender idS’s private key and certificate.(2)
Otherwise,B randomly chooses r, h3∈Zp*, h2∈{0,1}n and sets U=r(H1(idθ,PKθ)P+Ppub)-h3SKθ(H1(idR,PKR)P+Ppub), V=rCertR, C=M⊕h2, R1=e(U,CertR), and R2=e(U,CertR)SKR, respectively. It is easy to verify that e(H1(idθ,PKθ)P+Ppub,V)·(PKθ)-h3=e(U,CertR). Then, B inserts 〈R1,R2,h2〉 and 〈M,U,R1,R2,idθ,PKθ,idR,PKR,h3,C〉 intoH2List andH3List,respectively, and returns the ciphertext σ=(C,U,V) to AI. Note that B fails ifH2List orH3List is already defined in the corresponding value, but this only happens with probability smaller than (q2+2q3+2qsc)/2k.
O
D
e
s
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (σ=(C,U,V), idS, idR), B does the following.(1)
If(idR,PKR)≠(idθ,PKθ), B can answer the query according to the specification of the algorithmDesigncrypt since it knows the receiver idR’s private key and certificate.(2)
Otherwise,B searches inH3List for all tuples of the form 〈M,U,R1,R2,idS,PKS,idθ,PKθ,h3,C〉. If no such tuple is found, then σ is rejected. Otherwise, each one of them is further examined. For a tuple 〈M,U,R1,R2,idS,PKS,idθ,PKθ,h3,C〉, B first checks whether e(H1(idS,PKS)P+Ppub,V)·(PKS)-h3=R1. If the tuple passes the verification, then B returns M in this tuple to AI. If no such tuple is found, σ is rejected. Note that a valid ciphertext is rejected with probability smaller than qdsc/2k across the whole game.
In the challenge phase,AI outputs (M0,M1,idS*,idR*), on which it wants to be challenged. If (idR*,PKR*)≠(idθ,PKθ), then B aborts. Otherwise, B randomly chooses C*∈{0,1}n, r*∈Zp*, and V*∈G, computes U*=r*P, and returns σ*=(C*,U*,V*) to AI as the challenge ciphertext. Observe that the decryption of C* is C*⊕H2(e(U*,Certθ), e(U*,Certθ)SKθ).
In the guess phase,AI outputs a bit which is ignored by B. Note that AI cannot recognize that σ* is not a valid ciphertext unless it queries H2 on (e(U*,Certθ), e(U*,Certθ)SKθ) or H3 on (Mb,U*,(e(U*,Certθ),e(U*,Certθ)SKθ),idS*,PKS*,idθ,PKθ), where b∈{0,1}. Standard arguments can show that a successful AI is very likely to query H2 on (e(U*,Certθ), e(U*,Certθ)SKθ) or H3 on (Mb,U*,(e(U*,Certθ),e(U*,Certθ)SKθ),idS*,PKS*,idθ,PKθ) if the simulation is indistinguishable from a real attack environment. To produce a result, B picks a random tuple 〈R1,R2,h2〉 or 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉 fromH2List orH3List. With probability 1/(q2+2q3+2qsc) (asH2List,H3List contain at most q2+q3+qsc,q3+qsc tuples, resp.), the chosen tuple will contain the value R1=e(U*,Certθ). Because e(U*,Certθ)=e(r*P,t(ω*+α)-1P)=e(P,P)tr*(ω*+α)-1, B returns T=R1(tr*)-1as the solution to the given q-mBDHI problem.
We now deriveB’s advantage in solving the q-mBDHI problem. From the above construction, the simulation fails if any of the following events occurs: (1) E1: in the challenge phase, B aborts because (idR*,PKR*)≠(idθ,PKθ); (2)E2: AI makes an OGenerateCertificate query on (idθ,PKθ); (3)E3: B aborts in answer one of AI’s OSigncryption queries because of a collision on H2 or H3; (4)E4: B rejects a valid ciphertext at some point of the game.
We clearly have thatPr[¬E1]=1/q1 and ¬E1 implies ¬E2. We also already observed that Pr[E3]≤(q2+2q3+2qsc)/2k and Pr[E4]≤qdsc/2k. Thus, we have that
(4)Pr[¬E1∧¬E2∧¬E3∧¬E4]≥1q1(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).
SinceB selects the correct tuple fromH2List orH3List with probability 1/(q2+2q3+2qsc), we obtain the announced bound on B’s advantage in solving the q-mBDHI problem.Lemma 12.
If a Type II adversaryAII has advantage ε against our CBSC scheme when asking at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3, then there exists an algorithm B to solve the BDH problem with advantage
(5)ε′≥εqcu(q2+2q3+2qsc)(1-qscq2+2q3+2qsc2k)×(1-qdsc2k).Proof.
Assume thatB is given a BDH instance (P,aP,bP,cP), where a,b,c are three random elements from Zp*. B interacts with AII as follows.
In the setup phase,B randomly chooses α∈Zp*, sets Q=aP, and computes Ppub=αP and g=e(P,Q). Furthermore, it randomly chooses an index θ with 1≤θ≤qcu. Then, B startsIND-CBSC-CCA2 Game-II by supplying AII with msk=α and params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B. AII can make queries on these random oracles at any time during the game.
Now,B starts to respond various queries as follows.
H
1
Queries. B maintains a listH1List of tuples 〈idi,PKi,h1,i〉. On input (idi,PKi), B does the following: if (idi,PKi) already appears onH1List in a tuple 〈idi,PKi,h1,i〉, then B returns h1,i to AII; otherwise, it returns a random h1,i∈Zp* and inserts 〈idi,PKi,h1,i〉 intoH1List.
H
2
Queries. B responds as in the proof of Lemma 11.
H
3
Queries. B responds as in the proof of Lemma 11.
O
C
r
e
a
t
e
U
s
e
r
Queries. B maintains a list` of tuples 〈idi,PKi,SKi〉. On input (idi), B does the following: (1) if idi already appears onKeyList in a tuple 〈idi,PKi,SKi〉, B returns PKi to AII. (2) Else if idi=idθ, B returns PKθ=e(bP,Q)=e(bP,aP) to AII and inserts 〈idθ,PKθ,⊥〉 intoKeyList. Note that the private key for the identity idθ is b which is unknown to B. (3) Else B randomly chooses xi∈Zp* as the private key SKi for the identity idi and computes the corresponding public key as PKi=gxi. It then inserts 〈idi,PKi,SKi〉 intoKeyList and returns PKi to AII.
O
E
x
t
r
a
c
t
P
r
i
v
a
t
e
K
e
y
Queries. On receiving such a query on idi, B does the following: if idi=idθ, then B aborts; otherwise, B searches idi inKeyList to find the tuple 〈idi,PKi,SKi〉 and returns SKi to AII.
O
S
i
g
n
c
r
y
p
t
i
o
n
Queries. On input (M,idS,idR), B does the following: if idS≠idθ, B can answer the query according to the specification of theSigncrypt algorithm since it knows the sender idS’s private key and certificate. Otherwise, B randomly chooses r,h3∈Zp*, h2∈{0,1}n and computes U=r(H1(idθ,PKθ)P+Ppub)−h3(H1(idR,PKR)bP+αbP), V=rCertR, C=M⊕h2, R1=e(U,CertR), and R2=e(U,CertR)SKR, respectively. It is easy to verify that e(H1(idθ,PKθ)P+Ppub,V)·(PKθ)-h3=e(U,CertR). It then inserts 〈R1,R2,h2〉 and 〈M,U,R1,R2,idθ,PKθ,idR,PKR,h3,C〉 intoH2List andH3List, respectively, and returns the ciphertext σ=(C,U,V) to AII. Note that B fails ifH2List orH3List is already defined in the corresponding value, but this only happens with probability smaller than (q2+2q3+2qsc)/2k.
O
D
e
s
i
g
n
c
r
y
p
t
i
o
n
Queries. B responds as in the proof of Lemma 11.
In the challenge phase,AII outputs (M0,M1,idS*,idR*), on which it wants to be challenged. If idR*≠idθ, then B aborts. Otherwise, B randomly chooses C*∈{0,1}n, V*∈G, computes U*=(H1(idθ,PKθ)+α)cP, and returns σ*=(C*,U*,V*) to AII as the challenge ciphertext. Observe that the decryption of C* is C*⊕H2(e(U*,Certθ),e(U*,Certθ)SKθ).
In the guess phase,AII outputs a bit, which is ignored by B. Note that AII cannot recognize that σ* is not a valid ciphertext unless it queries H2 on (e(U*,Certθ),e(U*,Certθ)SKθ) or H3 on (Mβ,U*,e(U*,Certθ),e(U*,Certθ)SKθ,idS*,PKS*,idθ,PKθ), where β∈{0,1}. Standard arguments can show that a successful AII is very likely to query H2 on (e(U*,Certθ),e(U*,Certθ)SKθ) or H3 on (Mβ,U*,e(U*,Certθ),e(U*,Certθ)SKθ,idS*,PKS*,idθ,PKθ) if the simulation is indistinguishable from a real attack environment. To produce a result, B picks a random tuple 〈R1,R2,h2〉 or 〈M,U,R1,R2,idS,PKS,idR,PKR,h3,C〉 fromH2List orH3List. With probability 1/(q2+2q3+2qsc) (asH2List,H3List contain at most q2+q3+qsc, q3+qsc tuples, resp.), the chosen tuple will contain the right element R2=e(U*,Certθ)SKθ=e(P,P)abc. B then returns R2 as the solution to the given BDH problem.
We now deriveB’s advantage in solving the BDH problem. From the above construction, the simulation fails if any of the following events occurs: (1)E1: in the challenge phase, B aborts because idR*≠idθ; (2)E2: AII makes an OExtractPrivateKey query on idθ; (3)E3: B aborts in answer AII’s OSigncryption query because of a collision on H2 or H3; (4)E4: B rejects a valid ciphertext at some point of the game.
We clearly have thatPr[¬E1]=1/qcu and ¬E1 implies ¬E2. We also already observed that Pr[E3]≤(q2+2q3+2qsc)/2k and Pr[E4]≤qdsc/2k. Thus, we have that
(6)Pr[¬E1∧¬E2∧¬E3∧¬E4]≥1qcu(1-qscq2+2q3+2qsc2k)(1-qdsc2k).
SinceB selects the correct tuple fromH2List orH3List with probability 1/(q2+2q3+2qsc), we obtain the announced bound on B’s advantage in solving the BDH problem.Theorem 13.
The CBSC scheme above is EUF-CBSC-CMA secure under the hardness of the q-CAA and CDH problems in the random oracle model.This theorem can be proved by combining the following two lemmas.Lemma 14.
If a Type I adversaryAI asks at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to ODesigncryption, and qi queries to random oracles H1~H3 and produces a valid forgery with probability ε≥10(qsc+1)(qsc+q3)/2k, then there exists an algorithm B to solve the (q1-1)-CAA problem with advantage ε′≥1/(9q1).Proof.
Assume thatB is given a q-CAA instance (P,αP,(ω1+α)-1P,…,(ωq+α)-1P,ω1,…,ωq), where q=q1-1. B interacts with AI as follows.
In the setup phase,B randomly chooses t∈Zp*, sets Ppub=αP, and computes Q=tP and g=e(P,Q). Furthermore, it randomly chooses a value ω*∈Zp* such that ω*∉{ω1,…,ωq} and an index θ∈[1,q1]. Then, B startsEUF-CBSC-CMA Game-I by supplying AI with params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B. Note that the corresponding master key is msk=α which is unknown to B.
In the query phase,B responds to various oracle queries as in the proof of Lemma 11.
Finally, in the forge phaseAI outputs a valid forgery (σ*=(C*,U*,V*),idS*,idR*) with probability ε≥10(qsc+1)(qsc+q3)/2k [29]. If (idS*,PKS*)≠(idθ,PKθ), B aborts. Otherwise, having the knowledge of SKR* and CertR*, B runs the algorithm Designcrypt(params, σ*, idR*, PKR*, SKR*, CertR*, idθ, PKθ) to obtain the message M* and then simulates the random oracle H3 on its own to obtain h3*=H3(M*,U*,e(U*,CertR*),e(U*,CertR*)SKR*,idθ,PKθ,idR*,PKR*). Using the oracle replay technique [29], B replays AI with the same random tape but with the different hash value h3*′(≠h3*) to generate one more valid ciphertext σ*′=(C*,U*,V*′) such that V*′≠V*. Since σ*=(C*,U*,V*) and σ*′=(C*,U*,V*′) are both valid ciphertexts for the same message M* and the randomness r*, we obtain the following relations:
(7)V*-V*′=(h3*SKθ+r*)Certθ-(h3*′SKθ+r*)Certθ=(h3*-h3*′)SKθCertθ.
BecauseCertθ=t(ω*+α)-1P, B can compute (ω*+α)-1P=[t(h3*-h3*′)SKθ]-1(V*-V*′) as the solution to the given q-CAA problem.
We now deriveB’s advantage in solving the q-CAA problem. From the above construction, the simulation fails after AI outputs a valid forgery if any of the following events occurs: (1)E1: in the forge phase, B aborts because (idS*,PKS*)≠(idθ,PKθ); (2)E2: B fails in using the oracle replay technique to generate one more valid ciphertext.
Clearly,Pr[¬E1]=1/q1. Moreover, from the forking lemma [29], we know that Pr[¬E2]≥1/9. Thus, we have that if AI produces a forgery, then B will succeed in solving the q-CAA problem with probability ε′=Pr[¬E1∧¬E2]≥1/(9q1).Lemma 15.
If a Type II adversaryAII asks at most qcu queries to OCreateUser, qsc queries to OSigncryption, qdsc queries to  ODesigncryption, and qi queries to random oracles H1~H3 and produces a valid forgery with probability ε≥10(qsc+1)(qsc+q3)/2k, then there exists an algorithm B to solve the CDH problem with advantage ε′≥1/(9qcu).Proof.
Assume thatB is given a random CDH instance (P,aP,bP) where a,b are two random elements from Zp*. B interacts with AII as follows.
In the setup phase,B randomly chooses α∈Zp*, sets Q=aP, and computes Ppub=αP and g=e(P,Q). Furthermore, it randomly chooses an index θ with 1≤θ≤qcu. Then, B startsEUF-CBSC-CMA Game-II by supplying AII with msk=α and params={p,G,GT,e,n,P,Q,Ppub,g,H1,H2,H3}, where H1~H3 are random oracles controlled by B.
In the query phase,B responds to various oracle queries as in the proof of Lemma 12.
Finally, in the forge phaseAI outputs a valid forgery (σ*=(C*,U*,V*),idS*,idR*) with probability ε≥10(qsc+1)(qsc+q3)/2k [29]. If idS*≠idθ, then B aborts. Otherwise, having the knowledge of SKR* and CertR*, B runs the algorithm Designcrypt(params,σ*,idR*,PKR*,SKR*,CertR*,idθ,PKθ) to obtain the message M* and then simulates the random oracle H3 on its own to obtain h3*=H3(M*,U*,e(U*,CertR*),e(U*,CertR*)SKR*, idθ,PKθ,idR*,PKR*). Using the oracle replay technique [29], B replays AII with the same random tape but with the different hash value h3*′(≠h3*) to generate one more valid ciphertext σ*′=(C*,U*,V*′) such that V*′≠V*. Since σ*=(C*,U*,V*) and σ*′=(C*,U*,V*′) are both valid ciphertexts for the same message M* and randomness r*, we obtain the following relations:
(8)V*-V*′=(h3*SKθ+r*)Certθ-(h3*′SKθ+r*)Certθ=(h3*-h3*′)SKθ(H1(idθ,PKθ)+α)-1Q.
Then, we have the following relations:(9)e(H1(idθ,PKθ)P+αP,V*-V*′)=e(P,(h3*-h3*′)SKθQ).
BecauseQ=aP and SKθ=b, B can compute abP=SKθQ=(h3*-h3*′)-1(H1(idθ,PKθ)+α)(V*-V*′) as the solution to the given CDH problem.
We now deriveB’s advantage in solving the CDH problem. From the above construction, the simulation fails if any of the following events occurs: (1)E1: in the forge phase, B aborts because idS*≠idθ; (2)E2: B fails in using the oracle replay technique to generate one more valid ciphertext. Clearly, Pr[¬E1]=1/qcu. From the forking lemma [29], we know that Pr[¬E2]≥1/9. Thus, we have that if AII produces a valid forgery, then B will succeed in solving the CDH problem with probability ε′=Pr[¬E1∧¬E2]≥1/(9qcu).


## 5.3. Performance

To evaluate the performance of our new CBSC scheme, we compare our scheme with the previous CBSC schemes in terms of the computational cost and the communicational cost.In the computational cost comparison, we consider four major operations: pairing, exponentiation inGT, scalar multiplication in G, and hash. Among these operations, the pairing is considered as the heaviest time-consuming one in spite of the recent advances in the implementation technique. For simplicity, we denote these operations by p,e,m, and h, respectively. In the communicational cost comparison, ciphertext overhead represents the difference (in bits) between the ciphertext length and the message length, |id| denotes the bit-length of user’s identity, and |G| and |Zp| denote the bit-length of an element in G and Zp, respectively. Without considering precomputation, the performances of the compared CBSC schemes are listed in Table 2.Table 2
Performance of the CBSC schemes.
Schemes
Signcryption cost
Designcryption cost
Ciphertext overhead
Ours
2
e
+
3
m
+
3
h
2
p
+
2
e
+
1
m
+
3
h
2
|
G
|
[18]
1
p
+
1
e
+
4
m
+
3
h
3
p
+
1
e
+
1
m
+
3
h
2
|
G
|
[20]
1
p
+
5
m
+
4
h
4
p
+
2
m
+
3
h
3
|
G
|
+
|
id
|
[21]
2
p
+
4
e
+
3
m
+
3
h
3
p
+
4
e
+
3
h
2
|
G
|
+
2
|
Z
p
|The efficiency of a pairing-based cryptosystem always depends on the chosen curve. Boyen [30] computes estimated relative timings for all atomic asymmetric operations (exponentiations and pairings) and representation sizes for group elements when instantiated in supersingular curves with 80-bit security (SS/80) and MNT curves with 80-bit security (MNT/80). In Table 3, we recall the data from [30].Table 3
Timings needed to perform atomic operations and representation of group elements in bits.
Curves
Relative timings(1 unit = 1 scalar multiplication in G)
Representation  sizes (bits)
m
e
p
|
G
|
|
G
T
|
MNT/80
1
36
150
171
1026
SS/80
1
4
20
512
1024To make a much clearer comparison, Table4 gives the concrete values of the computational cost and the communicational cost for the compared CBE schemes according to the data in Table 3. As the hash operation is much more efficient than the multiplication in the group G, the costs of the hash operations are ignored.Table 4
Performance comparison of the CBSC schemes.
Schemes
Signcryption cost
Designcryption cost
Ciphertext overhead
MNT/80
Ours
75
373
342
[18]
187
487
342
[20]
155
602
513
+
|
id
|
[21]
447
594
2390
SS/80
Ours
11
49
1024
[18]
28
65
1024
[20]
25
82
1536
+
|
id
|
[21]
59
76
3072In our proposed CBSC scheme, theSigncrypt algorithm does not require computing any time-consuming pairings. It only needs to compute two exponentiations in GT, three scalar multiplications in G and three hashes in each signcryption operation. TheDesigncrypt algorithm needs to compute two pairings, two exponentiations in GT, one scalar multiplication in G, and three hashes to designcrypt a ciphertext. From Tables 2 and 4, we can see that our scheme is more efficient than the previous CBSC scheme, especially in the computational efficiency. Actually, the computational performance of our scheme can be further optimized when H1(idU,PKU)P+Ppub can be precomputed. Such a precomputation enables us to additionally reduce one scalar multiplication computation in G and one hash computation in both theSigncrypt algorithm and theDesigncrypt algorithm. In addition and most importantly, it is believed that our scheme is the first signcryption scheme in the certificate-based cryptographic setting that achieves security against both the public key replacement attacks and the insider attacks.


## 6. Conclusions

In this paper, we have introduced an improved security model of CBSC that captures both public key replacement attack and insider security. Our cryptanalysis has shown that Luo et al.’s CBSC scheme [20] is insecure in our security model. We have proposed a new CBSC scheme that resists both the key replacement attacks and the insider attacks. Compared with the previous CBSC schemes in the literature, the proposed scheme enjoys better performance, especially in the computation efficiency. However, a limitation of our schemes is that its security can only be achieved in the random oracle model [31]. Therefore, it would be interesting to construct a secure CBSC scheme without random oracles.



---

*Source: 295419-2014-05-12.xml*