# CLE against SOA with Better Data Security Storage to Cloud 5G

Authors: Huige Wang; Xing Chang; Kefei Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Cloud 5G and Cloud 6G technologies are strong backbone infrastructures to provide high data rate and data storage with low latency for preserving QoS (Quality of Service) and QoE (Quality of Experience) in applications such as driverless vehicles, drone-based deliveries, smart cities and factories, remote medical diagnosis and surgery, and artificial-intelligence-based personalized assistants. There are many techniques to support the aforementioned applications, but for privacy preservation of Cloud 5G, the existing methods are still not sufficient. Public key encryption (PKE) scheme is an important means to protect user data privacy in Cloud 5G. Currently, the most common PKE used in Cloud 5G is CCA or CPA secure ones. However, its security level maybe not enough. SOA security is a stronger security standard than CPA and CCA. Roughly speaking, PKE with SOA security means that the adversary is allowed to open a subset of challenger ciphertexts and obtains the corresponding encrypted messages and randomness, but the unopended messages and randomness remain secure in the rest of the challenger ciphertexts. Security against SOA in PKEs has been a research hotspot, especially with the wide discussion in Cloud 5G. We revisited the SOA-CLE and proposed a new security proof, which is more concise and user friendly to understand privacy preservation in Cloud 5G applications.


---

## Body

## 1. Introduction

Cloud 5G achieves high data transmission speed, large data storage, and low latency mobile communication. According to the inherent property of electromagnetic waves: the higher the frequency, the shorter the wavelength, so it tends to propagate like a straight line. From the last few years, we have witnessed a paradigm shift with a major focus on mission critical applications and ultra-reliable low latency applications (URLCC) such as AR/VR, autonomous vehicles, e-healthcare, smart education, and so on, the aim of which is to provide QoS (Quality of Service) and QoE (Quality of Experience) to the end users with high data storage and low latency. Starting from driverless vehicles and drone-based deliveries, smart cities and factories, remote medical diagnosis and surgery, and artificial-intelligence-based personalized assistants, there is enormous number of applications around us which require strong network backbone infrastructure for QoS and QoE preservation. Based on the above applications and the advantages in Cloud 5G, in the years to come, Cloud 5G and Cloud 6G technologies are expected to provide high data rate with low latency and large data storage for preserving QoS and QoE. Although there are many techniques in the literature which can resolve these issues, the existing methods are still not sufficient to privacy preservation in the application in Cloud 5G. Hence, secure protocols and encryption schemes are required to resolve the aforementioned issues. Public key encryption (PKE) scheme is an important means to protect user data privacy in Cloud 5G. Currently, the most commonly used means to protect user data privacy is CPA (chosen-plaintext attacks) or CCA (chosen-ciphertext attacks) secure PKEs where the latter provides the decryption queries and thus is stronger than the former. However, SOA is a stronger security standard than CCA because the SOA security allows additional opening partial ciphertexts. Specially, in particular, due to the inherent advantages of certificateless public key (CLE), it solves the certificate management problem in the traditional public key cryptography and the key-escrow problem [8] in IBE schemes. Security against SOA in CLEs has been a research hotspot, especially with the wide discussion in Cloud 5G [11, 12]. In this paper, we focus on the research on the SOA secure CLE.The definition of SOA was first proposed by Dwork et al. at FOCS99 [4], which is an important target to measure the security of PKE. SOA security mainly applies to multiple-user settings where a subset of the challenge ciphertexts is allowed to open for the adversary. From the opened ciphertexts, the adversary can get not only the message but also the randomness. The question that we want to solve is how to make the remaining unopened ciphertexts secure? Following Dwork’s work, SOA secure IBE and public key encryption (PKE) with SOA security have been widely developed [2, 5, 7]. CLE is another form of public key encryption system. Compared with IBE and PKE, CLE has the advantages of removing the certificate management in PKI-based PKE and key escrow in IBE. However, the study on CLE with SOA security is still rare.


### 1.1. Motivation

In the CLE system, a user’s private key is jointly generated by the KGC and the user. The user’s public key is generated by using the secret value generated by itself instead of the identity information. Obviously, compared with PKI-based PKE (hereafter, we abbreviated “PKI-based PKE” as “PKE”) and IBE, CLE removes the disadvantages that exist in both schemes, namely, the certificate transaction in PKE and key escrow in IBE. Due to the merits of this notion, many CLEs with various security models (e.g., IND-CPA [9] and IND-CCA [1, 13]) were presented. As in PKE and IBE settings, implementing SOA security in CLE is also important. However, the particular security model makes constructing CLEs with SOA security more intractable. With more and more applications for CLE (such as cloud computing), implementing SOA security in CLE becomes more and more critical. In 2016, Wang et al. proposed an SOA secure CLE [14] under the standard DDH assumptions where the scheme is user friendly in construction and more efficient in practical applications. Recently, the relative discussions about Cloud 5G have become a new research focus, especially its data security and privacy protection. Due to the notable efficiency and security level, SOA secure CLE has been regarded as one of the most practical candidate encryption algorithms for Cloud 5G. However, we find that there are still some disadvantages needed to avoid such as complex security proof and obscure proof process. Based on this, we revisited the scheme in [14] and improved the security proof to make it more concise and easier to understand.


### 1.2. Reviewing the Contribution in [14]

In the scheme of [3], the authors proposed a one-sided publicly opening identity-based encryption scheme (1SPO-IBE) and, based on which, constructed an IBE scheme with SOA security. Adopting the similar method, the authors in [14] resolved the SOA security in CLE. More concretely, they first proposed a one-sided publicly opening certificateless encryption scheme (1SPO-CLE). Then, based on the proposed 1SPO-CLE, they presented a CLE scheme that is SOA secure in the case of two-type adversary model (i.e., CLE security model where an adversary refers to a user who is granted the ability to change the public key but does not know the master key; another one means the malicious KGC, who is not granted the ability to change the public key but knows the master secret key). The core idea is that we first combined one-bit CLE and 1SPO to generate a 1SPO-CLE with IND-CPA security in the CLE settings and then showed that a multi-bit CLE scheme with SOA security can be constructed from the 1SPO-CLE scheme under the one-time signature and CDH assumptions.


### 1.3. Revisiting the Reduction from SOA to CPA in [14]

In [14], the authors constructed an IND-CPA secure 1SPO-CLE scheme by combining the 1SPO and one-bit CLE scheme. A CLE scheme that encrypts 1 bit messages is called 1SPO if it is possible, given the public parameter par, public key PKid, and the ciphertext c that encrypts message 0 with the randomness r to efficiently open the ciphertext c into another randomness used to encrypt message 1. In particular, the opening process is required to be done without any secret information. Furthermore, they proved that if the 1 bit 1SPO-CLE is IND-CPA secure, then the multi-bit CLE from it is SOA secure. Specifically, the encryption process is performed as follows. If the message is 1, then the encryption process follows specific rules and the correctness of the resulted ciphertext can be checked with some secret information; otherwise, the generated ciphertext is sampled randomly and uniformly from the ciphertext space. As stated in [3], the domain used as the ciphertext space is also required to have the property of sampleability and invertible sampleability in order to guarantee that the resulted scheme has the property of 1SPO.


### 1.4. Revisiting 1SPO-CLE Construction in [14]

In [14], the authors gave a concrete construction based on one-time signature and CDH assumptions. Specifically, the 1SPO-CLE is designed as follows. Assume G1 and G2 are both sampleable and invertibly sampleable domains as in [3]. If the encrypted message is 1, then the encryption of 1 is processed as c=c1,c2,σ,svk⟵Encryptexpar,PKid,1, where par is the public parameter and PKid is the public key, and the first two values c1,c2 have certain structure and the value σ is a signature for certain medians generated in the encryption, while the last value svk is the signature verification key. If the encrypted message is 0, then the first three elements of its encryption are all random. In particular, if c is an encryption of 1, then the medians u, K, and r can be always correctly recovered from c with the private key SKid. Then, using these medians and the output of the equations sign⋅Versvk,σ,u,id=1 and uxid=PKidH2KPKidid, the decryption algorithm Decrypexpar,c,SKid decides whether the ciphertext c encrypts 0 or 1, where xid is the secret value.


### 1.5. Revisiting the Security Proof of IND-CPA [14]

In this paper, we revisited the IND-CPA security proof of the 1 bit 1SPO-CLE scheme. Since the security proof in [14] is long and unintelligible, we do not intend to describe the difference between their scheme and ours. Below, we will directly describe our proof ideas and proof process. IND-CPA security means that given a ciphertext, no PPT adversary could distinguish which bit has been encrypted even if the adversary has the ability to replace public key or knows the master key (i.e., type 1 adversary and type 2 adversary) in the SOA security game. We present the proof of IND-CPA security for our concrete construction (for 1SPO-CLE scheme) under the two types of attacks defined in CLE. Briefly, under type 1 attack (where the adversary is granted the ability to change the public key but does not know the master key), we reduce the IND-CPA security to the assumption of one-time signature, where the reduction (the adversary that breaks one-time signature) performs the simulation itself except that the signature part is constructed by querying its signing oracle. However, unfortunately, under type 2 attack (where the adversary knows the master key but cannot change the public key), when we try to complete the reduction from the IND-CPA security to the CDH assumption, some obstacles arise. Namely, in the construction of challenge ciphertext, since the value r, as the exponent part of the challenge gr, is unknown to the CDH adversary, it results in that the c1=rQid∗P+rPpub part cannot be computed. Luckily, we find a way to solve this problem. Specifically, we do this by allowing the reduction algorithm (the CDH adversary) to query its CDH challenger to obtain c1. Of course, to do this, we assume that computing r from rP is not easier than computing r from gr. In fact, this can be done over the elliptic curve groups.


### 1.6. Other Related Work

We note that in the past few years, there emerged many remarkable SOA secure systems in PKE setting such as the schemes proposed by Bellare et al. [2], Fehr et al. [5], and Huang et al. [6]. Recently, SOA secure IBE also made rapid progress. In 2011, Bellare et al. [3] proposed two SO-CPA secure IBEs. In 2014, Lai et al. [10] proposed SO-CCA secure IBE using cross authentication codes. In 2016, Wang et al. proposed an SO-CPA secure CLE scheme [14] which avoids the problem of certificate management in PKE settings and key escrow in IBE settings. However, the security proof in [14] is complex and ambiguous.


### 1.7. Our Contribution

Our SO-CPA secure certificateless encryption scheme (CLE) is constructed based on the technique of one-sided public openability (1SPO) and one-bit CPA secure CLE. Specifically, by combining the techniques of 1SPO and one-bit CLE, we construct an IND-CPA secure 1SPO-CLE scheme. 1SPO means that given a system parameterpar, public key PKid, and a ciphertext c encrypting message 0 under randomness r, it enables to open the ciphertext c to another message and randomness pair 1,r′. This method is very challenging since the opening process does not need any secret key to participate in. Interestingly, by revisiting, we found that this method can provide us concise security proof in order to obtain the desired security. In particular, this design implies that 1 bit 1SPO-CLE with IND-CPA security implies multi-bit CLE with the same security. In more detail, the scheme is outlined as follows. If the encrypted message is 1, then its ciphertext preserves a certain structure and can be detected with some secret information. On the contrary, if the encrypted message is 0, its ciphertext takes on a random status and thus is not checkable due to its unstructured property. These properties described above are just what we need for revisiting the CLE with SO-CPA security in [14].


## 1.1. Motivation

In the CLE system, a user’s private key is jointly generated by the KGC and the user. The user’s public key is generated by using the secret value generated by itself instead of the identity information. Obviously, compared with PKI-based PKE (hereafter, we abbreviated “PKI-based PKE” as “PKE”) and IBE, CLE removes the disadvantages that exist in both schemes, namely, the certificate transaction in PKE and key escrow in IBE. Due to the merits of this notion, many CLEs with various security models (e.g., IND-CPA [9] and IND-CCA [1, 13]) were presented. As in PKE and IBE settings, implementing SOA security in CLE is also important. However, the particular security model makes constructing CLEs with SOA security more intractable. With more and more applications for CLE (such as cloud computing), implementing SOA security in CLE becomes more and more critical. In 2016, Wang et al. proposed an SOA secure CLE [14] under the standard DDH assumptions where the scheme is user friendly in construction and more efficient in practical applications. Recently, the relative discussions about Cloud 5G have become a new research focus, especially its data security and privacy protection. Due to the notable efficiency and security level, SOA secure CLE has been regarded as one of the most practical candidate encryption algorithms for Cloud 5G. However, we find that there are still some disadvantages needed to avoid such as complex security proof and obscure proof process. Based on this, we revisited the scheme in [14] and improved the security proof to make it more concise and easier to understand.


## 1.2. Reviewing the Contribution in [14]

In the scheme of [3], the authors proposed a one-sided publicly opening identity-based encryption scheme (1SPO-IBE) and, based on which, constructed an IBE scheme with SOA security. Adopting the similar method, the authors in [14] resolved the SOA security in CLE. More concretely, they first proposed a one-sided publicly opening certificateless encryption scheme (1SPO-CLE). Then, based on the proposed 1SPO-CLE, they presented a CLE scheme that is SOA secure in the case of two-type adversary model (i.e., CLE security model where an adversary refers to a user who is granted the ability to change the public key but does not know the master key; another one means the malicious KGC, who is not granted the ability to change the public key but knows the master secret key). The core idea is that we first combined one-bit CLE and 1SPO to generate a 1SPO-CLE with IND-CPA security in the CLE settings and then showed that a multi-bit CLE scheme with SOA security can be constructed from the 1SPO-CLE scheme under the one-time signature and CDH assumptions.


## 1.3. Revisiting the Reduction from SOA to CPA in [14]

In [14], the authors constructed an IND-CPA secure 1SPO-CLE scheme by combining the 1SPO and one-bit CLE scheme. A CLE scheme that encrypts 1 bit messages is called 1SPO if it is possible, given the public parameter par, public key PKid, and the ciphertext c that encrypts message 0 with the randomness r to efficiently open the ciphertext c into another randomness used to encrypt message 1. In particular, the opening process is required to be done without any secret information. Furthermore, they proved that if the 1 bit 1SPO-CLE is IND-CPA secure, then the multi-bit CLE from it is SOA secure. Specifically, the encryption process is performed as follows. If the message is 1, then the encryption process follows specific rules and the correctness of the resulted ciphertext can be checked with some secret information; otherwise, the generated ciphertext is sampled randomly and uniformly from the ciphertext space. As stated in [3], the domain used as the ciphertext space is also required to have the property of sampleability and invertible sampleability in order to guarantee that the resulted scheme has the property of 1SPO.


## 1.4. Revisiting 1SPO-CLE Construction in [14]

In [14], the authors gave a concrete construction based on one-time signature and CDH assumptions. Specifically, the 1SPO-CLE is designed as follows. Assume G1 and G2 are both sampleable and invertibly sampleable domains as in [3]. If the encrypted message is 1, then the encryption of 1 is processed as c=c1,c2,σ,svk⟵Encryptexpar,PKid,1, where par is the public parameter and PKid is the public key, and the first two values c1,c2 have certain structure and the value σ is a signature for certain medians generated in the encryption, while the last value svk is the signature verification key. If the encrypted message is 0, then the first three elements of its encryption are all random. In particular, if c is an encryption of 1, then the medians u, K, and r can be always correctly recovered from c with the private key SKid. Then, using these medians and the output of the equations sign⋅Versvk,σ,u,id=1 and uxid=PKidH2KPKidid, the decryption algorithm Decrypexpar,c,SKid decides whether the ciphertext c encrypts 0 or 1, where xid is the secret value.


## 1.5. Revisiting the Security Proof of IND-CPA [14]

In this paper, we revisited the IND-CPA security proof of the 1 bit 1SPO-CLE scheme. Since the security proof in [14] is long and unintelligible, we do not intend to describe the difference between their scheme and ours. Below, we will directly describe our proof ideas and proof process. IND-CPA security means that given a ciphertext, no PPT adversary could distinguish which bit has been encrypted even if the adversary has the ability to replace public key or knows the master key (i.e., type 1 adversary and type 2 adversary) in the SOA security game. We present the proof of IND-CPA security for our concrete construction (for 1SPO-CLE scheme) under the two types of attacks defined in CLE. Briefly, under type 1 attack (where the adversary is granted the ability to change the public key but does not know the master key), we reduce the IND-CPA security to the assumption of one-time signature, where the reduction (the adversary that breaks one-time signature) performs the simulation itself except that the signature part is constructed by querying its signing oracle. However, unfortunately, under type 2 attack (where the adversary knows the master key but cannot change the public key), when we try to complete the reduction from the IND-CPA security to the CDH assumption, some obstacles arise. Namely, in the construction of challenge ciphertext, since the value r, as the exponent part of the challenge gr, is unknown to the CDH adversary, it results in that the c1=rQid∗P+rPpub part cannot be computed. Luckily, we find a way to solve this problem. Specifically, we do this by allowing the reduction algorithm (the CDH adversary) to query its CDH challenger to obtain c1. Of course, to do this, we assume that computing r from rP is not easier than computing r from gr. In fact, this can be done over the elliptic curve groups.


## 1.6. Other Related Work

We note that in the past few years, there emerged many remarkable SOA secure systems in PKE setting such as the schemes proposed by Bellare et al. [2], Fehr et al. [5], and Huang et al. [6]. Recently, SOA secure IBE also made rapid progress. In 2011, Bellare et al. [3] proposed two SO-CPA secure IBEs. In 2014, Lai et al. [10] proposed SO-CCA secure IBE using cross authentication codes. In 2016, Wang et al. proposed an SO-CPA secure CLE scheme [14] which avoids the problem of certificate management in PKE settings and key escrow in IBE settings. However, the security proof in [14] is complex and ambiguous.


## 1.7. Our Contribution

Our SO-CPA secure certificateless encryption scheme (CLE) is constructed based on the technique of one-sided public openability (1SPO) and one-bit CPA secure CLE. Specifically, by combining the techniques of 1SPO and one-bit CLE, we construct an IND-CPA secure 1SPO-CLE scheme. 1SPO means that given a system parameterpar, public key PKid, and a ciphertext c encrypting message 0 under randomness r, it enables to open the ciphertext c to another message and randomness pair 1,r′. This method is very challenging since the opening process does not need any secret key to participate in. Interestingly, by revisiting, we found that this method can provide us concise security proof in order to obtain the desired security. In particular, this design implies that 1 bit 1SPO-CLE with IND-CPA security implies multi-bit CLE with the same security. In more detail, the scheme is outlined as follows. If the encrypted message is 1, then its ciphertext preserves a certain structure and can be detected with some secret information. On the contrary, if the encrypted message is 0, its ciphertext takes on a random status and thus is not checkable due to its unstructured property. These properties described above are just what we need for revisiting the CLE with SO-CPA security in [14].


## 2. Preliminary

In the following, we give several assumptions used in this paper.(i)
sign.Skg1λ: taking a security parameter 1λ as input, this algorithm outputs a signature/verification key pair ssk,svk.sign.Sigssk,m: on input signature key ssk and a message m∈ℳ, this algorithm outputs a signature σ.sign.Versvk,m,σ: on input a verification key svk, a signature σ and a message m, this algorithm outputs 1, if σ is valid, and 0 otherwise.Definition 1.
(discrete logarithm assumption (DL)). Assume thatG is a multiplicative group with prime order q and g∈G is a generator. Given g,y=ga, computing is difficult, where a⟵$0,…,q−1. Formally, for all probabilistic polynomial time (short for PPT) adversary A, there exists a negligible function negl such that AdvG,ADLλ=PrAg,y⟶a|g∈G,y=ga,a⟵$0,…,q−1≤neglλ, where neglλ is a negligible function in the security parameter λ.Definition 2.
(computational Diffie–Hellman assumption). Assume thatG is a cyclic group with prime order q and g∈G is a generator. Given g,ga,gb, computinggabis difficult, wherea,b⟵$0,…,q−1. Formally, for all PPT adversary A, there exists a negligible function negl such that: AdvG,ACDHλ=PrAg,ga,gb⟶gab|a,b⟵$0,…,q−1≤neglλ.Definition 3.
(one-time signature). Letℳ be message space, ℛ be randomness space, and S be the signature space. A signature scheme sign=sign.Skg,sign.Sig,sign.Ver consists of three (probabilistic) polynomial time algorithms:We say that a message/signature pairm,σ is valid if for all λ, all ssk,svk⟵sign.Skg1λ, all m∈ℳ, and all σ⟵sign.Sigssk,m, the equation sign.Versvk,m,σ=1 holds.We say that a signature schemesign=sign.Skg,sign.Sig,\\sign.Ver is one-time unforgeable under chosen-message attack if for any PPT adversary A, the success probability of A in the following experiment (see Figure 1) is negligible.Figure 1
OT-signature.


### 2.1. Detailed Legend for Figure1

This figure describes one-time unforgeability experiment for one-time signature denoted in Section2, where an adversary and a challenger participate in the experiment and interact with each other. Specifically, in this experiment, the challenger first invokes the algorithm ssk,svk⟵sign.Skg1λ to generate a pair of signature key and verification key ssk,svk. The signature key ssk is used to sign a message and the verification key svk is used to verify whether a given signature is valid. Given a verification key, the adversary outputs a message/signature forge pair m∗,σ∗ with multiple times of signature queries to oracle Ossksign.Sig·. When the message/signature forge does not belong to the queried items to oracle Ossksign.Sig· and the forge can verify, the experiment outputs 1 which denotes that the adversary wins the experiment. Particularly, the oracle Ossksign.Sig· means that when an adversary delivers a message m, the oracle returns a signature σ.In the above experiment, we allow the adversary to queryOssksign.Sig· oracle only one time. Assume that the adversary output a message/signature pair satisfying m∗,σ∗≠m,σ and sign.Versvk,m∗,σ∗=1. Then, we say that the adversary gives a successful forge. Formally, the scheme sign is unforgeable, if there exists a negligible function negl such that(1)Advsign,AotUFλ=PrExpsign,AotUFλ=1.Definition 4.
(efficiently sampleable and invertible domain3). Here, we define two PPT randomized algorithms that are sampleable and invertible, respectively:(i)
(efficient sampling) We say that a domainD is efficiently sampleable if there exists a PPT algorithm Sample s.t. x⟵SampleD;R is uniformly distributed over D for randomness R⟵RSample, where RSample is randomness space.(ii)
(efficient invertible sampling) We say that a domainD is efficiently invertible sampleable, if there exists a PPT invertible algorithm Sample−1 s.t. Sample−1D,x outputs R uniformly distributed over RSample for SampleD;R=x and any x∈D.Note that theSample algorithm has sampling failure probability ζ if the sampling algorithm Sample outputs ⊥ with probability at most ζ and invertible sampling failure probability θ if the invertible algorithm Sample−1 outputs ⊥ with probability at most θ.Definition 5.
(one-sided public openability (1SPO)). A scheme has the 1SPO property if for a ciphertextC=c0,c1 which is the encryption result of 0 under identity ID and public key PK, where c0 and c1 are randomly distributed over an efficiently sampleable and invertible domain G w.r.t. algorithms Sample and Sample−1, there exists an algorithm POpen To ZeroPK,ID,C=c0,c1 that can use the algorithm Sample−1 to open c0,c1. Namely, R0,R1⟵POpenPK,ID,c0,c1 with R0⟵Sample−1G,c0 and R1⟵Sample−1G,c1.


## 2.1. Detailed Legend for Figure1

This figure describes one-time unforgeability experiment for one-time signature denoted in Section2, where an adversary and a challenger participate in the experiment and interact with each other. Specifically, in this experiment, the challenger first invokes the algorithm ssk,svk⟵sign.Skg1λ to generate a pair of signature key and verification key ssk,svk. The signature key ssk is used to sign a message and the verification key svk is used to verify whether a given signature is valid. Given a verification key, the adversary outputs a message/signature forge pair m∗,σ∗ with multiple times of signature queries to oracle Ossksign.Sig·. When the message/signature forge does not belong to the queried items to oracle Ossksign.Sig· and the forge can verify, the experiment outputs 1 which denotes that the adversary wins the experiment. Particularly, the oracle Ossksign.Sig· means that when an adversary delivers a message m, the oracle returns a signature σ.In the above experiment, we allow the adversary to queryOssksign.Sig· oracle only one time. Assume that the adversary output a message/signature pair satisfying m∗,σ∗≠m,σ and sign.Versvk,m∗,σ∗=1. Then, we say that the adversary gives a successful forge. Formally, the scheme sign is unforgeable, if there exists a negligible function negl such that(1)Advsign,AotUFλ=PrExpsign,AotUFλ=1.Definition 4.
(efficiently sampleable and invertible domain3). Here, we define two PPT randomized algorithms that are sampleable and invertible, respectively:(i)
(efficient sampling) We say that a domainD is efficiently sampleable if there exists a PPT algorithm Sample s.t. x⟵SampleD;R is uniformly distributed over D for randomness R⟵RSample, where RSample is randomness space.(ii)
(efficient invertible sampling) We say that a domainD is efficiently invertible sampleable, if there exists a PPT invertible algorithm Sample−1 s.t. Sample−1D,x outputs R uniformly distributed over RSample for SampleD;R=x and any x∈D.Note that theSample algorithm has sampling failure probability ζ if the sampling algorithm Sample outputs ⊥ with probability at most ζ and invertible sampling failure probability θ if the invertible algorithm Sample−1 outputs ⊥ with probability at most θ.Definition 5.
(one-sided public openability (1SPO)). A scheme has the 1SPO property if for a ciphertextC=c0,c1 which is the encryption result of 0 under identity ID and public key PK, where c0 and c1 are randomly distributed over an efficiently sampleable and invertible domain G w.r.t. algorithms Sample and Sample−1, there exists an algorithm POpen To ZeroPK,ID,C=c0,c1 that can use the algorithm Sample−1 to open c0,c1. Namely, R0,R1⟵POpenPK,ID,c0,c1 with R0⟵Sample−1G,c0 and R1⟵Sample−1G,c1.


## 3. Extractable 1SPO-CLE

### 3.1. Extractable 1SPO-CLE

An extractable certificateless encryption consists of the following algorithms:(i)
Setup: the algorithm Setupex1λ takes a security parameter λ as input and outputs a master key msk and a public parameter par, where par defines an identity space v and ciphertext space Spacec.(ii)
Partial private key generation: the algorithm ParPrivKeyGenexpar,id,msk takes a public parameter par, an identity id∈Spaceid, and a master key msk as input and outputs the partial private key did.(iii)
Secret key generation: the algorithm SecValGenexpar,id takes an identity id and the public parameters par as input and outputs the secret value xid.(iv)
Private key generation: the algorithm PrivKeyGenexpar,did,xid takes the public parameter par, a user’s partial private key did, and secret value xid as input and outputs the private key SKid=did,xid.(v)
Public key generation: the algorithm PubKeyGenexpar,xid takes a public parameter par and a user’s secret value xid as input and outputs the user’s public key PKid.(vi)
Encryption: the algorithm Encryptexpar,m,PKid takes a public parameter par, a message m∈0,1, and a user’s public key PKid and returns the ciphertext c by using the defined algorithm if m=1; otherwise, it returns c by sampling randomly from the ciphertext space.(vii)Decryption: the algorithm Decryptexpar,c,SKid takes a public parameter par, a ciphertext c, and a private key SKid as input and outputs m∈0,1.(viii)Correctness: the correctness follows that in [14]; here we omitted it in order to save space.Definition 6.
(see [5] (1SPO-CLE)). An extractable 1SPO-CLE is a scheme with the property of one-sided public openability in the CLE setting and is associated with a PPT public algorithm POpen To Zero, so that for all par,msk⟵Setupex1k, c⟵Encryptexpar,0,PKid, PKid⟵PubKeyGenexpar,xid, xid⟵SecValGenexpar,id and id∈Spaceid, POpen To Zeropar,PKid,c distributes uniformly at random over Coinspar,PKid,c,0. Here, Coinspar,PKid,c,0 represent the set of random coins R|c=Encryptexpar,0,PKid;R.As described in [14], the multi-bit 1SPO-CLE can be constructed from 1 bit 1SPO-CLE. Since the concrete construction and security overlap with that in [14], here we do not dwell on it, but, for completeness, we describe it in Appendices A and B.


## 3.1. Extractable 1SPO-CLE

An extractable certificateless encryption consists of the following algorithms:(i)
Setup: the algorithm Setupex1λ takes a security parameter λ as input and outputs a master key msk and a public parameter par, where par defines an identity space v and ciphertext space Spacec.(ii)
Partial private key generation: the algorithm ParPrivKeyGenexpar,id,msk takes a public parameter par, an identity id∈Spaceid, and a master key msk as input and outputs the partial private key did.(iii)
Secret key generation: the algorithm SecValGenexpar,id takes an identity id and the public parameters par as input and outputs the secret value xid.(iv)
Private key generation: the algorithm PrivKeyGenexpar,did,xid takes the public parameter par, a user’s partial private key did, and secret value xid as input and outputs the private key SKid=did,xid.(v)
Public key generation: the algorithm PubKeyGenexpar,xid takes a public parameter par and a user’s secret value xid as input and outputs the user’s public key PKid.(vi)
Encryption: the algorithm Encryptexpar,m,PKid takes a public parameter par, a message m∈0,1, and a user’s public key PKid and returns the ciphertext c by using the defined algorithm if m=1; otherwise, it returns c by sampling randomly from the ciphertext space.(vii)Decryption: the algorithm Decryptexpar,c,SKid takes a public parameter par, a ciphertext c, and a private key SKid as input and outputs m∈0,1.(viii)Correctness: the correctness follows that in [14]; here we omitted it in order to save space.Definition 6.
(see [5] (1SPO-CLE)). An extractable 1SPO-CLE is a scheme with the property of one-sided public openability in the CLE setting and is associated with a PPT public algorithm POpen To Zero, so that for all par,msk⟵Setupex1k, c⟵Encryptexpar,0,PKid, PKid⟵PubKeyGenexpar,xid, xid⟵SecValGenexpar,id and id∈Spaceid, POpen To Zeropar,PKid,c distributes uniformly at random over Coinspar,PKid,c,0. Here, Coinspar,PKid,c,0 represent the set of random coins R|c=Encryptexpar,0,PKid;R.As described in [14], the multi-bit 1SPO-CLE can be constructed from 1 bit 1SPO-CLE. Since the concrete construction and security overlap with that in [14], here we do not dwell on it, but, for completeness, we describe it in Appendices A and B.


## 4. Proposed Extractable 1SPO-CLE

### 4.1. Construction

In this section, we describe the 1SPO-CPA secure 1-bit CLE scheme. We mainly focus on the following algorithms:Setup. The algorithm Setupex1λ first takes a security parameter λ as input and then runs a group generator GRλ to get a group description G1,G2,e,q. Here, G1 and G2 are both groups of prime order q, G1 is an additive group, and G2 is a multiplicative group. We also notice that both G1 and G2 are efficiently sampleable and invertible domain associated with algorithms Sample and Sample−1 shown in [3]. e:G1×G1⟶G2 is a non-degenerate bilinear map, and P is a non-zero generator of G1. Let H1:0,1l⟶Zq∗, H2:G1×G2×0,1l⟶Zq∗, H3:G22⟶G1 be three hash functions. Pick s⟵$Zq∗, set master key msk: = s, and compute Ppub=sP and g=eP,P∈G2. Let sign=sign.Skg,sign.Sig,sign.Ver be one-time signature scheme with signature space G2. Finally, the public parameter is set as par: = G1,G2,e,q,P,Ppub,g.Partial Private Key Generation. The algorithm ParPrivKeyGenexpar,id,msk first takes the public parameter par, an identity id∈0,1l, and the master secret key msk as input and proceeds as follows. It computes the partial private key did=1/s+H1idP∈G1. This can be done since if q is large enough, the probability that the unlikely event s+H1id=0modq happens is negligible.Secret Key Value Generation. The algorithm SecValGenexpar,id first takes the public parameters par and an identity id as input and then randomly selects a value xid⟵Zq∗ as the secret value.Private Key Generation. The algorithm PrivKeyGenexpar,did,xid first takes the public parameter par, the partial private key did, and the secret value xid as input and then returns SKid=did,xid as the private key.Public Key Generation. The algorithm PubKeyGenexpar,xid first takes the public parameter par and the secret value xid as input and then computes the public key PKid=gxid.Encryption. The algorithm Encryptexpar,m∈0,1,PKid first takes the public parameter par, a message m∈0,1, and the public key PKid as input. It then encrypts m as follows:First, check whetherPKidq≐1G2. If not, abort; otherwise, compute ssk,svk⟵sign.Skg1λ and proceed as follows.Ifm=1, pick K⟵$G1, compute r=H2K,PKid,id, c1=rH1idP+rPpub, σ=sign.Sigssk,gr,id∈G2, and c2=K+H3gr,PKidr.Ifm=0, pick c1⟵$SampleG1, c2⟵$SampleG1, and σ⟵$SampleG2.Finally, the ciphertext is set asc=c1,c2,σ,svk.Decryption. The algorithm Decryptexpar,c,SKid takes the public parameter par, a ciphertext c, and a private key SKid as input. To decrypt a ciphertext c=c1,c2,σ,svk, firstly compute u=ec1,did=gr and K=c2−H3u,uxid and verify whether sign.Versvk,σ,u,id=1 holds; if not, outputs ⊥; otherwise, verify whether uxid=PKidH2K,PKid,id holds; if so, set m=1; otherwise, m=0.Correctness. If c=c1,c2,σ,svk is the encryption of 1, then the equations u=ec1,did=erH1idP+rPpub,1/s+H1idP=gr, K=c2−H3u,uxid, sign.Versvk,σ,u,id=1, and uxid=PKidH2K,PKid,id hold, so the decryption always recovers 1. If c=c1,c2,σ,svk is the encryption of 0, since c1⟵$SampleG1, c2⟵$SampleG1 and σ⟵$SampleG2 are sampled uniformly and randomly. So, Prec1,didxid=PKidr=PKidH2K,PKid,id≤1/qλ (we assume that qλ is large enough which, in turn, results in a negligible quantity for 1/qλ).


### 4.2. Security

Theorem 1.
Assume the hash functionsH1,H2, andH3are random oracles, and the schemesign=sign.Skg,sign.Sig,sign.Veris one-time signature scheme. LetII′be extractable 1SPO-CLE scheme proposed in Section 4.1andG1andG2be PR-sampleable (pseudorandom-sampleable) with negligible sampling failure probability. LetA1andA2be any IND-CPA type 1 and type 2 adversaries against schemeII′, respectively, and are allowed to make polynomial times of queries toH2andH3; then, the schemeII′is IND-CPA secure under both type 1 adversary and type 2 adversary.Proof.
We first prove that, for type 1 adversary, the security can be reduced to the security of one-time signature schemesign and then prove that, for type 2 adversary, the security can be reduced to the computational Diffie–Hellman assumption (short for CDH). In the following, we describe the reduction between the adversary Asig (which tries to break the one-time signature scheme) and the type 1 adversary A1 and the reduction between the adversary Acdh (which tries to break the CDH assumption) and the type 2 adversary A2, respectively.


#### 4.2.1. Type 1 Adversary

Setup: the adversary Asig (which has the signing verification key svk) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A1.Partialprivatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, the adversary Asig invokes the partial private key generation algorithm to obtain the partial private key did and sends it to the adversary A1; otherwise it aborts. Concretely, the adversary Asig first queries the random oracle H1 to get Qid and then computes did=1/s+QidP∈G1. Note that the oracle H1 here is stateful and assume that all oracles in the following are stateful.Privatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, Asig first invokes the secret value generation algorithm and the partial private key generation algorithm to get the secret value xid and the partial private key did and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid; otherwise it aborts.Publickeyquery: on receiving the identity id, Asig first invokes the secret value generation algorithm to get xid and then computes the public key as PKid=gxid.Replacepublickeyquery: on receiving the identity id, Asig replaces the original public key PKid=gxid with the new public key PKid′=gxid′.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Asig computes challenge ciphertext as follows.First flip a coinb⟵$0,1 and then check whether PKid∗q≐1G2; if not, abort; otherwise, proceed as follows.Ifmb=1, do the following steps.(1)
First, pickK⟵$G1, and then for tuple K,PKid∗,id∗, query oracle H2 to get r.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Computegr and PKid∗r, and then for gr,PKid∗r, query oracle H3 to get h.(4)
Computec1=rQid∗P+rPpub and c2=K+h.(5)
Forgr,id∗, query signature oracle to get σ.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1 and σ⟵$SampleG2 at random. Then, the final challenge ciphertext is set as c=c1,c2,σ,svk.From above, we can see that the adversaryAsig provides perfect simulation for A1. Now we do the following analysis.Analysis: let the challenge ciphertext c=c1,c2,σ,svk. In the experiment, since A1 does not know did∗, it cannot compute the value u=gr. Assume A1 guess u′=gr′ randomly. Then, by the one-time signature scheme sign, the verification equation sign.Versvk,σ,u′,id∗=1 does not hold with overwhelming probability.


#### 4.2.2. Type 2 Adversary

Setup: the adversary Acdh (which has the challenge PKid∗,u=gr) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A2.Privatekeyquery: in this phase, If id∉ChID, where ChID is the challenge identity set, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and computes partial private key did, and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid.Publickeyquery: in this phase, if id∉ChID, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and then computes the public key as PKid=gxid; otherwise it aborts.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Acdh computes challenge ciphertext as follows. First sample a random b⟵$0,1, then check whether PKid∗q≐1G2; if not, abort; otherwise, compute ssk,svk⟵sign.Skg1λ and proceed as follows.Ifmb=1, do the following steps.(1)
Pickc2⟵$G1.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Query the CDH challenger to getc1, where c1 is computed as c1=rQid∗P+rPpub.(4)
Foru=gr,id∗, compute signature σ.(5)
Set the challenge ciphertext asc=c1,c2,σ,svk.From above, it is easy to see that we implicitly setr=H2K,PKid∗,id∗ for K=c2−h and h=H3gr,PKid∗r. In addition, we require here that computing r from rP is not easier than computing r from gr.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1, and σ⟵$SampleG2 at random.Then, set the challenge ciphertext asc=c1,c2,σ,svk.From above, we can see that the adversaryAcdh provides perfect simulations for the adversary A2. Now we do the following analysis.Analysis: let c=c1,c2,σ,svk be the challenge ciphertext. In the experiment, A2 knows u=gr and PKid∗; by the CDH assumption, it is still difficult to compute uxid∗ and K to make the verification equation uxid∗=PKid∗H2K,PKid∗,id∗ hold.This completes the proof of Theorem1.


## 4.1. Construction

In this section, we describe the 1SPO-CPA secure 1-bit CLE scheme. We mainly focus on the following algorithms:Setup. The algorithm Setupex1λ first takes a security parameter λ as input and then runs a group generator GRλ to get a group description G1,G2,e,q. Here, G1 and G2 are both groups of prime order q, G1 is an additive group, and G2 is a multiplicative group. We also notice that both G1 and G2 are efficiently sampleable and invertible domain associated with algorithms Sample and Sample−1 shown in [3]. e:G1×G1⟶G2 is a non-degenerate bilinear map, and P is a non-zero generator of G1. Let H1:0,1l⟶Zq∗, H2:G1×G2×0,1l⟶Zq∗, H3:G22⟶G1 be three hash functions. Pick s⟵$Zq∗, set master key msk: = s, and compute Ppub=sP and g=eP,P∈G2. Let sign=sign.Skg,sign.Sig,sign.Ver be one-time signature scheme with signature space G2. Finally, the public parameter is set as par: = G1,G2,e,q,P,Ppub,g.Partial Private Key Generation. The algorithm ParPrivKeyGenexpar,id,msk first takes the public parameter par, an identity id∈0,1l, and the master secret key msk as input and proceeds as follows. It computes the partial private key did=1/s+H1idP∈G1. This can be done since if q is large enough, the probability that the unlikely event s+H1id=0modq happens is negligible.Secret Key Value Generation. The algorithm SecValGenexpar,id first takes the public parameters par and an identity id as input and then randomly selects a value xid⟵Zq∗ as the secret value.Private Key Generation. The algorithm PrivKeyGenexpar,did,xid first takes the public parameter par, the partial private key did, and the secret value xid as input and then returns SKid=did,xid as the private key.Public Key Generation. The algorithm PubKeyGenexpar,xid first takes the public parameter par and the secret value xid as input and then computes the public key PKid=gxid.Encryption. The algorithm Encryptexpar,m∈0,1,PKid first takes the public parameter par, a message m∈0,1, and the public key PKid as input. It then encrypts m as follows:First, check whetherPKidq≐1G2. If not, abort; otherwise, compute ssk,svk⟵sign.Skg1λ and proceed as follows.Ifm=1, pick K⟵$G1, compute r=H2K,PKid,id, c1=rH1idP+rPpub, σ=sign.Sigssk,gr,id∈G2, and c2=K+H3gr,PKidr.Ifm=0, pick c1⟵$SampleG1, c2⟵$SampleG1, and σ⟵$SampleG2.Finally, the ciphertext is set asc=c1,c2,σ,svk.Decryption. The algorithm Decryptexpar,c,SKid takes the public parameter par, a ciphertext c, and a private key SKid as input. To decrypt a ciphertext c=c1,c2,σ,svk, firstly compute u=ec1,did=gr and K=c2−H3u,uxid and verify whether sign.Versvk,σ,u,id=1 holds; if not, outputs ⊥; otherwise, verify whether uxid=PKidH2K,PKid,id holds; if so, set m=1; otherwise, m=0.Correctness. If c=c1,c2,σ,svk is the encryption of 1, then the equations u=ec1,did=erH1idP+rPpub,1/s+H1idP=gr, K=c2−H3u,uxid, sign.Versvk,σ,u,id=1, and uxid=PKidH2K,PKid,id hold, so the decryption always recovers 1. If c=c1,c2,σ,svk is the encryption of 0, since c1⟵$SampleG1, c2⟵$SampleG1 and σ⟵$SampleG2 are sampled uniformly and randomly. So, Prec1,didxid=PKidr=PKidH2K,PKid,id≤1/qλ (we assume that qλ is large enough which, in turn, results in a negligible quantity for 1/qλ).


## 4.2. Security

Theorem 1.
Assume the hash functionsH1,H2, andH3are random oracles, and the schemesign=sign.Skg,sign.Sig,sign.Veris one-time signature scheme. LetII′be extractable 1SPO-CLE scheme proposed in Section 4.1andG1andG2be PR-sampleable (pseudorandom-sampleable) with negligible sampling failure probability. LetA1andA2be any IND-CPA type 1 and type 2 adversaries against schemeII′, respectively, and are allowed to make polynomial times of queries toH2andH3; then, the schemeII′is IND-CPA secure under both type 1 adversary and type 2 adversary.Proof.
We first prove that, for type 1 adversary, the security can be reduced to the security of one-time signature schemesign and then prove that, for type 2 adversary, the security can be reduced to the computational Diffie–Hellman assumption (short for CDH). In the following, we describe the reduction between the adversary Asig (which tries to break the one-time signature scheme) and the type 1 adversary A1 and the reduction between the adversary Acdh (which tries to break the CDH assumption) and the type 2 adversary A2, respectively.


### 4.2.1. Type 1 Adversary

Setup: the adversary Asig (which has the signing verification key svk) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A1.Partialprivatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, the adversary Asig invokes the partial private key generation algorithm to obtain the partial private key did and sends it to the adversary A1; otherwise it aborts. Concretely, the adversary Asig first queries the random oracle H1 to get Qid and then computes did=1/s+QidP∈G1. Note that the oracle H1 here is stateful and assume that all oracles in the following are stateful.Privatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, Asig first invokes the secret value generation algorithm and the partial private key generation algorithm to get the secret value xid and the partial private key did and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid; otherwise it aborts.Publickeyquery: on receiving the identity id, Asig first invokes the secret value generation algorithm to get xid and then computes the public key as PKid=gxid.Replacepublickeyquery: on receiving the identity id, Asig replaces the original public key PKid=gxid with the new public key PKid′=gxid′.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Asig computes challenge ciphertext as follows.First flip a coinb⟵$0,1 and then check whether PKid∗q≐1G2; if not, abort; otherwise, proceed as follows.Ifmb=1, do the following steps.(1)
First, pickK⟵$G1, and then for tuple K,PKid∗,id∗, query oracle H2 to get r.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Computegr and PKid∗r, and then for gr,PKid∗r, query oracle H3 to get h.(4)
Computec1=rQid∗P+rPpub and c2=K+h.(5)
Forgr,id∗, query signature oracle to get σ.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1 and σ⟵$SampleG2 at random. Then, the final challenge ciphertext is set as c=c1,c2,σ,svk.From above, we can see that the adversaryAsig provides perfect simulation for A1. Now we do the following analysis.Analysis: let the challenge ciphertext c=c1,c2,σ,svk. In the experiment, since A1 does not know did∗, it cannot compute the value u=gr. Assume A1 guess u′=gr′ randomly. Then, by the one-time signature scheme sign, the verification equation sign.Versvk,σ,u′,id∗=1 does not hold with overwhelming probability.


### 4.2.2. Type 2 Adversary

Setup: the adversary Acdh (which has the challenge PKid∗,u=gr) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A2.Privatekeyquery: in this phase, If id∉ChID, where ChID is the challenge identity set, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and computes partial private key did, and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid.Publickeyquery: in this phase, if id∉ChID, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and then computes the public key as PKid=gxid; otherwise it aborts.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Acdh computes challenge ciphertext as follows. First sample a random b⟵$0,1, then check whether PKid∗q≐1G2; if not, abort; otherwise, compute ssk,svk⟵sign.Skg1λ and proceed as follows.Ifmb=1, do the following steps.(1)
Pickc2⟵$G1.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Query the CDH challenger to getc1, where c1 is computed as c1=rQid∗P+rPpub.(4)
Foru=gr,id∗, compute signature σ.(5)
Set the challenge ciphertext asc=c1,c2,σ,svk.From above, it is easy to see that we implicitly setr=H2K,PKid∗,id∗ for K=c2−h and h=H3gr,PKid∗r. In addition, we require here that computing r from rP is not easier than computing r from gr.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1, and σ⟵$SampleG2 at random.Then, set the challenge ciphertext asc=c1,c2,σ,svk.From above, we can see that the adversaryAcdh provides perfect simulations for the adversary A2. Now we do the following analysis.Analysis: let c=c1,c2,σ,svk be the challenge ciphertext. In the experiment, A2 knows u=gr and PKid∗; by the CDH assumption, it is still difficult to compute uxid∗ and K to make the verification equation uxid∗=PKid∗H2K,PKid∗,id∗ hold.This completes the proof of Theorem1.


## 4.2.1. Type 1 Adversary

Setup: the adversary Asig (which has the signing verification key svk) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A1.Partialprivatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, the adversary Asig invokes the partial private key generation algorithm to obtain the partial private key did and sends it to the adversary A1; otherwise it aborts. Concretely, the adversary Asig first queries the random oracle H1 to get Qid and then computes did=1/s+QidP∈G1. Note that the oracle H1 here is stateful and assume that all oracles in the following are stateful.Privatekeyquery: on receiving the identity id, if id∉ChID, where ChID is the challenge identity set, Asig first invokes the secret value generation algorithm and the partial private key generation algorithm to get the secret value xid and the partial private key did and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid; otherwise it aborts.Publickeyquery: on receiving the identity id, Asig first invokes the secret value generation algorithm to get xid and then computes the public key as PKid=gxid.Replacepublickeyquery: on receiving the identity id, Asig replaces the original public key PKid=gxid with the new public key PKid′=gxid′.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Asig computes challenge ciphertext as follows.First flip a coinb⟵$0,1 and then check whether PKid∗q≐1G2; if not, abort; otherwise, proceed as follows.Ifmb=1, do the following steps.(1)
First, pickK⟵$G1, and then for tuple K,PKid∗,id∗, query oracle H2 to get r.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Computegr and PKid∗r, and then for gr,PKid∗r, query oracle H3 to get h.(4)
Computec1=rQid∗P+rPpub and c2=K+h.(5)
Forgr,id∗, query signature oracle to get σ.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1 and σ⟵$SampleG2 at random. Then, the final challenge ciphertext is set as c=c1,c2,σ,svk.From above, we can see that the adversaryAsig provides perfect simulation for A1. Now we do the following analysis.Analysis: let the challenge ciphertext c=c1,c2,σ,svk. In the experiment, since A1 does not know did∗, it cannot compute the value u=gr. Assume A1 guess u′=gr′ randomly. Then, by the one-time signature scheme sign, the verification equation sign.Versvk,σ,u′,id∗=1 does not hold with overwhelming probability.


## 4.2.2. Type 2 Adversary

Setup: the adversary Acdh (which has the challenge PKid∗,u=gr) first generates the public parameter par: = G1,G2,e,q,P,Ppub,g and the master key s, where Ppub=sP and g=eP,P∈G2, and then sends the public parameter par to the adversary A2.Privatekeyquery: in this phase, If id∉ChID, where ChID is the challenge identity set, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and computes partial private key did, and then sets the private key as SKid=did,xid, i.e., SKid=1/s+H1idP,xid.Publickeyquery: in this phase, if id∉ChID, the adversary Acdh first invokes the secret value generation algorithm to get secret value xid and then computes the public key as PKid=gxid; otherwise it aborts.Challenge: on receiving the challenge identity id∗ and the challenge message m0=0, m1=1 and the public key PKid∗, the adversary Acdh computes challenge ciphertext as follows. First sample a random b⟵$0,1, then check whether PKid∗q≐1G2; if not, abort; otherwise, compute ssk,svk⟵sign.Skg1λ and proceed as follows.Ifmb=1, do the following steps.(1)
Pickc2⟵$G1.(2)
Forid∗, query oracle H1 to get Qid∗.(3)
Query the CDH challenger to getc1, where c1 is computed as c1=rQid∗P+rPpub.(4)
Foru=gr,id∗, compute signature σ.(5)
Set the challenge ciphertext asc=c1,c2,σ,svk.From above, it is easy to see that we implicitly setr=H2K,PKid∗,id∗ for K=c2−h and h=H3gr,PKid∗r. In addition, we require here that computing r from rP is not easier than computing r from gr.Ifmb=0, pick c1⟵$SampleG1, c2⟵$SampleG1, and σ⟵$SampleG2 at random.Then, set the challenge ciphertext asc=c1,c2,σ,svk.From above, we can see that the adversaryAcdh provides perfect simulations for the adversary A2. Now we do the following analysis.Analysis: let c=c1,c2,σ,svk be the challenge ciphertext. In the experiment, A2 knows u=gr and PKid∗; by the CDH assumption, it is still difficult to compute uxid∗ and K to make the verification equation uxid∗=PKid∗H2K,PKid∗,id∗ hold.This completes the proof of Theorem1.


## 5. Comparisons and Discussion

The authors in [14] first proposed an SOA secure certificateless encryption scheme. In this paper, we improved it to make the security proof more concise and user friendly. Although in [14], they gave an efficiency analysis, here, to make it easier to understand, we give a more detailed comparison with the existing similar schemes, especially with that in [3, 14]. The detailed comparison results are shown in Table 1. Similarly, in terms of complexity, we also just make comparisons among them on the cost of the additive and multiplicative operations, especially on the exponent and the pairing operations. In addition, we also compare them in “security model,” “whether key escrow is needed,” and “whether a simplified proof is provided.” From this table, we can see that in [3], the first scheme requires 14 exponents and 5 pairings and the second scheme requires 15 exponents and 1 pairing, while in [14], the scheme only needs 6 exponents and 2 pairings. By comparison, we can see that our scheme not only realizes a simplified security proof but also obtains the same efficiency and security level as that of [14].Table 1
Comparison in exponent, pairing, and security model.
ExponentPairingSecurity modelNeed key escrow?Simplified proof?SchemeLoR [3]145SMYes—SchemeBBoR [3]151SMYes—Scheme [14]62ROMNoNoOur scheme62ROMNoYes


## 6. Result

As shown in Table1, compared with the schemes in [3], our scheme is practical in real applications which is mainly reflected in the following 4 aspects: (1) our scheme can be instantiated from very standard assumption such as computational Diffie–Hellman; (2) the used one-time signature can be constructed from standard assumption such as one-way function; (3) the hash functions such as random oracles in our scheme are very easily run on a low-configured device; (4) our scheme has better efficiency as analyzed in Section 5. Specifically, our scheme has 8 exponents and 3 pairings less than that of the first scheme in [3] and has 1 pairing more than that of the second scheme in [3], respectively. In addition, compared with [14], our scheme has more concise and user-friendly security proof.


## 7. Conclusions

This paper proposed a certificateless public key encryption against selective opening attacks (SOA), which is suitable for the data storage in Cloud 5G environment. This scheme is proved secure in the ROM under the assumptions of CDH and security of one-time signature. The advantage of the scheme is that it eliminates both certificate management and key management in PKI-based PKE and IBE settings and is practical in Cloud 5G settings. Compared with [14], our scheme not only has more concise and user-friendly security proof but also achieves the same level of security, which strengthens the data security storage in Cloud 5G applications.



---

*Source: 6695964-2021-05-28.xml*