# An Efficient Certificateless Generalized Signcryption Scheme

Authors: Bo Zhang; Zhongtian Jia; Chuan Zhao
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Generalized signcryption can adaptively work as an encryption scheme, a signature scheme, or a signcryption scheme with only one algorithm. The paper proposes an efficient certificateless generic signcryption scheme without utilizing bilinear pairing operations. It is proved to satisfy confidentiality and unforgeability against chosen ciphertext and message attacks in an adaptive manner, respectively, in the random oracle model. Due to the lower computational cost and communication overhead, the proposed scheme is suitable for low power and processor devices.


---

## Body

## 1. Introduction

In the traditional Public Key Infrastructure (PKI), a certificate authority (CA) which is a third party issues the certificates to bind the identity of a user and the corresponding public key. The certificate provides an unforgeable and trusted link by CA’s digital signature. However, the problem of certificate management, including the storage, revocation, and distribution of certificates, is complex in this kind of PKI. Identity-based Public Key Cryptosystems (ID-PKC) were introduced by Shamir [1] in 1984 to simplify certificate management problem. A user’s public key can be easily derived from arbitrary strings corresponding to his identity information, such as passport number, telephone number, name, and email address. A trusted third party named private key generator (PKG) computes private keys from a master secret and users’ identity information and distributes these private keys to users participating in the scheme. This eliminates the need for certificates as used in a traditional PKI. ID-based systems may be a good alternative for certificate-based systems from the viewpoint of efficiency and convenience. But an inherent problem of ID-based cryptosystems is the key escrow; that is, the PKG knows the user’s private key, resulting in no user privacy and authenticity. To eliminate these problems simultaneously, Al-Riyami and Paterson introduced the concept of certificateless public key cryptography (CL-PKC) in 2003 [2]. In a CL-PKC, a public/secret key pair is produced by the user himself independently without requiring the public key to be certified. Also, a partial private key is generated by a semi-trusted third party, called the key generation center (KGC), from the unique identifier information of the user. Knowing only one of them should not be able to impersonate the user and carry out any of the cryptographic operations as the user. In other words, CL-PKC can act as an intermediate between traditional PKI and ID-PKC.The confidentiality and authenticity of messages are the basic requirement for secure communication. In 1997, Zheng proposed a cryptographic primitive signcryption [3], which simultaneously fulfils the integrated function of public encryption and digital signature with a computing and communication cost significantly smaller than that required by the signature-then-encryption method. According to the three public key authentication methods, signcryption can be divided into three types: PKI-based signcryption schemes [4–10], ID-based signcryption schemes (IBSC) [11–16], and certificateless signcryption schemes (CLSC) [17–20].Sometimes, confidentiality and authenticity are needed separately, and sometimes, both of them are needed simultaneously. We can use encryption, signature, or signcryption to achieve the security properties, respectively. But maintaining three different primitives or components at the same time is quite a burden to a system, especially to the low power and processor devices in low-bandwidth environments. Generalized signcryption (GSC) was proposed [21–23] to solve this problem. GSC scheme can adaptively work as encryption scheme, signature scheme, or signcryption scheme with only one algorithm. In other words, without any additional modification and computation, it provides double functions when confidentiality and authenticity are required simultaneously and the separate encryption or signature function when one of them is required. So, the GSC scheme can be viewed as a primitive with three work modes. In 2010, the first certificateless generalized signcryption (CLGSC) scheme was introduced by Ji et al. [24]. In their work, the formal definition, security model, and a concrete scheme were proposed. But Kushwah and Lai [25] noted that the scheme [24] is not existentially unforgeable against TypeI adversary, and they proposed a new secure and efficient CLGSC scheme. Zhou et al. [26] proposed a more efficient CLGSC scheme based on the certificateless signcryption proposed in [17]. However, all the existing CLGSC schemes are realized with bilinear pairing operations. Compared with other operations, the bilinear pairing operation is much more complicated. Therefore, a concrete scheme without bilinear pairing is more suitable for applications. Very recently, Zhou et al. [27] introduced the key-insulated mechanism into GSC and propose a concrete scheme without bilinear pairings in the certificateless cryptosystem setting.In this paper, we give a formal definition and the security concept of CLGSC and propose an efficient concrete scheme without utilizing bilinear pairing operations based on a certificateless signcryption-tag key encapsulation mechanism [28]. The concrete scheme is proved to satisfy confidentiality and unforgeability against chosen ciphertext and message attacks in an adaptive manner, respectively, in the random oracle model. Due to less computational cost and communication overhead, the proposed scheme is suitable for low power and processor devices.The rest of the paper is organized as follows. The security problems, complexity assumptions, and the formal model of CLGSC scheme are introduced in Section2. We describe a new CLGSC scheme in Section 3 and give the security proof and performance analysis of the new scheme in Sections 4 and 5, respectively. Finally, the conclusions are given in Section 6.


## 2. Preliminaries

### 2.1. Security Problems and Complexity Assumptions

Several related mathematical hard problems and security assumptions are presented here.(i) The Elliptic Curve Discrete Log Problem (ECDLP) [29]: for group Gq which is generated by P∈Gq, given Q∈RGq, to find x∈Zq∗ such that Q=xP.Definition 1 (ECDLP assumption).
For groupGq which is generated by P∈Gq, given Q∈RGq, the successful advantage of any probabilistic polynomial time (PPT) adversary A is presented as AdvAECDLP=Pr[A(P,Q=xP)=x∣x∈Zq∗]. If there exists no PPT adversary A with nonnegligible advantage ϵ in solving the ECDLP problem, we say that the ECDLP assumption holds.(ii) One-sided Gap Diffie-Hellman problem (ECDLP) [30]: for group Gq which is generated by P∈Gq, Q=xP is a fixed point, given R=yP, to find xyP with the help of a one-sided decision Diffie-Hellman (ODDH) oracle. The ODDH oracle gets the tuple (P,xP,yP,cP) as the input and outputs 1 if c=ab(mod⁡q) and 0 otherwise.Definition 2 (ECDLP assumption).
For groupGq which is generated by P∈Gq, Q=xP is a fixed point, given R=yP. The successful advantage of any PPT adversary A is presented as AdvAECDLP=Pr[A(P,xP,yP)=xyP∣x,y∈Zq∗]. If there exists no PPT adversary A with nonnegligible advantage ϵ by making qo ODDH oracle queries in solving the ECDLP problem, we say that the (qo,ϵ)-ECDLP assumption holds.


### 2.2. Certificateless Generic Signcryption Scheme (CLGSC)

#### 2.2.1. Framework

Certificateless generic signcryption scheme (CLGSC) consists of the following probabilistic polynomial time algorithms.(1) Setup. Take a security parameter l as input, KGC runs Setup algorithm to generate common parametersparams and a master keymsk.params are publicly available, whereas themsk is kept by the KGC secretly. Formally, we can write (1)params,msk⟵Setup1l.(2) Set-User-Key. Take the common parametersparams and the identity information ID of himself as input; each user runs Set-User-Key algorithm to generate a secure value and the corresponding public key value for himself. It returns the user’s secret value x and a corresponding public valuePV. Formally, we can write (2)x,PV⟵Set-User-Keyparams,ID.(3) Extract-Partial-Private-Key. Given the common parametersparams, an identityID, and the corresponding public valuePV, KGC runs Extract-Partial-Private-Key algorithm to generate the partial private key d associated withID. It distributes d to the user via a secure channel. Formally, we can write (3)d⟵Extract-partial-private-keyparams,msk,ID,PV.(4) Set-Private-Key. Given the common parametersparams, the partial private key d, and the secret value x, the user with identityID runs this algorithm to generate the full private keySK for himself. Formally, we can write (4)SK⟵Set-private-keyparams,x,d.(5) Set-Public-Key. Given the common parametersparams, the partial private key d, the secret value x, and the public valuePV, the user with identityID runs this algorithm to generate the full public keyPK as the output. Formally, we can write (5)PK⟵Set-public-keyparams,x,d,PV.(6) CLGSC-Signcrypt. Given the common parametersparams, the message m, the receiver’s identity IDB, and the full public value PKB, the user with identity IDA and the full private key SKA runs this algorithm to generate the ciphertext δ as the output. Note that IDA and IDB could be null string. Formally, we can write (6)IDA,IDB,δ⟵CLGSC-signcryptparams,m,IDA,SKA,IDB,PKB.(7) CLGSC-Unsigncrypt. Given the ciphertext δ, the sender’s identity IDA, and the public key PKA, the receiver with identity IDB and the full private key SKB runs this algorithm to unsigncrypt (or decrypt) the ciphertext. It returns m or true for the valid signcryption ciphertext or signature; return ⊥ means invalid. Note that IDA and IDB could be null string. Formally, we can write (7)m/true/⊥⟵CLGSC-unsigncryptparams,δ,IDA,PKA,IDB,SKB.


#### 2.2.2. Security Model

A CLGSC must satisfy confidentiality in encryption mode or signcryption mode and unforgeability in signcryption mode or signature mode. In a CLGSC scheme, we must consider two types of adversaries: a common user of the system and a honest-but-curious KGC. A common user cannot be in possession of the master secret key generated by KGC. But he can replace the public key of the users with valid public keys of his choice in an adaptive manner. This type of adversary is modeled by the TypeI adversary. An honest-but-curious KGC knows the KGC’s master secret key. But he is not able to replace the public keys of the users. This type of adversary is modeled by the TypeII adversary.An adversaryA can access seven kinds of oracles as follows.Set-User-Key Queries. A requests the secret value for a user U with IDU. C uses the Set-User-Key algorithm to compute (xu,PVU) and sends xU to A. If U’s public key has already been replaced, then a TypeI adversary cannot submit U’s identity IDU and requests the secret value of U.Extract-Partial-Private-Key Queries. A requests the partial private key for a user U with IDU; C uses the Set-User-Key algorithm to compute (xu,PVU) and then sends a partial private key dU generated by the Extract-Partial-Private-Key algorithm to A.Set-Private-Key Queries. A requests the private key for a user U with IDU; C sends the full private key SKU generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm to A. Note that if U’s public key has already been replaced, then a TypeI adversary cannot submit the identity IDU and requests the full private key of U.Set-Public-Key Queries. A requests the public key for a user U with IDU; C returns the public key PKU to A generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm.Public-Key-Replacement Queries. A computes a new public key PKU′ for IDU and replaces PKU. Note that a TypeII adversary cannot access Public-Key-Replacement queries.CLGSC-Signcrypt Queries. A submits (IDA,IDB,m) to C, in which m is a message and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the ciphertext δ to A. Note that if the public key of the sender has been replaced, then C may not return the ciphertext δ. In this case, A must provide the secret value to C.CLGSC-Unsigncrypt Queries. A submits (IDA,IDB,δ) to C, in which δ is a signature or signcryption ciphertext and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the output of CLGSC-unsigncrypt to A. Note that if the public key of the receiver is replaced, then C may not return the corresponding value. In this case, A must provide the secret value to C.ConfidentialityDefinition 3 (IND-CLGSC-CCA2 confidentiality).
A certificateless generic signcryption scheme in signcryption mode or encryption mode is semantically secure against adaptive chosen ciphertext attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries AI and AII, respectively.GAME 1 (IND-CLGSC-CCA2-I)Initial. C generates the system parametersparams and the master secret keymsk by running the Setup algorithm. It keepsmsk secret and sendsparams to AI.Phase I. AI performs a polynomially bounded number of the above queries.Challenge. AI outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that IDB’s full private key has not been extracted by AI in PhaseI. It is also to be noted that IDB’s partial private key has not been extracted and his public key has not been replaced simultaneously. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (IDA,IDB,mγ), and sends the output δ to AI.Phase II. AI asks queries adaptively again. However, the full private key for IDB may not be extracted by AI and the partial private key for IDB may not be extracted if the public key of IDB has been replaced in PhaseI. Only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AI outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAI is AdvAIIND-CLGSC-CCA2-I=2Pr[γ′=γ]-1.GAME 2 (IND-CLGSC-CCA2-II)Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to AII.Phase I. AII performs a polynomially bounded number of queries just as AI in IND-CLGSC-CCA2-I game. Extract-Partial-Private-Key queries are not included here, because AII knows msk, and he can generate users’ partial private keys by himself.Challenge. At the end of PhaseI, AII outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AII must have made no Set-Private-Key queries on IDB in PhaseI. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (mγ,IDA,IDB), and sends the output δ to AII.Phase II. AII asks queries adaptively again. However, the full private key for IDB may not be extracted and only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AII outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAII is AdvAIIIND-CLGSC-CCA2-II=2Pr[γ′=γ]-1.Note that, in the above games, only the signcryption mode and encryption mode of the CLGSC scheme must be considered. The receiver’s identityIDB cannot be vacant. If the sender’s identity IDA is not vacant, the algorithm runs in signcryption mode; otherwise it runs in encryption mode.UnforgeabilityDefinition 4 (EUF-CLGSC-CMA unforgeability).
A certificateless generic signcryption scheme in signature mode or signcryption mode is existentially unforgeable against adaptive chosen message attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries FI and FII, respectively.GAME 3 (EUF-CLGSC-CMA- I )Initial. C generatesparams andmsk by running the Setup algorithm. It keepsmsk secret and sendsparams to FI.Training Phase. Like AI in PhaseI of the IND-CLGSC-CCA2-I game, FI may perform a series of adaptive queries.Forgery. FI outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. The full private key of IDA∗ must not be extracted by FI during the Training Phase. Moreover, FI must have not replaced IDA∗’s public key and extracted IDA∗’s partial private key simultaneously. If the output of CLGSC-unsigncrypt is not ⊥, FI wins the game.GAME 4 (EUF-CLGSC-CMA- I I )Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to FII.Training Phase. Like AII in PhaseI of the IND-CLGSC-CCA2-II game, FII may perform a series of adaptive queries.Forgery. FII outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. During the Training Phase, FII must have made no Set-Private-Key queries and Set-User-Key queries on IDA∗. If the output of CLGSC-unsigncrypt is not ⊥, FII wins the game.Note that, in the above games, only the signcryption mode and signature mode of the CLGSC scheme must be considered. The sender’s identityIDA cannot be vacant. If the receiver’s identity IDB is not vacant, the algorithm runs in signcryption mode; otherwise it runs in signature mode.


## 2.1. Security Problems and Complexity Assumptions

Several related mathematical hard problems and security assumptions are presented here.(i) The Elliptic Curve Discrete Log Problem (ECDLP) [29]: for group Gq which is generated by P∈Gq, given Q∈RGq, to find x∈Zq∗ such that Q=xP.Definition 1 (ECDLP assumption).
For groupGq which is generated by P∈Gq, given Q∈RGq, the successful advantage of any probabilistic polynomial time (PPT) adversary A is presented as AdvAECDLP=Pr[A(P,Q=xP)=x∣x∈Zq∗]. If there exists no PPT adversary A with nonnegligible advantage ϵ in solving the ECDLP problem, we say that the ECDLP assumption holds.(ii) One-sided Gap Diffie-Hellman problem (ECDLP) [30]: for group Gq which is generated by P∈Gq, Q=xP is a fixed point, given R=yP, to find xyP with the help of a one-sided decision Diffie-Hellman (ODDH) oracle. The ODDH oracle gets the tuple (P,xP,yP,cP) as the input and outputs 1 if c=ab(mod⁡q) and 0 otherwise.Definition 2 (ECDLP assumption).
For groupGq which is generated by P∈Gq, Q=xP is a fixed point, given R=yP. The successful advantage of any PPT adversary A is presented as AdvAECDLP=Pr[A(P,xP,yP)=xyP∣x,y∈Zq∗]. If there exists no PPT adversary A with nonnegligible advantage ϵ by making qo ODDH oracle queries in solving the ECDLP problem, we say that the (qo,ϵ)-ECDLP assumption holds.


## 2.2. Certificateless Generic Signcryption Scheme (CLGSC)

### 2.2.1. Framework

Certificateless generic signcryption scheme (CLGSC) consists of the following probabilistic polynomial time algorithms.(1) Setup. Take a security parameter l as input, KGC runs Setup algorithm to generate common parametersparams and a master keymsk.params are publicly available, whereas themsk is kept by the KGC secretly. Formally, we can write (1)params,msk⟵Setup1l.(2) Set-User-Key. Take the common parametersparams and the identity information ID of himself as input; each user runs Set-User-Key algorithm to generate a secure value and the corresponding public key value for himself. It returns the user’s secret value x and a corresponding public valuePV. Formally, we can write (2)x,PV⟵Set-User-Keyparams,ID.(3) Extract-Partial-Private-Key. Given the common parametersparams, an identityID, and the corresponding public valuePV, KGC runs Extract-Partial-Private-Key algorithm to generate the partial private key d associated withID. It distributes d to the user via a secure channel. Formally, we can write (3)d⟵Extract-partial-private-keyparams,msk,ID,PV.(4) Set-Private-Key. Given the common parametersparams, the partial private key d, and the secret value x, the user with identityID runs this algorithm to generate the full private keySK for himself. Formally, we can write (4)SK⟵Set-private-keyparams,x,d.(5) Set-Public-Key. Given the common parametersparams, the partial private key d, the secret value x, and the public valuePV, the user with identityID runs this algorithm to generate the full public keyPK as the output. Formally, we can write (5)PK⟵Set-public-keyparams,x,d,PV.(6) CLGSC-Signcrypt. Given the common parametersparams, the message m, the receiver’s identity IDB, and the full public value PKB, the user with identity IDA and the full private key SKA runs this algorithm to generate the ciphertext δ as the output. Note that IDA and IDB could be null string. Formally, we can write (6)IDA,IDB,δ⟵CLGSC-signcryptparams,m,IDA,SKA,IDB,PKB.(7) CLGSC-Unsigncrypt. Given the ciphertext δ, the sender’s identity IDA, and the public key PKA, the receiver with identity IDB and the full private key SKB runs this algorithm to unsigncrypt (or decrypt) the ciphertext. It returns m or true for the valid signcryption ciphertext or signature; return ⊥ means invalid. Note that IDA and IDB could be null string. Formally, we can write (7)m/true/⊥⟵CLGSC-unsigncryptparams,δ,IDA,PKA,IDB,SKB.


### 2.2.2. Security Model

A CLGSC must satisfy confidentiality in encryption mode or signcryption mode and unforgeability in signcryption mode or signature mode. In a CLGSC scheme, we must consider two types of adversaries: a common user of the system and a honest-but-curious KGC. A common user cannot be in possession of the master secret key generated by KGC. But he can replace the public key of the users with valid public keys of his choice in an adaptive manner. This type of adversary is modeled by the TypeI adversary. An honest-but-curious KGC knows the KGC’s master secret key. But he is not able to replace the public keys of the users. This type of adversary is modeled by the TypeII adversary.An adversaryA can access seven kinds of oracles as follows.Set-User-Key Queries. A requests the secret value for a user U with IDU. C uses the Set-User-Key algorithm to compute (xu,PVU) and sends xU to A. If U’s public key has already been replaced, then a TypeI adversary cannot submit U’s identity IDU and requests the secret value of U.Extract-Partial-Private-Key Queries. A requests the partial private key for a user U with IDU; C uses the Set-User-Key algorithm to compute (xu,PVU) and then sends a partial private key dU generated by the Extract-Partial-Private-Key algorithm to A.Set-Private-Key Queries. A requests the private key for a user U with IDU; C sends the full private key SKU generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm to A. Note that if U’s public key has already been replaced, then a TypeI adversary cannot submit the identity IDU and requests the full private key of U.Set-Public-Key Queries. A requests the public key for a user U with IDU; C returns the public key PKU to A generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm.Public-Key-Replacement Queries. A computes a new public key PKU′ for IDU and replaces PKU. Note that a TypeII adversary cannot access Public-Key-Replacement queries.CLGSC-Signcrypt Queries. A submits (IDA,IDB,m) to C, in which m is a message and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the ciphertext δ to A. Note that if the public key of the sender has been replaced, then C may not return the ciphertext δ. In this case, A must provide the secret value to C.CLGSC-Unsigncrypt Queries. A submits (IDA,IDB,δ) to C, in which δ is a signature or signcryption ciphertext and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the output of CLGSC-unsigncrypt to A. Note that if the public key of the receiver is replaced, then C may not return the corresponding value. In this case, A must provide the secret value to C.ConfidentialityDefinition 3 (IND-CLGSC-CCA2 confidentiality).
A certificateless generic signcryption scheme in signcryption mode or encryption mode is semantically secure against adaptive chosen ciphertext attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries AI and AII, respectively.GAME 1 (IND-CLGSC-CCA2-I)Initial. C generates the system parametersparams and the master secret keymsk by running the Setup algorithm. It keepsmsk secret and sendsparams to AI.Phase I. AI performs a polynomially bounded number of the above queries.Challenge. AI outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that IDB’s full private key has not been extracted by AI in PhaseI. It is also to be noted that IDB’s partial private key has not been extracted and his public key has not been replaced simultaneously. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (IDA,IDB,mγ), and sends the output δ to AI.Phase II. AI asks queries adaptively again. However, the full private key for IDB may not be extracted by AI and the partial private key for IDB may not be extracted if the public key of IDB has been replaced in PhaseI. Only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AI outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAI is AdvAIIND-CLGSC-CCA2-I=2Pr[γ′=γ]-1.GAME 2 (IND-CLGSC-CCA2-II)Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to AII.Phase I. AII performs a polynomially bounded number of queries just as AI in IND-CLGSC-CCA2-I game. Extract-Partial-Private-Key queries are not included here, because AII knows msk, and he can generate users’ partial private keys by himself.Challenge. At the end of PhaseI, AII outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AII must have made no Set-Private-Key queries on IDB in PhaseI. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (mγ,IDA,IDB), and sends the output δ to AII.Phase II. AII asks queries adaptively again. However, the full private key for IDB may not be extracted and only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AII outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAII is AdvAIIIND-CLGSC-CCA2-II=2Pr[γ′=γ]-1.Note that, in the above games, only the signcryption mode and encryption mode of the CLGSC scheme must be considered. The receiver’s identityIDB cannot be vacant. If the sender’s identity IDA is not vacant, the algorithm runs in signcryption mode; otherwise it runs in encryption mode.UnforgeabilityDefinition 4 (EUF-CLGSC-CMA unforgeability).
A certificateless generic signcryption scheme in signature mode or signcryption mode is existentially unforgeable against adaptive chosen message attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries FI and FII, respectively.GAME 3 (EUF-CLGSC-CMA- I )Initial. C generatesparams andmsk by running the Setup algorithm. It keepsmsk secret and sendsparams to FI.Training Phase. Like AI in PhaseI of the IND-CLGSC-CCA2-I game, FI may perform a series of adaptive queries.Forgery. FI outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. The full private key of IDA∗ must not be extracted by FI during the Training Phase. Moreover, FI must have not replaced IDA∗’s public key and extracted IDA∗’s partial private key simultaneously. If the output of CLGSC-unsigncrypt is not ⊥, FI wins the game.GAME 4 (EUF-CLGSC-CMA- I I )Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to FII.Training Phase. Like AII in PhaseI of the IND-CLGSC-CCA2-II game, FII may perform a series of adaptive queries.Forgery. FII outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. During the Training Phase, FII must have made no Set-Private-Key queries and Set-User-Key queries on IDA∗. If the output of CLGSC-unsigncrypt is not ⊥, FII wins the game.Note that, in the above games, only the signcryption mode and signature mode of the CLGSC scheme must be considered. The sender’s identityIDA cannot be vacant. If the receiver’s identity IDB is not vacant, the algorithm runs in signcryption mode; otherwise it runs in signature mode.


## 2.2.1. Framework

Certificateless generic signcryption scheme (CLGSC) consists of the following probabilistic polynomial time algorithms.(1) Setup. Take a security parameter l as input, KGC runs Setup algorithm to generate common parametersparams and a master keymsk.params are publicly available, whereas themsk is kept by the KGC secretly. Formally, we can write (1)params,msk⟵Setup1l.(2) Set-User-Key. Take the common parametersparams and the identity information ID of himself as input; each user runs Set-User-Key algorithm to generate a secure value and the corresponding public key value for himself. It returns the user’s secret value x and a corresponding public valuePV. Formally, we can write (2)x,PV⟵Set-User-Keyparams,ID.(3) Extract-Partial-Private-Key. Given the common parametersparams, an identityID, and the corresponding public valuePV, KGC runs Extract-Partial-Private-Key algorithm to generate the partial private key d associated withID. It distributes d to the user via a secure channel. Formally, we can write (3)d⟵Extract-partial-private-keyparams,msk,ID,PV.(4) Set-Private-Key. Given the common parametersparams, the partial private key d, and the secret value x, the user with identityID runs this algorithm to generate the full private keySK for himself. Formally, we can write (4)SK⟵Set-private-keyparams,x,d.(5) Set-Public-Key. Given the common parametersparams, the partial private key d, the secret value x, and the public valuePV, the user with identityID runs this algorithm to generate the full public keyPK as the output. Formally, we can write (5)PK⟵Set-public-keyparams,x,d,PV.(6) CLGSC-Signcrypt. Given the common parametersparams, the message m, the receiver’s identity IDB, and the full public value PKB, the user with identity IDA and the full private key SKA runs this algorithm to generate the ciphertext δ as the output. Note that IDA and IDB could be null string. Formally, we can write (6)IDA,IDB,δ⟵CLGSC-signcryptparams,m,IDA,SKA,IDB,PKB.(7) CLGSC-Unsigncrypt. Given the ciphertext δ, the sender’s identity IDA, and the public key PKA, the receiver with identity IDB and the full private key SKB runs this algorithm to unsigncrypt (or decrypt) the ciphertext. It returns m or true for the valid signcryption ciphertext or signature; return ⊥ means invalid. Note that IDA and IDB could be null string. Formally, we can write (7)m/true/⊥⟵CLGSC-unsigncryptparams,δ,IDA,PKA,IDB,SKB.


## 2.2.2. Security Model

A CLGSC must satisfy confidentiality in encryption mode or signcryption mode and unforgeability in signcryption mode or signature mode. In a CLGSC scheme, we must consider two types of adversaries: a common user of the system and a honest-but-curious KGC. A common user cannot be in possession of the master secret key generated by KGC. But he can replace the public key of the users with valid public keys of his choice in an adaptive manner. This type of adversary is modeled by the TypeI adversary. An honest-but-curious KGC knows the KGC’s master secret key. But he is not able to replace the public keys of the users. This type of adversary is modeled by the TypeII adversary.An adversaryA can access seven kinds of oracles as follows.Set-User-Key Queries. A requests the secret value for a user U with IDU. C uses the Set-User-Key algorithm to compute (xu,PVU) and sends xU to A. If U’s public key has already been replaced, then a TypeI adversary cannot submit U’s identity IDU and requests the secret value of U.Extract-Partial-Private-Key Queries. A requests the partial private key for a user U with IDU; C uses the Set-User-Key algorithm to compute (xu,PVU) and then sends a partial private key dU generated by the Extract-Partial-Private-Key algorithm to A.Set-Private-Key Queries. A requests the private key for a user U with IDU; C sends the full private key SKU generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm to A. Note that if U’s public key has already been replaced, then a TypeI adversary cannot submit the identity IDU and requests the full private key of U.Set-Public-Key Queries. A requests the public key for a user U with IDU; C returns the public key PKU to A generated by the Set-User-Key algorithm and Extract-Partial-Private-Key algorithm.Public-Key-Replacement Queries. A computes a new public key PKU′ for IDU and replaces PKU. Note that a TypeII adversary cannot access Public-Key-Replacement queries.CLGSC-Signcrypt Queries. A submits (IDA,IDB,m) to C, in which m is a message and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the ciphertext δ to A. Note that if the public key of the sender has been replaced, then C may not return the ciphertext δ. In this case, A must provide the secret value to C.CLGSC-Unsigncrypt Queries. A submits (IDA,IDB,δ) to C, in which δ is a signature or signcryption ciphertext and IDA and IDB are the sender’s and the receiver’s identities, respectively. C returns the output of CLGSC-unsigncrypt to A. Note that if the public key of the receiver is replaced, then C may not return the corresponding value. In this case, A must provide the secret value to C.ConfidentialityDefinition 3 (IND-CLGSC-CCA2 confidentiality).
A certificateless generic signcryption scheme in signcryption mode or encryption mode is semantically secure against adaptive chosen ciphertext attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries AI and AII, respectively.GAME 1 (IND-CLGSC-CCA2-I)Initial. C generates the system parametersparams and the master secret keymsk by running the Setup algorithm. It keepsmsk secret and sendsparams to AI.Phase I. AI performs a polynomially bounded number of the above queries.Challenge. AI outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that IDB’s full private key has not been extracted by AI in PhaseI. It is also to be noted that IDB’s partial private key has not been extracted and his public key has not been replaced simultaneously. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (IDA,IDB,mγ), and sends the output δ to AI.Phase II. AI asks queries adaptively again. However, the full private key for IDB may not be extracted by AI and the partial private key for IDB may not be extracted if the public key of IDB has been replaced in PhaseI. Only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AI outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAI is AdvAIIND-CLGSC-CCA2-I=2Pr[γ′=γ]-1.GAME 2 (IND-CLGSC-CCA2-II)Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to AII.Phase I. AII performs a polynomially bounded number of queries just as AI in IND-CLGSC-CCA2-I game. Extract-Partial-Private-Key queries are not included here, because AII knows msk, and he can generate users’ partial private keys by himself.Challenge. At the end of PhaseI, AII outputs a tuple (m0,m1,IDA,IDB), in which m0 and m1 are distinct messages of equal length and IDA and IDB are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AII must have made no Set-Private-Key queries on IDB in PhaseI. C picks γ∈{0,1} randomly, runs the algorithm of CLGSC-signcrypt with (mγ,IDA,IDB), and sends the output δ to AII.Phase II. AII asks queries adaptively again. However, the full private key for IDB may not be extracted and only after the public key PKA or PKB has been replaced, CLGSC-unsigncrypt query on δ with sender IDA and receiver IDB is allowed.Guess Stage. AII outputs his guess γ′ and if γ′=γ he wins the game.The advantage ofAII is AdvAIIIND-CLGSC-CCA2-II=2Pr[γ′=γ]-1.Note that, in the above games, only the signcryption mode and encryption mode of the CLGSC scheme must be considered. The receiver’s identityIDB cannot be vacant. If the sender’s identity IDA is not vacant, the algorithm runs in signcryption mode; otherwise it runs in encryption mode.UnforgeabilityDefinition 4 (EUF-CLGSC-CMA unforgeability).
A certificateless generic signcryption scheme in signature mode or signcryption mode is existentially unforgeable against adaptive chosen message attacks if, for all PPT adversary, the advantage is negligible in the following games. The games are played between a challengerC and the adversaries FI and FII, respectively.GAME 3 (EUF-CLGSC-CMA- I )Initial. C generatesparams andmsk by running the Setup algorithm. It keepsmsk secret and sendsparams to FI.Training Phase. Like AI in PhaseI of the IND-CLGSC-CCA2-I game, FI may perform a series of adaptive queries.Forgery. FI outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. The full private key of IDA∗ must not be extracted by FI during the Training Phase. Moreover, FI must have not replaced IDA∗’s public key and extracted IDA∗’s partial private key simultaneously. If the output of CLGSC-unsigncrypt is not ⊥, FI wins the game.GAME 4 (EUF-CLGSC-CMA- I I )Initial. C generatesparams andmsk by running the Setup algorithm. It sendsparams andmsk to FII.Training Phase. Like AII in PhaseI of the IND-CLGSC-CCA2-II game, FII may perform a series of adaptive queries.Forgery. FII outputs a tuple (IDA∗,IDB∗,δ∗). It must not be an output of the CLGSC-signcrypt query. During the Training Phase, FII must have made no Set-Private-Key queries and Set-User-Key queries on IDA∗. If the output of CLGSC-unsigncrypt is not ⊥, FII wins the game.Note that, in the above games, only the signcryption mode and signature mode of the CLGSC scheme must be considered. The sender’s identityIDA cannot be vacant. If the receiver’s identity IDB is not vacant, the algorithm runs in signcryption mode; otherwise it runs in signature mode.


## 3. The Concrete Scheme

Motivated by the pairing-free CLSC-TKEM protocol, in this section, we present a novel certificateless generalized signcryption scheme. It consists of seven algorithms.(1) Setup. Given a security parameters l∈Z+, the KGC executes the following operations:(i)
It chooses al-bits prime q and the tuple {Fq,E/Fq,Gq,P}, where Gq is generated by P.(ii)
It choosess∈RZq∗ uniformly as the master key and computes Ppub=s·P.(iii)
LetH0, H1, H2 be cryptography hash functions, where H0:0,1∗×Gq2→Zq∗, H1:Gq3×0,1∗→{0,1}w, H2:0,1∗×0,1∗×Gq3→Zq∗, where w is the plaintext block length.(iv)
Define an index functionf(ID) as follows: f(ID)=0 if ID=∅; otherwise, f(ID)=1.(v)
The public parameters and functions are presented asparams={Fq,E/Fq,Gq,P,Ppub,H0,H1,H2}.(2) Set-User-Key. A user U with the identity IDU randomly chooses xU∈Zq∗ as its secret value and computes the corresponding public value as PVU=xU·P.(3) Extract-Partial-Private-Key. U sends (IDU,PVU) to the KGC. In turn, the KGC generates and returns the partial private key of U as follows:(i)
It choosesrU∈Zq∗ and computes RU=rU·P.(ii)
It computesdU=rU+s·H0IDU,RU,PVUmodq.d U is the partial private key of U. U can accept dU as a valid partial private key by determining if dU·P=RU+H0(IDU,RU,PVU)·Ppub holds.(4) Set-Private-Key. The user U takes the pair (xU,dU) as its full private key SKU.(5) Set-Public-Key. The user U takes the pair (PVU,RU) as its full public key PKU.(6) CLGSC-Signcrypt. With the message m and the receiver’s identity IDB, the sender A performs as follows:(i)
It choosessA∈Zq∗ randomly and computes V=sA·P.(ii)
It computesf(IDA), f(IDB).(iii)
It computesc=H1(V,T,sAPVB,IDB)·f(IDB)⊕m, where T=sA·(H0(IDB,RB,PVB)·Ppub+RB+PVB).(iv)
It computesW=(dA+xA·H2(IDA,m,V,T,PVA)+sA·H2(IDA,m,V,T,RA))·f(IDA).(v)
It setsδ=(V,W,c) and returns (IDA,IDB,δ) as the ciphertext.(7) CLGSC-Unsigncrypt. Given the ciphertext (IDA,IDB,δ=(V,W,c)), the receiver IDB decrypts and verifies the ciphertext as follows:(i)
It computesf(IDA), f(IDB).(ii)
It computesm′=c⊕(H1(V,T′,xBV,IDB)·f(IDB)), where T′=V·(xB+dB).(iii)
It checks ifW·P=f(IDA)(RA+H0(IDA,RA,PVA)·Ppub+PVA·H2(IDA,m′,V,T′,PVA)+V·H2(IDA,m′,V,T′,RA)). If the equation does not hold, then return ⊥ indicating the message is not valid. Otherwise, return true when f(IDB)=0 indicating it is a valid signature of user A or m indicating it is a valid encryption/signcryption ciphertext of the message m sent to user B.Correctness of the Scheme. The correctness of the proposed concrete scheme is proved as follows.(i) Correctness of the Encryption  (8) m ′ = c ⊕ H 1 V , T ′ , x B V , I D B = c ⊕ H 1 V , V · x B + d B , x B s A P , I D B = c ⊕ H 1 V , s A · x B · P + d B · P , s A x B P , I D B = c ⊕ H 1 V , s A · P V B + R B + H 0 I D B , R B , P V B · P p u b , s A P V B , I D B = c ⊕ H 1 V , T , s A P V B , I D B = H 1 V , T , s A P V B , I D B ⊕ m ⊕ H 1 V , T , s A P V B , I D B = m .(ii) Correctness of the Signature  (9) W · P = d A + x A · H 2 I D A , m , V , T , P V A + s A · H 2 I D A , m , V , T , R A · P = d A · P + x A · P · H 2 I D A , m , V , T , P V A + s A · P · H 2 I D A , m , V , T , R A = r A · P + s · P · H 0 I D A , R A , P V A + x A · P · H 2 I D A , m , V , T , P V A + s A · P · H 2 I D A , m , V , T , R A = R A + H 0 I D A , R A , P V A · P p u b + P V A · H 2 I D A , m , V , T , P V A + V · H 2 I D A , m , V , T , R A .


## 4. Security Analysis of the Proposed Scheme

In this section, the security of the proposed concrete CLGSC scheme is proved as follows.


### 4.1. Confidentiality

Theorem 5.
The CLGSC scheme is semantically secure against adaptive chosen ciphertext attacks in encryption mode or signcryption mode in the random oracle model.Theorem5 is proved based on Lemmas 6 and 7.Lemma 6.
If an adversaryAI has a nonnegligible advantage ε against the IND-CLGSC-CCA2-I security of our scheme and performing qHi queries to oracles Hi(i=0,1,2), qppk Extract-Partial-Private-Key queries, and qsk Set-Private-Key queries, then there is an algorithm that solves the ECDLP problem with probability ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk))·1/qH1.Proof.
Given an instance of the ECDLP problem, for groupGq generated by P and a fixed second point Q(=aP) having as input R(=bP)∈Gq, C has to compute for the point S(=cP)∈Gq such that c=ab(mod⁡q) with the help of a ODDH oracle. Suppose the IND-CLGSC-CCA2-I security of the CLGSC can be violated by a Type I adversary AI. C can utilize AI to compute abP as the solution to this instance by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=s·P. It sendsparams to AI and maintains lists Li(0≤i≤2) to keep the consistency between the responses to the hash queries and a list Lk of issued keys which are initially empty. C selects t randomly, where 1≤t≤qH0, and takes IDt as the target identity. C chooses et,xt∈RZq∗ and sets H0(IDt,Rt,PVt)=-et, Rt=etPpub+aP-xtP, and PVt=xtP. C inserts (IDt,Rt,PVt,-et) into the list L0 and (IDt,⊥,xt,Rt,PVt) into the list Lk.
C answers AI’s queries to random oracles Hi(0≤i≤2) as follows.
(i)H0queries: when AI submits a H0 query with (IDi,Ri,PVi) for some i∈[1,q0], C checks in L0, and if (IDi,Ri,PVi,-ei) exists, C returns -ei. Otherwise, C chooses ei∈RZq∗ and returns -ei to AI. Then C inserts (IDi,Ri,PVi,-ei) into the list L0.
(ii)H1queries: when AI submits a H1 query with (Vi,Ti,Yi,IDi) for some i∈[1,q1], C sets the tuple (aP,Vi,Ti) as the input of ODDH orale. If the output of ODDH oracle is 1, then C returns Ti as the solution abP and stops; else C searches in L1, if (Vi,∗,Yi,IDi,li) exists, it replaces the symbol ∗ with Ti and returns li. Otherwise, C chooses li∈R0,1n and returns li to AI. Then C inserts (Vi,Ti,Yi,IDi,li) into the list L1.
(iii)H2queries: when AI submits a H2 query with (IDi,mi,Vi,Ti,PVi/Ri) for some i∈[1,q2], C checks in L2, and if (IDi,mi,Vi,Ti,PVi/Ri,hi) exists in L2, C returns hi. Otherwise, C chooses hi∈RZq∗ and returns hi to AI. Then C inserts (IDi,mi,Vi,Ti,PVi/Ri,hi) into L2.
C can answer AI’s other queries as follows.
Phase I
(i) Set-User-Key Queries. AI requests a secret value of the user with IDi. If the public key of IDi has not been replaced, then C responds with xi by retrieving from the list Lk.
(ii) Extract-Partial-Private-Key Queries. AI requests the partial private key of a user with IDi. If IDi=IDt, C aborts the execution. Otherwise, C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns di. Otherwise, C computes the partial private key of IDi by using the actual Extract-Partial-Private-Key algorithm, and C inserts (IDi,di,xt,Ri,PVi) into the list Lk and returns di.
(iii) Set-Private-Key Queries. AI requests a user’s full private key with IDi. C aborts the execution when IDi=IDt. Otherwise, C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns the corresponding private key (xi,di). Otherwise, C picks ei,bi,xi∈RZq∗, then sets H0(IDi,Ri,PVi)=-ei, Ri=eiPpub+biP, and computes PVi=xiP·di=bi and it satisfies the equation diP=Ri+H0(IDi,Ri,PVi)Ppub. C returns (xi,di) to AI and inserts (IDi,Ri,PVi,-ei) into the list L0 and (IDi,di,xi,Ri,PVi) into Lk.
(iv) Set-Public-Key Queries. AI requests a user’s public key with IDi. C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns the corresponding public key (Ri,PVi). Otherwise, C picks ei,bi,xi∈RZq∗, then sets H0(IDi,Ri,PVi)=-ei, Ri=eiPpub+biP, and computes the public key as PVi=xiP·di=bi and it satisfies the equation diP=Ri+H0(IDi,Ri,PVi)Ppub. C returns (PVi,Ri) to AI and inserts (IDi,Ri,PVi,-ei) into the list L0 and (IDi,di,xi,Ri,PVi) into Lk.
(v) Public-Key-Replacement Queries. AI requests to replace a user’s public key (Ri,PVi) with chosen values (IDi,Ri′,PVi′). C updates corresponding tuple with (IDi,-,-,Ri′,PVi′).
(vi) CLGSC-Signcrypt Queries. AI sends the tuple (IDA,PVA,RA,IDB,PVB,RB,m) to C. For each query (IDA,IDB), if IDA≠IDt, C executes the Set-Private-Key algorithm to compute SKA corresponding to IDA. Then, C gets the ciphertext δ by running the actual CLGSC-signcrypt algorithm. C sends δ to AI. If IDA=IDt (and hence, IDB≠IDt), C can obtain the full private key SKB corresponding to IDB. C computes V=rP-ht-1·ap, T=V·(xB+dB), sets H2(IDA,m,V,T,PVA)=ht′, H2(IDA,m,V,T,RA)=ht, and adds the tuples (IDA,m,V,T,PVA,ht′) and (IDA,m,V,T,RA,ht) to the list L2 in which r,ht,ht′∈RZq∗. C computes c=H1(V,T,sBV,IDB)·f(IDB)⊕m and W=r·ht+xA·ht′-xA. C outputs (IDA,IDB,δ=(V,W,c)) as the ciphertext.
The tuple(IDA,IDB,δ=(V,W,c)) can pass the verification as the valid ciphertext because the equality holds as follows: (10)RA+H0IDA,RA,PVA·Ppub+PVA·H2IDA,m,V,T,PVA+V·H2IDA,m,V,T,RA=etPpub+aP-xtP+-etPpub+xtP·ht′+rP-ht-1aP·ht=r·ht+xtht′-xt·P=W·P.
(vii) CLGSC-Unsigncrypt Queries. AI submits (IDA,IDB,δ) to C. If IDB≠IDt, C obtains the receiver’s private key and returns the output of CLGSC-unsigncrypt algorithm to AI. Note that if the receiver’s public value is replaced, C may not obtain the receiver’s secret value. In this case, receiver’s secret value is requested to be provided by A. Otherwise, C searches in L2 for (IDA,m,V,T,PVA,hi) and (IDA,m,V,T,RA,hi′). If the entries exist and the equality W·P=RA+H0(IDA,RA,PVA)·Ppub+PVA·hi+V·hi′ holds, T is retrieved. If C can find a tuple (V,T,Y,IDB,l) in L1 making the ODDH oracle return 1 when queries are on (ap,V,T), then the message is c⊕l.
Challenge. AI submits (m0,m1,IDA∗,IDB∗) in which m0 and m1 are distinct messages of equal length and IDA∗ and IDB∗ are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AI must have made no Set-Private-Key queries on IDB∗ in PhaseI. It is also to be noted that IDB∗’s partial private key has not been extracted and his public key has not been replaced simultaneously. C aborts the game if IDB∗≠IDt. Otherwise, C generates the challenge ciphertext as follows.(1)
It setsV∗=bP and chooses T∗∈RGq.(2)
It selects randomly a bitγ∈{0,1} and a random hash value h and sets c∗=mγ⊕h.(3)
It selectsW∗, satisfies the equation W∗P=RA+H0(IDA,RA,PVA)·Ppub+PVA·H2(IDA,m,V∗,T∗,PVA)+V∗·H2(IDA,m,V∗,T∗,RA), and sends δ∗=(V∗,W∗,c∗) to AI.
Phase II. AI asks queries adaptively again. In addition, the full private key for IDB∗ may not be extracted by AI and the partial private key for IDB∗ may not be extracted if the public key of IDB∗ has been replaced in PhaseI. Only after the public key PKA∗ or PKB∗ has been replaced, CLGSC-unsigncrypt query on δ with sender IDA∗ and receiver IDB∗ is allowed.
Guess. Since AI is able to break the IND-CLGSC-CCA2-I security of the CLGSC, a H1 query with (V∗,T∗,Y∗,IDB∗) should have been asked. Note that T∗=b·(H0(IDB,RB,PVB)·Ppub+RB+PVB)=abP. Therefore, one of the T’s in L1 is the ECDLP problem’s solution. C chooses one T randomly and outputs it as the solution.
In the above challenge query, the sendersIDA and IDA∗ can be ∅ for the encryption mode; otherwise, it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Lets E1, E2, and E3 be the events when C aborts this game.
(i)E1 is an event in which the target identity IDt’s partial private key is queried by AI. The probability of E1 is Pr[E1]=qppk/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by AI. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the receiver by AI during the challenge phase. The probability of E3 is Pr[E3]=1-1/(qH0-qppk-qsk).
Thus,C does not abort this game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).
C chooses the solution of ECDLP problem from L1’s probability of 1/qH1. So, the successful advantage of C is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk))·1/qH1.Lemma 7.
IfAII has nonnegligible advantage ε against the IND-CLGSC-CCA2-II security of our scheme and performing qsv Extract-Secret-Value queries, qsk Set-Private-Key queries, and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm that solves the ECDLP problem with probability ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).Proof.
Given an instance of the ECDLP problem, for groupGq generated by P and a fixed second point Q(=aP) having as input R(=bP)∈Gq, C has to compute for the point S(=cP)∈Gq such that c=ab(mod⁡q) with the help of a ODDH oracle. Suppose the IND-CLGSC-CCA2-II security of the CLGSC can be violated by a TypeII adversary AII. C can utilize AII to compute abP as the solution to this instance by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=s·P. C sendsparams and s to AII and maintains lists Li(0≤i≤2) to avoid the inconsistency between the responses to the hash queries and a list Lk of issued keys which is initially empty. C selects t randomly, where 1≤t≤qH0, and fixes IDt as the target identity. C chooses at,lt∈RZq∗, sets H0(IDt,Rt,PVt)=lt, and computes Rt=atP,dt=at+lt·s, and the public key as PVt=aP. C inserts (IDt,Rt,PVt,lt) into the list L0 and (IDt,dt,⊥,Rt,PVt) into the list Lk.
C answers AII’s queries to random oracles Hi(0≤i≤2) as follows:
(i)H0queries: when AII submits a H0 query with (IDi,Ri,PVi) for some i∈[1,q0], C checks if there exists a tuple (IDi,Ri,PVi,li) in L0. If such a tuple exists, C answers with li. Otherwise, C chooses li∈RZq∗ and returns li as the answer. Then C inserts (IDi,Ri,PVi,li) into the list L0.
(ii)H1queries: when AII submits a H1 query with (Vi,Ti,Yi,IDi), where i∈[1,q1], C sets the tuple (aP,Vi,Yi) as the input of ODDH oracle. If the output of ODDH oracle is 1, then C outputs Yi as the solution; else C searches L1 with entries (Vi,Ti,∗,IDi,li). If such a tuple exists, it replaces the symbol ∗ with Yi and returns li. Otherwise, C chooses li∈R0,1n, inserts (Vi,Ti,Yi,IDi,li) into L1, and returns li to AII.
(iii)H2queries: when AII submits a H2 query with (IDi,mi,Vi,Ti,PVi/Ri), where i∈[1,q2], C checks whether (IDi,mi,Vi,Ti,PVi/Ri,hi) exists in L2. If it exists, C returns hi. Otherwise, C chooses hi∈RZq∗, inserts (IDi,mi,Vi,Ti,PVi/Ri,hi) into L2, and returns hi.
C can answer AII’s other queries as follows.
Phase I
(i) Set-User-Key Queries. AII requests a user’s secret value with IDi. If IDi=IDt, C aborts. If IDi≠IDt, C checks for a tuple (IDi,di,xi,Ri,PVi) in Lk. If it exists, C returns xi. Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and the public key as PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns xi.
(ii) Set-Private-Key Queries. AII produces IDi to C and requests a user’s private key with IDi. If IDi=IDt, C aborts. Otherwise, C checks for a tuple (IDi,di,xi,Ri,PVi) in Lk. If it exists, C returns (xi,di). Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns (xi,di).
(iii) Set-Public-Key Queries. AII requests a user’s public key with IDi. C checks for a tuple (IDi,di,xi,Ri,PVi). If it exists, C returns the corresponding public key (PVi,Ri). Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and the public key as PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns (PVi,Ri).
(iv) CLGSC-Signcrypt Queries. AII sends the tuple IDA,PVA,RA,IDB,PVB,RB,m to C. For each query (IDA,IDB), if IDA≠IDt, C executes the Set-Private-Key algorithm to compute SKA corresponding to IDA. Then, C gets the ciphertext δ by running the actual CLGSC-signcrypt algorithm. C sends δ to AII. If IDA=IDt (and hence, IDB≠IDt), C can obtain the full private key SKB corresponding to IDB. C computes V=rP-ht-1ht′·ap, T=V·(xB+dB), sets H2(IDA,m,V,T,PVA)=ht′, H2(IDA,m,V,T,RA)=ht, and adds the tuples (IDA,m,V,T,PVA,ht′) and (IDA,m,V,T,RA,ht) to the list L2 in which r,ht,ht′∈RZq∗. C computes c=H1(V,T,sBV,IDB)·f(IDB)⊕m and W=r·ht+dt. C outputs (IDA,IDB,δ=(V,W,c)) as the ciphertext.
The tuple(IDA,IDB,δ=(V,W,c)) can pass the verification as the valid ciphertext because the equality holds as follows: (11)RA+H0IDA,RA,PVA·Ppub+PVA·H2IDA,m,V,T,PVA+V·H2IDA,m,V,T,RA=atP+ltP+aPht′+rP-ht-1aP·ht=r·ht+at+slt·P=r·ht+dt·P=W·P.
(v) CLGSC-Unsigncrypt Queries. AII submits (IDA,IDB,δ) to C. If IDB≠IDt, C obtains the receiver’s private key, runs the CLGSC-unsigncrypt algorithm, and returns the output of CLGSC-unsigncrypt to AII. Otherwise, C searches in L2 for (IDA,m,V,T,PVA,hi′) and (IDA,m,V,T,RA,hi). If the entries exist and the equality W·P=RA+H0(IDA,RA,PVA)·Ppub+PVA·hi′+V·hi holds, T is retrieved. If C can find a tuple (V,T,Y,IDB,l) in L1 making the ODDH oracle return 1 when queries are on (ap,V,Y), then the message is c⊕l.
Challenge. AII submits (m0,m1,IDA∗,IDB∗) in which m0 and m1 are distinct messages of equal length and IDA∗ and IDB∗ are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AII must have made no Set-Private-Key queries on IDB∗ in PhaseI. C aborts the game if IDB∗≠IDt. Otherwise, C generates the challenge ciphertext as follows. (1)
It setsV∗=bP, where bP is given in the instance of the ECDLP problem and computes T∗=(xB∗+dB∗)·V∗.(2)
It selects randomly a bitγ∈{0,1} and h as a random hash value and sets c∗=mγ⊕h.(3)
It selectsW∗, satisfies the equation W∗P=RA+H0(IDA,RA,PVA)·Ppub+PVA·H2(IDA,m,V∗,T∗,PVA)+V∗·H2(IDA,m,V∗,T∗,RA), and sends δ∗=(V∗,W∗,c∗) to AII.
Phase II. AII asks queries adaptively again. In addition, it cannot query CLGSC-unsigncrypt on δ∗.
Guess. Since AII is able to break the IND-CLGSC-CCA2-II security of the CLGSC, a H1 query with (V∗,T∗,Y∗,IDB∗) should have been asked. Note that Y∗=xB∗·V∗=abP. Therefore, one of the qH1 values of Y∗ in L1 is the ECDLP problem’s solution. C chooses one Y∗ randomly and outputs it as the solution.
In the above challenge query, the sendersIDA and IDA∗ can be ∅ for the encryption mode; otherwise, it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. In order to assess the probability of success of the challenger, C lets E1, E2, and E3 be the events in which C aborts the IND-CLGSC-CCA2-II game.
(i)E1 is an event in which AII asks to query the secret value of the target identity IDt. The probability of E1 is Pr[E1]=qsv/qH0.
(ii)E2 is an event in which AII asks to query the private key of the target identity IDt. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the receiver by AII during the challenge. The probability of E3 is Pr[E3]=1-1/(qH0-qsk-qsv).
Thus,C does not abort the IND-CLGSC-CCA2-II game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).
So, the successful advantage ofC is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).


### 4.2. Unforgeability

Theorem 8.
The CLGSC scheme in signcryption mode or signature mode is existentially unforgeable.Theorem8 is proved based on Lemmas 9 and 10.Lemma 9.
If an adversaryFI has nonnegligible advantage ε against the EUF-CLGSC-CMA-I security of our scheme and performing qppk Extract-Partial-Private-Key queries, qsk Set-Private-Key queries, and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm that solves the ECDLP problem with probability ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).Proof.
Given an instance of the ECDLP problem(P,bP)∈Gq, C must find b. Suppose the EUF-CLGSC-CMA-I security of the CLGSC can be violated by a forger FI. C can utilize FI to compute b as the solution by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=sP; it sendsparams to FI and maintains lists Li(0≤i≤2) to keep consistency between the responses to the hash queries and a list Lk of issued keys which is initially empty.
Training Phase. FI may make a series of queries and all of the queries are responded to identically as those queries in the IND-CLGSC-CCA2-I game.
Forgery. FI returns a valid ciphertext from the sender IDA to the receiver IDB. If IDA≠IDt, C aborts the execution of this game. We are ready to apply the forking lemma [31] that essentially says the following: consider the concrete scheme producing signatures (m,V,h,W) or signcryption ciphertexts of the form (c,V,h,W), where each of V,h,W corresponds to one of the three moves of a honest-verifier zero-knowledge protocol. If FI is a sufficiently efficient forger in the above interaction and forges a signature or signcryption ciphertext (V,W,c) in a time t with probability ϵ⩾10(qsc+1)(qsc+qh)/2l (l being a security parameter so that h is uniformly taken from a set of 2l elements) when making qsc CLGSC-signcrypt queries and qh random oracle calls and if the triples (V,h,W) can be simulated without knowing the private key, then there exists a Turing machine F′ that uses FI to produce two valid ciphertexts (V∗,W,c∗) and (V∗,W∗,c∗) on the same message m, in expected time t′⩽120686qht/ϵ. Thus, we can get W·P=RA-et·Ppub+ht′·PVA+ht·V and W∗·P=RA-et·Ppub+ht′·PVA+ht∗·V. Let V=bP. We can obtain the following value.(12)W·P-W∗·P=htV˙-ht∗·V⟹W-W∗·P=ht-ht∗·V⟹W-W∗·P=ht-ht∗·bP⟹W-W∗=ht-ht∗·b⟹W-W∗(˙ht-ht∗)-1=b.Therefore, C solve the ECDLP as b=(W-W∗)(˙ht-ht∗)-1 for the ECDLP problem.
In the above forgery query, the receiverIDB can be ∅ for the signature mode; otherwise it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Let E1, E2, and E3 be the events when C aborts the game.
(i)E1 is an event in which the target identity IDt’s partial private key is queried by FI. The probability of E1 is Pr[E1]=qppk/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by FI. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the sender by FI during the forgery. The probability of E3 is Pr[E3]=1-1/(qH0-qppk-qsk).
Thus,C does not abort the EUF-CLGSC-CMA-I game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).
So, the successful advantage ofC is ADVCELDLP=Pr[C(P,bP)=b]=ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).Lemma 10.
If an adversaryFII has nonnegligible advantage ε against the EUF-CLGSC-CMA-II security of our scheme performing qsv Extract-Secret-Value queries and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm C that solves the ECDLP problem with probability ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).Proof.
Given an instance of the ECDLP problem(P,bP), C must find b. Suppose the EUF-CLGSC-CMA-II security of the CLGSC can be violated by a forger FII. C can utilize FII to compute b as the solution by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=sP; it sendsparams and s to FII and maintains lists Li(0≤i≤2) to keep consistency between the responses to the hash queries and a list Lk of issued keys which is initially empty.
Training Phase. FII may make a series of queries and all the queries are responded to identically as those queries in the IND-CLGSC-CCA2-II game.
Forgery. Eventually, FII returns a valid ciphertext from the sender IDA to the receiver IDB. If IDA≠IDt, C aborts the execution of this game. It follows from the forking lemma [31] that if FII is a sufficiently efficient forger in the above interaction, then we can construct another probabilistic polynomial time Turing machine FII′ that outputs two ciphertexts (V∗,W,c∗) and (V∗,W∗,c∗) on the same message m. Thus, we can get W·P=Rt+lt·Ppub+ht′·PVt+htV and W∗·P=Rt+lt·Ppub+ht′·PVt+ht∗V. Let V=bP. We can obtain the following value. (13)W·P-W∗·P=htV˙-ht∗·V⟹W-W∗·P=ht-ht∗·V⟹W-W∗·P=ht-ht∗·bP⟹W-W∗=ht-ht∗·b⟹W-W∗(˙ht-ht∗)-1=b.Therefore, C solves the ECDLP as b=(W-W∗)(˙ht-ht∗)-1 for the ECDLP problem.
In the above forgery query, the receiverIDB can be ∅ for the signature mode; otherwise it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Let E1, E2, and E3 be the events when C aborts the game.
(i)E1 is an event in which the target identity IDt’s secret value is queried by FII. The probability of E1 is Pr[E1]=qsv/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by FII. The probability of E2 is Pr[E1]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the sender by FII during forgery. The probability of E3 is Pr[E3]=1-1/(qH0-qsk-qsv).
Thus,C does not abort the EUF-CLGSC-CMA-II game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).
So, the successful advantage ofC is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).


## 4.1. Confidentiality

Theorem 5.
The CLGSC scheme is semantically secure against adaptive chosen ciphertext attacks in encryption mode or signcryption mode in the random oracle model.Theorem5 is proved based on Lemmas 6 and 7.Lemma 6.
If an adversaryAI has a nonnegligible advantage ε against the IND-CLGSC-CCA2-I security of our scheme and performing qHi queries to oracles Hi(i=0,1,2), qppk Extract-Partial-Private-Key queries, and qsk Set-Private-Key queries, then there is an algorithm that solves the ECDLP problem with probability ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk))·1/qH1.Proof.
Given an instance of the ECDLP problem, for groupGq generated by P and a fixed second point Q(=aP) having as input R(=bP)∈Gq, C has to compute for the point S(=cP)∈Gq such that c=ab(mod⁡q) with the help of a ODDH oracle. Suppose the IND-CLGSC-CCA2-I security of the CLGSC can be violated by a Type I adversary AI. C can utilize AI to compute abP as the solution to this instance by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=s·P. It sendsparams to AI and maintains lists Li(0≤i≤2) to keep the consistency between the responses to the hash queries and a list Lk of issued keys which are initially empty. C selects t randomly, where 1≤t≤qH0, and takes IDt as the target identity. C chooses et,xt∈RZq∗ and sets H0(IDt,Rt,PVt)=-et, Rt=etPpub+aP-xtP, and PVt=xtP. C inserts (IDt,Rt,PVt,-et) into the list L0 and (IDt,⊥,xt,Rt,PVt) into the list Lk.
C answers AI’s queries to random oracles Hi(0≤i≤2) as follows.
(i)H0queries: when AI submits a H0 query with (IDi,Ri,PVi) for some i∈[1,q0], C checks in L0, and if (IDi,Ri,PVi,-ei) exists, C returns -ei. Otherwise, C chooses ei∈RZq∗ and returns -ei to AI. Then C inserts (IDi,Ri,PVi,-ei) into the list L0.
(ii)H1queries: when AI submits a H1 query with (Vi,Ti,Yi,IDi) for some i∈[1,q1], C sets the tuple (aP,Vi,Ti) as the input of ODDH orale. If the output of ODDH oracle is 1, then C returns Ti as the solution abP and stops; else C searches in L1, if (Vi,∗,Yi,IDi,li) exists, it replaces the symbol ∗ with Ti and returns li. Otherwise, C chooses li∈R0,1n and returns li to AI. Then C inserts (Vi,Ti,Yi,IDi,li) into the list L1.
(iii)H2queries: when AI submits a H2 query with (IDi,mi,Vi,Ti,PVi/Ri) for some i∈[1,q2], C checks in L2, and if (IDi,mi,Vi,Ti,PVi/Ri,hi) exists in L2, C returns hi. Otherwise, C chooses hi∈RZq∗ and returns hi to AI. Then C inserts (IDi,mi,Vi,Ti,PVi/Ri,hi) into L2.
C can answer AI’s other queries as follows.
Phase I
(i) Set-User-Key Queries. AI requests a secret value of the user with IDi. If the public key of IDi has not been replaced, then C responds with xi by retrieving from the list Lk.
(ii) Extract-Partial-Private-Key Queries. AI requests the partial private key of a user with IDi. If IDi=IDt, C aborts the execution. Otherwise, C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns di. Otherwise, C computes the partial private key of IDi by using the actual Extract-Partial-Private-Key algorithm, and C inserts (IDi,di,xt,Ri,PVi) into the list Lk and returns di.
(iii) Set-Private-Key Queries. AI requests a user’s full private key with IDi. C aborts the execution when IDi=IDt. Otherwise, C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns the corresponding private key (xi,di). Otherwise, C picks ei,bi,xi∈RZq∗, then sets H0(IDi,Ri,PVi)=-ei, Ri=eiPpub+biP, and computes PVi=xiP·di=bi and it satisfies the equation diP=Ri+H0(IDi,Ri,PVi)Ppub. C returns (xi,di) to AI and inserts (IDi,Ri,PVi,-ei) into the list L0 and (IDi,di,xi,Ri,PVi) into Lk.
(iv) Set-Public-Key Queries. AI requests a user’s public key with IDi. C checks in Lk, and if (IDi,di,xi,Ri,PVi) exists, C returns the corresponding public key (Ri,PVi). Otherwise, C picks ei,bi,xi∈RZq∗, then sets H0(IDi,Ri,PVi)=-ei, Ri=eiPpub+biP, and computes the public key as PVi=xiP·di=bi and it satisfies the equation diP=Ri+H0(IDi,Ri,PVi)Ppub. C returns (PVi,Ri) to AI and inserts (IDi,Ri,PVi,-ei) into the list L0 and (IDi,di,xi,Ri,PVi) into Lk.
(v) Public-Key-Replacement Queries. AI requests to replace a user’s public key (Ri,PVi) with chosen values (IDi,Ri′,PVi′). C updates corresponding tuple with (IDi,-,-,Ri′,PVi′).
(vi) CLGSC-Signcrypt Queries. AI sends the tuple (IDA,PVA,RA,IDB,PVB,RB,m) to C. For each query (IDA,IDB), if IDA≠IDt, C executes the Set-Private-Key algorithm to compute SKA corresponding to IDA. Then, C gets the ciphertext δ by running the actual CLGSC-signcrypt algorithm. C sends δ to AI. If IDA=IDt (and hence, IDB≠IDt), C can obtain the full private key SKB corresponding to IDB. C computes V=rP-ht-1·ap, T=V·(xB+dB), sets H2(IDA,m,V,T,PVA)=ht′, H2(IDA,m,V,T,RA)=ht, and adds the tuples (IDA,m,V,T,PVA,ht′) and (IDA,m,V,T,RA,ht) to the list L2 in which r,ht,ht′∈RZq∗. C computes c=H1(V,T,sBV,IDB)·f(IDB)⊕m and W=r·ht+xA·ht′-xA. C outputs (IDA,IDB,δ=(V,W,c)) as the ciphertext.
The tuple(IDA,IDB,δ=(V,W,c)) can pass the verification as the valid ciphertext because the equality holds as follows: (10)RA+H0IDA,RA,PVA·Ppub+PVA·H2IDA,m,V,T,PVA+V·H2IDA,m,V,T,RA=etPpub+aP-xtP+-etPpub+xtP·ht′+rP-ht-1aP·ht=r·ht+xtht′-xt·P=W·P.
(vii) CLGSC-Unsigncrypt Queries. AI submits (IDA,IDB,δ) to C. If IDB≠IDt, C obtains the receiver’s private key and returns the output of CLGSC-unsigncrypt algorithm to AI. Note that if the receiver’s public value is replaced, C may not obtain the receiver’s secret value. In this case, receiver’s secret value is requested to be provided by A. Otherwise, C searches in L2 for (IDA,m,V,T,PVA,hi) and (IDA,m,V,T,RA,hi′). If the entries exist and the equality W·P=RA+H0(IDA,RA,PVA)·Ppub+PVA·hi+V·hi′ holds, T is retrieved. If C can find a tuple (V,T,Y,IDB,l) in L1 making the ODDH oracle return 1 when queries are on (ap,V,T), then the message is c⊕l.
Challenge. AI submits (m0,m1,IDA∗,IDB∗) in which m0 and m1 are distinct messages of equal length and IDA∗ and IDB∗ are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AI must have made no Set-Private-Key queries on IDB∗ in PhaseI. It is also to be noted that IDB∗’s partial private key has not been extracted and his public key has not been replaced simultaneously. C aborts the game if IDB∗≠IDt. Otherwise, C generates the challenge ciphertext as follows.(1)
It setsV∗=bP and chooses T∗∈RGq.(2)
It selects randomly a bitγ∈{0,1} and a random hash value h and sets c∗=mγ⊕h.(3)
It selectsW∗, satisfies the equation W∗P=RA+H0(IDA,RA,PVA)·Ppub+PVA·H2(IDA,m,V∗,T∗,PVA)+V∗·H2(IDA,m,V∗,T∗,RA), and sends δ∗=(V∗,W∗,c∗) to AI.
Phase II. AI asks queries adaptively again. In addition, the full private key for IDB∗ may not be extracted by AI and the partial private key for IDB∗ may not be extracted if the public key of IDB∗ has been replaced in PhaseI. Only after the public key PKA∗ or PKB∗ has been replaced, CLGSC-unsigncrypt query on δ with sender IDA∗ and receiver IDB∗ is allowed.
Guess. Since AI is able to break the IND-CLGSC-CCA2-I security of the CLGSC, a H1 query with (V∗,T∗,Y∗,IDB∗) should have been asked. Note that T∗=b·(H0(IDB,RB,PVB)·Ppub+RB+PVB)=abP. Therefore, one of the T’s in L1 is the ECDLP problem’s solution. C chooses one T randomly and outputs it as the solution.
In the above challenge query, the sendersIDA and IDA∗ can be ∅ for the encryption mode; otherwise, it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Lets E1, E2, and E3 be the events when C aborts this game.
(i)E1 is an event in which the target identity IDt’s partial private key is queried by AI. The probability of E1 is Pr[E1]=qppk/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by AI. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the receiver by AI during the challenge phase. The probability of E3 is Pr[E3]=1-1/(qH0-qppk-qsk).
Thus,C does not abort this game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).
C chooses the solution of ECDLP problem from L1’s probability of 1/qH1. So, the successful advantage of C is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk))·1/qH1.Lemma 7.
IfAII has nonnegligible advantage ε against the IND-CLGSC-CCA2-II security of our scheme and performing qsv Extract-Secret-Value queries, qsk Set-Private-Key queries, and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm that solves the ECDLP problem with probability ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).Proof.
Given an instance of the ECDLP problem, for groupGq generated by P and a fixed second point Q(=aP) having as input R(=bP)∈Gq, C has to compute for the point S(=cP)∈Gq such that c=ab(mod⁡q) with the help of a ODDH oracle. Suppose the IND-CLGSC-CCA2-II security of the CLGSC can be violated by a TypeII adversary AII. C can utilize AII to compute abP as the solution to this instance by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=s·P. C sendsparams and s to AII and maintains lists Li(0≤i≤2) to avoid the inconsistency between the responses to the hash queries and a list Lk of issued keys which is initially empty. C selects t randomly, where 1≤t≤qH0, and fixes IDt as the target identity. C chooses at,lt∈RZq∗, sets H0(IDt,Rt,PVt)=lt, and computes Rt=atP,dt=at+lt·s, and the public key as PVt=aP. C inserts (IDt,Rt,PVt,lt) into the list L0 and (IDt,dt,⊥,Rt,PVt) into the list Lk.
C answers AII’s queries to random oracles Hi(0≤i≤2) as follows:
(i)H0queries: when AII submits a H0 query with (IDi,Ri,PVi) for some i∈[1,q0], C checks if there exists a tuple (IDi,Ri,PVi,li) in L0. If such a tuple exists, C answers with li. Otherwise, C chooses li∈RZq∗ and returns li as the answer. Then C inserts (IDi,Ri,PVi,li) into the list L0.
(ii)H1queries: when AII submits a H1 query with (Vi,Ti,Yi,IDi), where i∈[1,q1], C sets the tuple (aP,Vi,Yi) as the input of ODDH oracle. If the output of ODDH oracle is 1, then C outputs Yi as the solution; else C searches L1 with entries (Vi,Ti,∗,IDi,li). If such a tuple exists, it replaces the symbol ∗ with Yi and returns li. Otherwise, C chooses li∈R0,1n, inserts (Vi,Ti,Yi,IDi,li) into L1, and returns li to AII.
(iii)H2queries: when AII submits a H2 query with (IDi,mi,Vi,Ti,PVi/Ri), where i∈[1,q2], C checks whether (IDi,mi,Vi,Ti,PVi/Ri,hi) exists in L2. If it exists, C returns hi. Otherwise, C chooses hi∈RZq∗, inserts (IDi,mi,Vi,Ti,PVi/Ri,hi) into L2, and returns hi.
C can answer AII’s other queries as follows.
Phase I
(i) Set-User-Key Queries. AII requests a user’s secret value with IDi. If IDi=IDt, C aborts. If IDi≠IDt, C checks for a tuple (IDi,di,xi,Ri,PVi) in Lk. If it exists, C returns xi. Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and the public key as PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns xi.
(ii) Set-Private-Key Queries. AII produces IDi to C and requests a user’s private key with IDi. If IDi=IDt, C aborts. Otherwise, C checks for a tuple (IDi,di,xi,Ri,PVi) in Lk. If it exists, C returns (xi,di). Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns (xi,di).
(iii) Set-Public-Key Queries. AII requests a user’s public key with IDi. C checks for a tuple (IDi,di,xi,Ri,PVi). If it exists, C returns the corresponding public key (PVi,Ri). Otherwise, C chooses ai,xi,li∈RZq∗, then sets H0(IDi,Ri,PVi)=li, and computes Ri=aiP, di=ai+li·s, and the public key as PVi=xiP. C inserts (IDi,Ri,PVi,li) into the list L0 and (IDi,di,xi,Ri,PVi) into the list Lk and returns (PVi,Ri).
(iv) CLGSC-Signcrypt Queries. AII sends the tuple IDA,PVA,RA,IDB,PVB,RB,m to C. For each query (IDA,IDB), if IDA≠IDt, C executes the Set-Private-Key algorithm to compute SKA corresponding to IDA. Then, C gets the ciphertext δ by running the actual CLGSC-signcrypt algorithm. C sends δ to AII. If IDA=IDt (and hence, IDB≠IDt), C can obtain the full private key SKB corresponding to IDB. C computes V=rP-ht-1ht′·ap, T=V·(xB+dB), sets H2(IDA,m,V,T,PVA)=ht′, H2(IDA,m,V,T,RA)=ht, and adds the tuples (IDA,m,V,T,PVA,ht′) and (IDA,m,V,T,RA,ht) to the list L2 in which r,ht,ht′∈RZq∗. C computes c=H1(V,T,sBV,IDB)·f(IDB)⊕m and W=r·ht+dt. C outputs (IDA,IDB,δ=(V,W,c)) as the ciphertext.
The tuple(IDA,IDB,δ=(V,W,c)) can pass the verification as the valid ciphertext because the equality holds as follows: (11)RA+H0IDA,RA,PVA·Ppub+PVA·H2IDA,m,V,T,PVA+V·H2IDA,m,V,T,RA=atP+ltP+aPht′+rP-ht-1aP·ht=r·ht+at+slt·P=r·ht+dt·P=W·P.
(v) CLGSC-Unsigncrypt Queries. AII submits (IDA,IDB,δ) to C. If IDB≠IDt, C obtains the receiver’s private key, runs the CLGSC-unsigncrypt algorithm, and returns the output of CLGSC-unsigncrypt to AII. Otherwise, C searches in L2 for (IDA,m,V,T,PVA,hi′) and (IDA,m,V,T,RA,hi). If the entries exist and the equality W·P=RA+H0(IDA,RA,PVA)·Ppub+PVA·hi′+V·hi holds, T is retrieved. If C can find a tuple (V,T,Y,IDB,l) in L1 making the ODDH oracle return 1 when queries are on (ap,V,Y), then the message is c⊕l.
Challenge. AII submits (m0,m1,IDA∗,IDB∗) in which m0 and m1 are distinct messages of equal length and IDA∗ and IDB∗ are the sender’s and the receiver’s identities, respectively. Here, it is to be noted that AII must have made no Set-Private-Key queries on IDB∗ in PhaseI. C aborts the game if IDB∗≠IDt. Otherwise, C generates the challenge ciphertext as follows. (1)
It setsV∗=bP, where bP is given in the instance of the ECDLP problem and computes T∗=(xB∗+dB∗)·V∗.(2)
It selects randomly a bitγ∈{0,1} and h as a random hash value and sets c∗=mγ⊕h.(3)
It selectsW∗, satisfies the equation W∗P=RA+H0(IDA,RA,PVA)·Ppub+PVA·H2(IDA,m,V∗,T∗,PVA)+V∗·H2(IDA,m,V∗,T∗,RA), and sends δ∗=(V∗,W∗,c∗) to AII.
Phase II. AII asks queries adaptively again. In addition, it cannot query CLGSC-unsigncrypt on δ∗.
Guess. Since AII is able to break the IND-CLGSC-CCA2-II security of the CLGSC, a H1 query with (V∗,T∗,Y∗,IDB∗) should have been asked. Note that Y∗=xB∗·V∗=abP. Therefore, one of the qH1 values of Y∗ in L1 is the ECDLP problem’s solution. C chooses one Y∗ randomly and outputs it as the solution.
In the above challenge query, the sendersIDA and IDA∗ can be ∅ for the encryption mode; otherwise, it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. In order to assess the probability of success of the challenger, C lets E1, E2, and E3 be the events in which C aborts the IND-CLGSC-CCA2-II game.
(i)E1 is an event in which AII asks to query the secret value of the target identity IDt. The probability of E1 is Pr[E1]=qsv/qH0.
(ii)E2 is an event in which AII asks to query the private key of the target identity IDt. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the receiver by AII during the challenge. The probability of E3 is Pr[E3]=1-1/(qH0-qsk-qsv).
Thus,C does not abort the IND-CLGSC-CCA2-II game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).
So, the successful advantage ofC is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).


## 4.2. Unforgeability

Theorem 8.
The CLGSC scheme in signcryption mode or signature mode is existentially unforgeable.Theorem8 is proved based on Lemmas 9 and 10.Lemma 9.
If an adversaryFI has nonnegligible advantage ε against the EUF-CLGSC-CMA-I security of our scheme and performing qppk Extract-Partial-Private-Key queries, qsk Set-Private-Key queries, and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm that solves the ECDLP problem with probability ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).Proof.
Given an instance of the ECDLP problem(P,bP)∈Gq, C must find b. Suppose the EUF-CLGSC-CMA-I security of the CLGSC can be violated by a forger FI. C can utilize FI to compute b as the solution by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=sP; it sendsparams to FI and maintains lists Li(0≤i≤2) to keep consistency between the responses to the hash queries and a list Lk of issued keys which is initially empty.
Training Phase. FI may make a series of queries and all of the queries are responded to identically as those queries in the IND-CLGSC-CCA2-I game.
Forgery. FI returns a valid ciphertext from the sender IDA to the receiver IDB. If IDA≠IDt, C aborts the execution of this game. We are ready to apply the forking lemma [31] that essentially says the following: consider the concrete scheme producing signatures (m,V,h,W) or signcryption ciphertexts of the form (c,V,h,W), where each of V,h,W corresponds to one of the three moves of a honest-verifier zero-knowledge protocol. If FI is a sufficiently efficient forger in the above interaction and forges a signature or signcryption ciphertext (V,W,c) in a time t with probability ϵ⩾10(qsc+1)(qsc+qh)/2l (l being a security parameter so that h is uniformly taken from a set of 2l elements) when making qsc CLGSC-signcrypt queries and qh random oracle calls and if the triples (V,h,W) can be simulated without knowing the private key, then there exists a Turing machine F′ that uses FI to produce two valid ciphertexts (V∗,W,c∗) and (V∗,W∗,c∗) on the same message m, in expected time t′⩽120686qht/ϵ. Thus, we can get W·P=RA-et·Ppub+ht′·PVA+ht·V and W∗·P=RA-et·Ppub+ht′·PVA+ht∗·V. Let V=bP. We can obtain the following value.(12)W·P-W∗·P=htV˙-ht∗·V⟹W-W∗·P=ht-ht∗·V⟹W-W∗·P=ht-ht∗·bP⟹W-W∗=ht-ht∗·b⟹W-W∗(˙ht-ht∗)-1=b.Therefore, C solve the ECDLP as b=(W-W∗)(˙ht-ht∗)-1 for the ECDLP problem.
In the above forgery query, the receiverIDB can be ∅ for the signature mode; otherwise it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Let E1, E2, and E3 be the events when C aborts the game.
(i)E1 is an event in which the target identity IDt’s partial private key is queried by FI. The probability of E1 is Pr[E1]=qppk/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by FI. The probability of E2 is Pr[E2]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the sender by FI during the forgery. The probability of E3 is Pr[E3]=1-1/(qH0-qppk-qsk).
Thus,C does not abort the EUF-CLGSC-CMA-I game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).
So, the successful advantage ofC is ADVCELDLP=Pr[C(P,bP)=b]=ε·(1-qppk/qH0)·(1-qsk/qH0)·(1/(qH0-qppk-qsk)).Lemma 10.
If an adversaryFII has nonnegligible advantage ε against the EUF-CLGSC-CMA-II security of our scheme performing qsv Extract-Secret-Value queries and qHi queries to oracles Hi(i=0,1,2), then there is an algorithm C that solves the ECDLP problem with probability ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).Proof.
Given an instance of the ECDLP problem(P,bP), C must find b. Suppose the EUF-CLGSC-CMA-II security of the CLGSC can be violated by a forger FII. C can utilize FII to compute b as the solution by the following interactive game.
C chooses s∈RZq∗ uniformly as the master key and computes Ppub=sP; it sendsparams and s to FII and maintains lists Li(0≤i≤2) to keep consistency between the responses to the hash queries and a list Lk of issued keys which is initially empty.
Training Phase. FII may make a series of queries and all the queries are responded to identically as those queries in the IND-CLGSC-CCA2-II game.
Forgery. Eventually, FII returns a valid ciphertext from the sender IDA to the receiver IDB. If IDA≠IDt, C aborts the execution of this game. It follows from the forking lemma [31] that if FII is a sufficiently efficient forger in the above interaction, then we can construct another probabilistic polynomial time Turing machine FII′ that outputs two ciphertexts (V∗,W,c∗) and (V∗,W∗,c∗) on the same message m. Thus, we can get W·P=Rt+lt·Ppub+ht′·PVt+htV and W∗·P=Rt+lt·Ppub+ht′·PVt+ht∗V. Let V=bP. We can obtain the following value. (13)W·P-W∗·P=htV˙-ht∗·V⟹W-W∗·P=ht-ht∗·V⟹W-W∗·P=ht-ht∗·bP⟹W-W∗=ht-ht∗·b⟹W-W∗(˙ht-ht∗)-1=b.Therefore, C solves the ECDLP as b=(W-W∗)(˙ht-ht∗)-1 for the ECDLP problem.
In the above forgery query, the receiverIDB can be ∅ for the signature mode; otherwise it works as signcryption. Thus, the proof is suitable for the two modes.
Analysis. Let E1, E2, and E3 be the events when C aborts the game.
(i)E1 is an event in which the target identity IDt’s secret value is queried by FII. The probability of E1 is Pr[E1]=qsv/qH0.
(ii)E2 is an event in which the target identity IDt’s private key is queried by FII. The probability of E2 is Pr[E1]=qsk/qH0.
(iii)E3 is an event in which the target identity IDt has not been chosen as the sender by FII during forgery. The probability of E3 is Pr[E3]=1-1/(qH0-qsk-qsv).
Thus,C does not abort the EUF-CLGSC-CMA-II game’s probability of Pr[¬E1∧¬E2∧¬E3]=(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).
So, the successful advantage ofC is ADVCOGDH=Pr[C(P,aP,bP)=abP]=ε·(1-qsv/qH0)·(1-qsk/qH0)·(1/(qH0-qsk-qsv)).


## 5. Performance Analysis

Since computation time and ciphertext size are two important factors affecting efficiency, we compare our scheme with several existing schemes in these two terms from two aspects: CLGSC-signcrypt and CLGSC-unsigncrypt. We pay attention to operations such as bilinear pairing operations, exponentiation operations, scalar multiplication operations, and hash operations. We define the notations in the Notations section and adopt the experiment testing results from [32–34].The comparison is shown in Table1; G1 denotes the size of an element in G1, G2 denotes the size of an element in G2, m denotes the length of message m, ID denotes the length of identity ID, and q is the size of an element in Zq∗.Table 1
Comparisons of the computational overhead and storage costs.
Schemes Ciphertext size CLGSC-signcrypt time CLGSC-unsigncrypt time [24] 2 G 1 + m + I D + G 2 + q ( 3 T E + 2 T M + 4 T H ) ≈ 188.5  T M u l ( T E + T M + 4 T H + 2 T P ) ≈ 246.5  T M u l [25] 2 G 1 + m + I D + G 2 ( 2 T E + 3 T M + 3 T H ) ≈ 174  T M u l ( T E + 3 T M + 3 T H + 2 T P ) ≈ 304.5  T M u l [26] 2 G 1 + m ( T E + 4 T M + 3 T H + T P ) ≈ 246.5  T M u l ( T M + 3 T H + 5 T P ) ≈ 464  T M u l [27]∗ 2 G 1 + q + m 7 T M + 7 T H ≈ 203 T M u l 8 T M + 7 T H ≈ 232  T M u l Ours 2 G q + m ( 5 T M + 4 T H ) ≈ 145  T M u l ( 4 T M + 4 T H ) ≈ 116  T M u l N o t e   ∗ that the authors also considered the private key exposure problem in their paper.Since the pairing and exponentiation operations require much more time than the multiplication operation, our proposed scheme is implemented without pairing and exponentiation operations. From Table1, it shows that our proposed CLGSC scheme requires much less computational time than the other four schemes. So, our scheme has the shortest ciphertext size and is of high efficiency too.


## 6. Conclusion

In this paper, a concrete CLGSC scheme without utilizing bilinear pairing operations is proposed, and its security is proved in the random oracle model under the ECDLP and ECDLP assumptions, including security against both an adaptively chosen ciphertext attack and an existential forgery of TypeI andII adversaries. The new scheme is computationally efficient and is suitable for low power and processor devices.



---

*Source: 3578942-2018-05-15.xml*