# Efficient Certificateless Anonymous Multi-Receiver Encryption Scheme without Bilinear Parings

Authors: Ronghai Gao; Jiwen Zeng; Lunzhi Deng
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

With the growing development of Internet technology and popularization of mobile devices, we easily access the Internet anytime and anywhere by mobile devices. It has brought great convenience for our lives. But it brought more challenges than traditional wired communication, such as confidentiality and privacy. In order to improve security and privacy protection in using mobile network, numerous multi-receiver identity-based encryption schemes have been proposed with bilinear pairing and probabilistic hap-to-point (HTP) function. To address the troubles of private key escrow in multi-receiver encryption scheme based on ID-PKC, recently, some certificateless anonymous multi-receiver encryption (CLAMRE) schemes are introduced. But previous CLAMRE schemes using the bilinear pairing are not suitable to mobile device because the use of bilinear pairing and probabilistic hash-to-point (HTP) function results in expensive operation costs in encryption or decryption. In this paper, we propose an efficient CLAMRE scheme using elliptic curve cryptography (ECC) without bilinear pairing and HTP hash function. Since our scheme does not use bilinear pairing and HTP operation during the encryption and decryption process, the proposed CLAMRE scheme has much less computation cost than the latest CLAMRE schemes. Performance analysis shows that runtime of our scheme is much less when the sender generates ciphertext, compared with existing schemes. Security analysis shows proposed CLAMRE scheme provides confidentiality of message and receiver anonymity under the random oracle model with the difficulties of decision Diffie-Hellman problem and against the adversaries defined in CL-PKC system.


---

## Body

## 1. Introduction

With the rapid development of the Internet technology and wireless communications and the popularity of mobile devices, we can access the Internet freely anytime and anywhere using mobile devices. This brings great convenience to our lives by Internet services. But we have to face the security problems of the openness of the wireless network. How to protect the security and privacy of wireless communications using mobile devices has been extensively considered by scholars. In order to achieve this goal, many encryption schemes (Fu Z et al. [1, 2]; Xia Z et al. [3]; Huang X et al. [4]), authentication schemes (Guo P et al. [5]; Shen J et al. [6]; Huang X et al. [4, 7];) and signature schemes (Ren Y et al. [8]; Wang J et al. [9]; Lee C C et al. [10]) have been proposed in recent years.The multi-receiver encryption (MRE) or broadcast encryption (BEN) scheme is an important cryptographic primitive, in which a sender produces an identical ciphertextσ by enciphering message m and then sends σ to group S of selected receivers, and anyone in the group S can decrypt the received ciphertext using his/her private key, and any user outside the privileged set S should not be able to recover the message. In fact, the application of multi-receiver confidential communication is very extensive, such as pay TV, video on demand, software protect, distribution of copyrighted material, and online gaming. When transmitting encrypted information to a public channel, the confidentiality of the information and the anonymity of the receiver are greatly challenged. The confidentiality is that only the authorized receiver can decrypt ciphertext σ and message m correctly. On the other hand, identity protection means that any receiver of the group cannot identify the identity of other receivers. MRE scheme is suitable for protecting the users' security and privacy. Therefore, it is necessary to consider how to design efficient and secure broadcast encryption and multiple receivers encryption scheme. In order to meet security requirements of the practical application, many MRE schemes (Kurosawa K [11]; Bellare M et al. [12]; Dodis Y et al. [13]; Kurosawa K [14]; Bellare M [15]) were proposed using the public key infrastructure (PKI).In multi-receivers encryption schemes [11–15], existing management, distribution, and revocation of public key certificate need to bear huge storage space and high computing cost. To solve this problem, Beak et al. [16] constructed an efficient multi-receivers identity-based encryption (ID-based MRE); only one bilinear pair is required to encrypt a single message for n receivers. In 2006, Chatterjee S et al. [17] proposed a multi-receiver identity-based key encapsulation mechanism with security in the full model and sublinear size ciphertext. In this scheme, a controllable trade-off is achieved between the ciphertext size and the private size. However, Park et al. gave a way to attack the scheme of Chatterjee S [17] and proved that it is not secure. In 2006, another IBBE scheme is designed by Yang et al. [18] using elliptic curve bilinear paring. However, they did not consider joining and departure of the recipient’s membership in the design process, so the scheme was not suitable for a dynamic set. In scheme [16–18], the application scenario is single domain environment; that is, n receivers come from the same management domain. However, in realistic applications, usually n receivers will come from different management domains and they need once the bilinear pairing computation for one message, so their scheme becomes inefficient. In 2014, Wang H et al. [19] proposed an efficient multiple domain multi-receiver identity-based encryption scheme that only requires one pairing computation to encrypt a single message for n receivers from different administrative domains.However, the above ID-based MRE schemes [16–19] cannot consider the receiver anonymity. To achieve preserving privacy of receivers, in 2010, Fan et al. [20] presented a new ID-based MRE scheme and claimed that it can protect receiver anonymity; the scheme is highly efficient for each receiver as it requires only two pairing operations. In 2012, Chien [21] found that the scheme of Fan et al. [20] failed to protect receiver anonymity and proposed an improved scheme which proves that the scheme enhances security and protects the anonymity of recipients. It is very unfortunate that Wang [22] pointed out the fact that Chien’s scheme does not satisfy the indiscernibility of encryption under selective multi-identity, chosen ciphertext attacks. In 2015, Zhang [23] proposed the most efficient anonymous MRIBE scheme in terms of computational cost and communication overhead, compared with schemes of [20–22].Although the above ID-based MRE schemes have many advantages, all of them face the problem of the private key escrow, which means that key generator center (KGC) calculates private key for every user by user identity and master private key of KGC; KGC retains all users private key; thus the user’s privacy is easy to be leaked if KGC is not fully trusted. In order to address this security weakness, in 2003, Al-Riyami et al. [24] introduced the concept of the certificateless cryptography (CLC). In the CLC, the users' private key contains two parts: KGC and the user generate a partial private key and a secret value, respectively. Based on Al-Riyami et al.'s work, most certificateless signature (encryption) schemes [25–29] are proposed. In the existing research literature, certificateless multi-receiver encryption (CLMRE) scheme did not get more attention; Islam et al. [27] presented the concept of certificateless anonymous multi-receiver encryption (CLAMRE) and proposed the first CLAMRE scheme using the elliptic curve cryptography (ECC). Hung et al. [28] pointed out that scheme of [27] is less efficient and is not suitable in mobile devices environment, because the cost of encryption calculation is square of number of recipients, and proposed a new CLAMRE using the bilinear pairing. However, Hung et al.’s CLAMRE scheme still does not suit mobile devices because of using bilinear pairing. In encryption, the sender that needs to operate bilinear pairs grows linearly because of the increase in the receivers' number.Our Contribution.In this paper, we propose an efficient CLAMRE scheme using elliptic curve cryptography (ECC) without bilinear pairing and MTP hash function. Since our scheme does not use bilinear pairing and HTP operation during the encryption process, the proposed CLAMRE scheme has much less computation cost than the latest CLAMRE schemes; runtime of our scheme is much less in both encryption and decryption, compared with existing scheme [28, 29]. Our scheme provides confidentiality of message and anonymity of receiver under the random oracle model with the difficulties of computational Diffie-Hellman problem and against the adversaries defined in CL-PKC system.In this paper, we propose an efficient CLAMRE scheme using elliptic curve cryptography (ECC) without bilinear pairing and MTP hash function. Since our scheme does not use bilinear pairing and HTP operation during the encryption process, the proposed CLAMRE scheme has much less computation cost than the latest CLAMRE schemes; runtime of our scheme is much less in both encryption and decryption, compared with existing scheme [28, 29]. Our scheme provides confidentiality of message and anonymity of receiver under the random oracle model with the difficulties of computational Diffie-Hellman problem and against the adversaries defined in CL-PKC system.Organization.The rest of the paper is organized as follows. Mathematical preliminaries are introduced in Section 2. Formal definition of our CLAMRE scheme is presented in Section 3. Our CLAMRE scheme is proposed in Section 4. In Section 5, we give some security analysis of our CLAMRE scheme. Some performance analysis of our CLAMRE scheme is given in Section 6. At last, some conclusions of the paper are presented.The rest of the paper is organized as follows. Mathematical preliminaries are introduced in Section2. Formal definition of our CLAMRE scheme is presented in Section 3. Our CLAMRE scheme is proposed in Section 4. In Section 5, we give some security analysis of our CLAMRE scheme. Some performance analysis of our CLAMRE scheme is given in Section 6. At last, some conclusions of the paper are presented.


## 2. Mathematical Preliminaries

Here, we introduced the basic theory about the elliptic curve and existing some intractable problems.


### 2.1. Elliptic Curve

Suppose thatFp is a finite field determined by a prime number p. The elliptic curve E(Fp) over Fp is the set of solutions (x,y)∈Fp×Fp to the congruence y2≡x3+ax+b(modp), where a,b∈Fp are constants such that 4a3+27b2≠0(modp), together with a special point O called the point at infinity or zero point.The addition operation “+” onE is defined as follows (where all arithmetic operations are performed in Fp): the point at infinity, O, will be the identity element, so P+O=O+P=P for arbitrary P∈E.SupposeP,Q∈E, if P≠Q and reflection of the point P with respect to the x-axis is not the point Q; let l be the line through P and Q; otherwise P=Q; we define l to be the tangent line through the point P. We denote R′ as the third point in which l intersects E; if we reflect R′ in the x-axis, then we get a point which we call R. We define the following: P+Q=R. If reflection of the point P with respect to the x-axis is point Q, let Q=-P; we define the following: P+Q=P+(-P)=P-P=O. The scalar point multiplication of the elliptic curve E is defined as tP=P+P+⋯+P(t times). Point P has order n if n is the smallest positive integer such that nP=O. So (E,+) is an abelian group.


### 2.2. Computational Problems and Some Assumptions

Here, we mainly introduce the definitions of negligible function, decision Diffie-Hellman problem, and discrete logarithm (DL) problem, and assumptions are given.Negligible Function.We call function ω(k) negligible if, for every a>0, there exists l0 such that ω(k)≤1/kl for every l≥l0.We call functionω(k) negligible if, for every a>0, there exists l0 such that ω(k)≤1/kl for every l≥l0.Discrete Logarithm (DL) Problem.Given a random instance (P,xP), where P∈E, and x∈Zp∗, computation of x is computationally hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DL problem is defined as AdvADL(k)=Pr[A(P,xP)=x:P∈E;x∈Zp∗].Given a random instance(P,xP), where P∈E, and x∈Zp∗, computation of x is computationally hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DL problem is defined as AdvADL(k)=Pr[A(P,xP)=x:P∈E;x∈Zp∗].Discrete Logarithm (DL) Assumption.For any probabilistic polynomial time-bounded algorithm A, AdvADL(k) is negligible if AdvADL(k)≤ω, for negligible function ω.For any probabilistic polynomial time-bounded algorithmA, AdvADL(k) is negligible if AdvADL(k)≤ω, for negligible function ω.Decision Diffie-Hellman (DDH) Problem.Suppose that P is point with order p on E, and A=aP,B=bP,X are random points on P, where a,b∈Zp∗. Determining if X=abP holds is hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DDH problem is defined as AdvADDH(k)=|Pr[A(P,aP,bP,X)∣X=abP]-1/2|Suppose thatP is point with order p on E, and A=aP,B=bP,X are random points on P, where a,b∈Zp∗. Determining if X=abP holds is hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DDH problem is defined as AdvADDH(k)=|Pr[A(P,aP,bP,X)∣X=abP]-1/2|Decision Diffie-Hellman Assumption.For any probabilistic polynomial time-bounded algorithm A, AdvADDH(k) is negligible if AdvADDH(k)≤ω, for negligible function ω.For any probabilistic polynomial time-bounded algorithmA, AdvACDH(k) is negligible if AdvADDH(k)≤ω, for negligible function ω.


## 2.1. Elliptic Curve

Suppose thatFp is a finite field determined by a prime number p. The elliptic curve E(Fp) over Fp is the set of solutions (x,y)∈Fp×Fp to the congruence y2≡x3+ax+b(modp), where a,b∈Fp are constants such that 4a3+27b2≠0(modp), together with a special point O called the point at infinity or zero point.The addition operation “+” onE is defined as follows (where all arithmetic operations are performed in Fp): the point at infinity, O, will be the identity element, so P+O=O+P=P for arbitrary P∈E.SupposeP,Q∈E, if P≠Q and reflection of the point P with respect to the x-axis is not the point Q; let l be the line through P and Q; otherwise P=Q; we define l to be the tangent line through the point P. We denote R′ as the third point in which l intersects E; if we reflect R′ in the x-axis, then we get a point which we call R. We define the following: P+Q=R. If reflection of the point P with respect to the x-axis is point Q, let Q=-P; we define the following: P+Q=P+(-P)=P-P=O. The scalar point multiplication of the elliptic curve E is defined as tP=P+P+⋯+P(t times). Point P has order n if n is the smallest positive integer such that nP=O. So (E,+) is an abelian group.


## 2.2. Computational Problems and Some Assumptions

Here, we mainly introduce the definitions of negligible function, decision Diffie-Hellman problem, and discrete logarithm (DL) problem, and assumptions are given.Negligible Function.We call function ω(k) negligible if, for every a>0, there exists l0 such that ω(k)≤1/kl for every l≥l0.We call functionω(k) negligible if, for every a>0, there exists l0 such that ω(k)≤1/kl for every l≥l0.Discrete Logarithm (DL) Problem.Given a random instance (P,xP), where P∈E, and x∈Zp∗, computation of x is computationally hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DL problem is defined as AdvADL(k)=Pr[A(P,xP)=x:P∈E;x∈Zp∗].Given a random instance(P,xP), where P∈E, and x∈Zp∗, computation of x is computationally hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DL problem is defined as AdvADL(k)=Pr[A(P,xP)=x:P∈E;x∈Zp∗].Discrete Logarithm (DL) Assumption.For any probabilistic polynomial time-bounded algorithm A, AdvADL(k) is negligible if AdvADL(k)≤ω, for negligible function ω.For any probabilistic polynomial time-bounded algorithmA, AdvADL(k) is negligible if AdvADL(k)≤ω, for negligible function ω.Decision Diffie-Hellman (DDH) Problem.Suppose that P is point with order p on E, and A=aP,B=bP,X are random points on P, where a,b∈Zp∗. Determining if X=abP holds is hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DDH problem is defined as AdvADDH(k)=|Pr[A(P,aP,bP,X)∣X=abP]-1/2|Suppose thatP is point with order p on E, and A=aP,B=bP,X are random points on P, where a,b∈Zp∗. Determining if X=abP holds is hard by a polynomial time-bounded algorithm. The probability that a polynomial time-bounded algorithm A can solve the DDH problem is defined as AdvADDH(k)=|Pr[A(P,aP,bP,X)∣X=abP]-1/2|Decision Diffie-Hellman Assumption.For any probabilistic polynomial time-bounded algorithm A, AdvADDH(k) is negligible if AdvADDH(k)≤ω, for negligible function ω.For any probabilistic polynomial time-bounded algorithmA, AdvACDH(k) is negligible if AdvADDH(k)≤ω, for negligible function ω.


## 3. Formal Definition of the CLAMRE Scheme

The CLAMRE scheme includes three categories of participants, that is, the sender of information, the private key generation center, and the group of selective receivers, respectively.We denoteT={R1,R2,⋯,Rn} as group of n receivers selected by sender, ID={ID1,ID2,⋯,IDn} are their group identities, pk={pk1,pk2,⋯,pkn} are group public key, and sk1,sk2,⋯,skn are the full private key. In CLAMRE scheme, sender generates ciphertext σ for message m using public key {pk1,pk2⋯,pkn} and identities {ID1,ID2,⋯,IDn} of receivers {R1,R2,⋯,Rn}. Ciphertext σ is conveyed to the receiver through the public channel. Every receiver Ri in group T can correctly decrypt ciphertext σ by using private key ski for i∈{1,2,⋯,n}. And arbitrary two receivers Ri,Rj(i≠j) in selected receiver group T do not disclose the identity with each other. Figure 1 demonstrates intuitively the process of CLAMRE scheme. In the following, we depict the definition of the CLAMRE scheme.Figure 1
Process of a CLAMRE scheme.In generally, a certificateless anonymous multi-receiver encryption scheme consists of a tuple(Setup,Partial-Private-Key-Extract,Set-Secret-Value,Set-Private-Key,Set-Public-Key,Multi-encryption,andMulti-decryption.)(i)
Setup: selecting a security parameter k as input, semitrusted private key generation center (KGC) executes this algorithm to generate the system’s public parameters Ω and KGC’s the master public/private key pair (mpk,msk). Ωandmpk are published, and the master private msk is kept by KGC.(ii)
Partial-Private-Key-Extract: this algorithm is executed by KGC, according to the identity IDi of receiver Ri; the PKG computes the corresponding partial private key sIDi using the master private key and delivers it to receiver Ri via an secure channel.(iii)
Set-secret-value: this algorithm is executed by receiver with identity IDi himself/herself to generate his/her secret value ti.(iv)
Set-Private-Key: this algorithm is executed by receiver Ri with identity IDi. It takes (Ω,sIDi,ti) as input and returns the full private key ski to Ri as output.(v)
Set-Public-Key: this algorithm is executed by receiver Ri himself/herself to generate his/her public key pki according to his/her secret value ti.(vi)
Multi-encryption:this is PPT algorithm. Sender executes this algorithm to generate a ciphertext for message m by identities and full public of selected receivers.(vii)
Multi-decryption: a selected receiver runs this algorithm to decrypt the received ciphertext using the receivers full private key.


## 4. Description of the Proposed CLAMRE Scheme

In this section, we introduced our certificateless anonymous multi-receiver encryption (CLAMRE) scheme using elliptic curve cryptography (ECC) without bilinear pairings. The proposed scheme has three kinds of participants, i.e., a senderS, set T consisting of selected n receivers R1,R2,⋯,Rn, and a KGC. Sender generates ciphertext σ by encrypting message m only for selected receivers R1,R2,⋯,Rn; then sender delivers the ciphertext σ to the receivers. Every receiver Ri in T can correctly decrypt ciphertext σ receive by using his/her full private key ski for i∈{1,2,⋯,n}. And arbitrary two receivers Ri,Rj(i≠j) in selective receiver set T do not disclose the identity with each other. The PKG generates the systems parameter and identity-based partial private keys of all the receivers Ri for i∈{1,2,⋯,n}. The proposed scheme includes the following seven algorithms (Setup, Partial-Private-Key-Extract,Set-Secret-Value,Set-Private-Key, Set-Public-Key, Multi-encryption, andMulti-decryption.)(i)
Setup: With the given security parameter k, this algorithm is executed KGC to generate the system’s parameters. The following steps will be implemented KGC in this algorithm.
(1)
Choose twok-bits prime integers p,q, two k-bits integers l1,l2, and an elliptic curve E defined on Fp. Let G be additive group on elliptic curve E, and Gq be subgroup of G with prime order q.(2)
Select randomly a generatorP∈Gq.(3)
Randomly choosex∈RZq∗ as the master key and Ppub=x·P.(4)
Select four secure one-way hash functionsHi:{0,1}∗→Zq∗ (i=1,2,3); H4:{0,1}∗→{0,1}l1+l2.(5)
Publish system’s parametersΩ={p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} and message space M={0,1}l1.(ii)
Set-secret-value: A receiver Ri with IDi randomly selects ti∈Zq∗ as his or her secret value and computes PKIDi=ti·P as the corresponding public key, and Ri sends (PKIDi,IDi) to KGC.(iii)
Partial-Private-Key-Extract: According to the identity IDi of receiver Ri, the KGC performs the following steps:
(1)
Randomly chooseri∈RZq∗ and compute RIDi=ri·P.(2)
CalculatekIDi=H1(RIDi,PKIDi,IDi) and sIDi=ri+kIDix mod (q)(3)
The tuple(RIDi,sIDi) is delivered to receiver Ri by authenticated secure channel.Here,sIDi is receiver Ri’s partial private key. Partial private key sIDi is valid if verify that equation sIDiP=RIDi+H1(RIDi,PKIDi,IDi)Ppub is true and vice versa. Since we have(1)RIDi+H1RIDi,PKIDi,IDiPpub=riP+kIDiPpub=riP+kIDixP=ri+kIDixP=sIDiP(iv)
Set-Private-Key: Receiver Ri secret keeps ski=(di,ti) as his or her the full private.(v)
Set-Public-Key: Reciever Ri keeps pki=(RIDi,PKIDi) as full public key.(vi)
Multi-encryption: This algorithm is executed by sender S to generate a ciphertext for given message m and selected n receivers R1,R2,⋯,Rn with identity ID1,ID2,⋯IDn respectively. The following steps will be performed in this algorithm.
(1)
Choose randomlyω∈{0,1}l2 and given message m∈M. Calculate s=H2(m,ω) and S=sP.(2)
ComputeUi=s·(RIDi+kIDiPpub+PKIDi) and μi=H3(Ui,IDi,pki), where i=1,2,⋯,n.(3)
Randomly selecte∈RZq∗ and compute a polynomial f(x) with degree n as follows:(2)fx=∏i=1nx-μi+emod⁡q=xn+an-1xn-1+⋯+a1x+a0,whereai∈Zq∗i=0,1,…,n-1(4)
ComputeC=H4(S,e)⊕(m∥ω)(5)
Generate ciphertextσ=(S,C,f).(vii)
Multi-decryption: This algorithm is executed by selected receiver Ri to extract plaintext from the received ciphertext σ=(S,C,f). Ri performs following steps:
(1)
ComputeUi=(sIDi+ti)S and μi=H3(Ui,IDi,pki),i∈{1,2,⋯,n}.(2)
Calculatef(x)=xn+an-1xn-1+⋯+a1x+a0 and e=f(μi).(3)
Computem∥ω=H4(S,e)⊕C(4)
Verify ifS=H2(m,ω)P holds. If not, Ri stops the process; otherwise, Ri output the plaintext m.


## 5. Security Analysis of the Proposed CLAMRE Scheme

### 5.1. Security Model

In order to prove the security of the CLAMRE scheme, we take into account of the malicious-but-passive KGC. The robust security model is proposed by Hung et al. [28] in the CLAMRE scheme. Two kinds of adversaries are defined as follows.Type I adversary A 1: A1 is a malicious outside adversary who can replace the users public key with a value chosen by himself/herself. However, A1 cannot access the master private key of KGC.Type II adversary A 2: A2 behaves as a honest-but-curious KGC who owns the master key. However it does not allow him/her to replace public key of any user. Define the security of a CLAMRE scheme as a game played between an adversary A∈{A1,A2} and a challenger C. During the game, A can make the following queries to C.C r e a t e - U s e r query: C generates private key and public key for the user Ui. C sends the user Ui ’s public key to A.P u b l i c - K e y - R e t r i e v e query: C returns the matching user Ui s public key to A.P u b l i c - K e y - R e p l a c e query: C replaces the associated users public key with new public key chosen by himself/herself.P a r t i a l - P r i v a t e - K e y - E x t r a c t query: C sends the users partial private key to A.S e c r e t - V a l u e - E x t r a c t query: C sends the users secret value to A.D e c r y p t i o n query: C decrypts the received ciphertext and sends plaintext to A.We define the confidentiality of a CLAMRE scheme as the indistinguishability against selective multi-identity chosen ciphertext attack (IND-sMID-CCA). The IND-sMID-CCA game is defined as follows.Game I.This game is to prove the confidentiality of the CLAMRE scheme.This game is to prove the confidentiality of the CLAMRE scheme.Phase 1.In this phase, adversary A selects n target users with identities IDR1,IDR2,⋯,IDRn and delivers them to C. C performs setup to generate system parameters and master key.In this phase, adversaryA selects n target users with identities IDR1,IDR2,⋯,IDRn and delivers them to C. C performs setup to generate system parameters and master key.Phase 2. A could adaptively make the aforementioned oracle query but does not allow him/her to make Partial-Private-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.A could adaptively make the aforementioned oracle query but does not allow him/her to make Partial-Private-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.Challenge. A chooses two plaintexts {m0,m1} with the same length, then delivers {m0,m1} to C. C randomly selects λ∈{0,1} and uses {IDR1,IDR2,⋯,IDRn} and the corresponding public key to encrypt the message mλ for generation the ciphertext CT∗. Then C sends CT∗ to A.A chooses two plaintexts {m0,m1} with the same length, then delivers {m0,m1} to C. C randomly selects λ∈{0,1} and uses {IDR1,IDR2,⋯,IDRn} and the corresponding public key to encrypt the message mλ for generation the ciphertext CT∗. Then C sends CT∗ to A.Phase 3.In this phase, A can make the same queries as he/she doesin Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDR1,IDR2,⋯,IDRn}.In this phase,A can make the same queries as he/she doesin Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDR1,IDR2,⋯,IDRn}.Guess.Finally, A outputs λ′∈{0,1}, that is, his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the CLAMRE scheme is defined by AdvCLAMREIND-sMID-CCA(A)=|Pr[λ′=λ]-1/2|.Finally,A outputs λ′∈{0,1}, that is, his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the CLAMRE scheme is defined by AdvCLAMREIND-sMID-CCA(A)=|Pr[λ′=λ]-1/2|.Definition 1.
We say a CLAMRE scheme is IND-sMID-CCA secure ifAdvCLAMREIND-sMID-CCA(A) is negligible for any polynomial-time-bounded adversary A.The receiver anonymity of a CLAMRE scheme is defined by the anonymous indistinguishability against selective identity chosen ciphertext attack (ANON-IND-sID-CCA). The ANON-IND-sID-CCA game is defined as follows.Game II.This game is to prove the anonymity of the CLAMRE schemeThis game is to prove the anonymity of the CLAMRE schemePhase 1.In this phase, A selects two target users with identities {ID0,ID1} and sends them to C. Then C runs setup to generate system parameters and the master key.In this phase,A selects two target users with identities {ID0,ID1} and sends them to C. Then C runs setup to generate system parameters and the master key.Phase 2.In this phase, A could adaptively make the aforementioned the oracle query. However he/she cannot make Create-User,Secret-Value-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.In this phase,A could adaptively make the aforementioned the oracle query. However he/she cannot make Create-User,Secret-Value-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.Challenge. A picks message m together with identities IDR2′,⋯,IDRn′ and sends them to C; C randomly selects λ∈{0,1} and uses {IDλ,IDR2′,⋯,IDRn′} and the corresponding public keys to generate a ciphertext CT∗ of a message mλ. Then C delivers CT∗ to A.A picks message m together with identities IDR2′,⋯,IDRn′ and sends them to C; C randomly selects λ∈{0,1} and uses {IDλ,IDR2′,⋯,IDRn′} and the corresponding public keys to generate a ciphertext CT∗ of a message mλ. Then C delivers CT∗ to A.Phase 3.In this phase, A can make the same queries as he/she does in Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDλ,IDR2′,⋯,IDRn′}.In this phase,A can make the same queries as he/she does in Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDλ,IDR2′,⋯,IDRn′}.Guess.Finally, A returns λ′∈{0,1} as his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the game is defined by AdvCLAMREANON-IND-sID-CCA(A)=|Pr[λ′=λ]-1/2|.Finally,A returns λ′∈{0,1} as his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the game is defined by AdvCLAMREANON-IND-sID-CCA(A)=|Pr[λ′=λ]-1/2|.Definition 2.
We say a CLAMRE scheme is ANON-IND-sID-CCA secure ifAdvCLAMREANON-IND-sID-CCA(A) is negligible for any polynomial-time-bounded adversary A.


### 5.2. Security Theorems

In this subsection, we will analyze in detail security of the proposed CLAMRE scheme. Through the analysis, it is shown that the proposed CLAMRE scheme is IND-sMID-CCA secure and ANON-IND-sID-CCA secure against two types of adversariesA1,A2.Theorem 3.
The proposed CLMRE scheme correctly generates the ciphertextσ=(S,C,a), where a=(a1,a2,⋯,an-1) and receiver Ri(1≤i≤n) decrypts it appropriately.Proof.
Due to the fact that(ti+sIDi)S = (ti+ri+kIDix)sP = s(tiP+riP+kIDiPpub) = s(PKIDi+RIDi+kIDiPpub)=Ui, receiver Ri computes the following:μi=H3(Ui,IDi,pki) and e=f(μi).m∥ω=H4(S,e)⊕C, and s=H2(m,ω) is true.
So we proposed that CLAMRE scheme is correct and consistent.Theorem 4.
In the random oracle model, our CLAMRE scheme satisfies the IND-sMID-CCA against the adversaryA1 with the hardness assumption of DDH problem.Proof.
A 1 is the polynomial time-bounded adversary, if A1 has the ability to break the security of the proposed CLAMRE scheme. Then we can construct a probabilistic polynomial time-bounded challenger C to solve the DDH problem by interacting with the adversary A1; that is, given an instance (P,aP,bP,X) of the DDH problem, challenger C is able to determine if X=ab·P holds. Challenger C maintains the following initial-empty lists in order to achieve the consistency between queries made by the adversary A1:
Phase 1
In this phase,A1 selects n target identities; we denote these identities as ID1,⋯,IDn.
C sets Ppub←x·P, and executes setup algorithm to generate other parameters. Then C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A1. To achieve the random oracles, C maintains four lists LHilist, where LHilist is initialized empty (i=1,2,3,4). The four random oracles make the following answer for A1s queries.
(i)H1(IDi,PKIDi,RIDi):C checks if (IDi,PKIDi,RIDi,kIDi) exists in LH1list. If so, C sends kIDi to A1. Otherwise, C randomly chooses value kIDi∈Zq∗, inserts (IDi,PKIDi,RIDi,kIDi) into LH1list, and sends kIDi.
(ii)H2(m,ω): C checks if (m,ω,s) exists in LH1list. If so, C returns s to A1. Otherwise, C randomly chooses value s∈Zq∗, inserts (m,ω,s) into LH2list, and returns s.
(iii)H3(Ui,IDi,pki): C checks if (Ui,IDi,pki,μi) exists in LH3list. If so, C returns μi to A1. Otherwise, C randomly chooses value μi∈Zq∗, inserts (Ui,IDi,pki,μi) into LH3list, and returns μi.
(iv)H4(S,e): C checks if (S,e,τ) exists in LH4list. If so, C returns τ to A1. Otherwise, C randomly selects an element τ∈{0,1}l1+l2, inserts (S,e,τ) into LH4list, and returns τ.
Phase 2
A 1 can adaptively make queries to C.C maintains a list LRlist, which is initialized empty. Challenger C responded to these queries made by adversary A1 as follows.
(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A1. Otherwise, C executes the following processes.
(ii) IfIDRi∈{ID1,⋯,IDn} holds, without losing generality, we suppose IDRi=IDi, C randomly picks ri,ti∈Zq∗, computes PKIDi=tiP,RIDi=riaP,kIDi=H1(IDi,PKIDi,RIDi), and sets sIDi←⊥. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.
(iii) OtherwiseIDRi∉{ID1,⋯,IDn}; C randomly picks ti,sIDi,kIDi∈Zq∗ and computes RIDi=sIDiP-kIDiPpub,PKIDi=tiP. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.
(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns (RIDi,PKIDi) to A1.
(v)Public-key-Replace(IDRi,RIDi′,PKIDi′): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C replaces (RIDi,PKIDi) with (IDi,RIDi′,PKIDi′)
(vi)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A1.
(vii)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.
(viii)Decryption(IDRi,σi): C checks if IDRi∈{ID1,⋯,IDn} holds, where σi=(Si,Ci,fi). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID1,⋯,IDn},C responds according to the following steps.
(ix)C looks up LH4list for (Si,ei,τi). If not, C outputs failure and stops.
(x)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.
(xi)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise return mi to A1
Challenge.   After making the above queries, A1 picks two messages m0 and m1 with length l2 and sends them to challenger C,C chooses λ∈{0,1} at random and performs the following steps.
(i)C sets S∗←b·P.
(ii) LetUi=(kIDix+ti)S∗+riX, and compute μi=H3(Ui,IDi,pki),i=1,2,⋯,n
(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(3)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,…,n-1
(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).
Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).
Phase 3
In this phase,A1 can make the same queries in Phase 2 except that it cannot make decryption queries with ID∗∈{ID1,ID2,⋯,IDn} and σ∗.
Guess
A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise,C outputs 0. A1 wins the game if and only if λ=λ′ holds.
Based on the above oracle queries, the simulation ofC is perfect. Next, we consider the probability that challenger C fails in Game I. Combined with the previous description, we know that C fails in Decryption query if (Si,ei) is not in LH4list. The probability that A1 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability of C failure in game I is less than qd/2l1+l2, where qd denote the decryption query times in the game.
IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(4)Prc=1∣X=abP=Prλ=λ′∣X=abP=12+ϵ.
IfX≠abP, then the ciphertext distribution is random and uniform when λ=0 or λ=1, so A1 cannot distinguish λ with any advantage.(5)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.
Therefore, ifA1 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2, because the DDH problem is difficult. Therefore, the proposed CLAMRE scheme is IND-sMID-CCA secure against A1.Theorem 5.
Our CLAMRE scheme is IND-sMID-CCA secure against type II adversaryA2 under random oracle model with the difficulties of computational Diffie-Hellman problem.Proof.
A 2 is the polynomial time-bounded adversary, if A2 has the ability to break the security of the proposed CLAMRE scheme. Then we can construct a probabilistic polynomial time-bounded challenger C to solve the DDH problem by interacting with the adversary A2; that is, for given an instance (P,aP,bP,X) of the DDH problem, challenger C is able to determine if X=ab·P holds. Challenger C maintains the following initial-empty lists in order to achieve the consistency between queries made by adversary A2.
Phase 1
In this phase,A2 selects n target identities; we denote these identities as ID1,⋯,IDn.
C picks x∈Zq∗ at random as system private key and computes corresponding public key Ppub=x·P. C performs Setup algorithm to construct other parameters. At last, C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A2 and master private key x to A2. To achieve the random oracles, C maintains four lists LHilist, where initial LHilist is empty (i=1,2,3,4). The four random oracles make the following answer for A2s queries.
(i)H1(IDi,PKIDi,RIDi): C checks if (IDi,PKIDi,RIDi,kIDi) exists in LH1list. If so, C returns kIDi to A2. Otherwise, C randomly selects an element kIDi∈Zq∗, inserts (IDi,PKIDi,RIDi,kIDi) into LH1list, and returns kIDi.
(ii)H2(m,ω): C checks if (m,ω,s) exists in LH1list. If so, C returns s to A2. Otherwise, C randomly selects an element s∈Zq∗, inserts (m,ω,s) into LH2list, and returns s.
(iii)H3(Ui,IDi,pki): C checks if (Ui,IDi,pki,μi) exists in LH3list. If so, C returns μi to A2. Otherwise, C randomly selects an element μi∈Zq∗, inserts (Ui,IDi,pki,μi) into LH3list, and returns μi.
(iv)H4(S,e): C checks if (S,e,τ) exists in LH4list. If so, C returns τ to A2. Otherwise, C randomly selects an element τ∈{0,1}l1+l2, inserts (S,e,τ) into LH4list, and returns τ.
Phase 2
In this phase,A2 can adaptively make a lot of queries to C. C maintains a list LRlist, which is initialized empty. These queries are responded as follows.
(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A2. Otherwise, C performs the following steps.
(ii) IfIDRi∈{ID1,⋯,IDn} holds, without losing generality, we suppose IDRi=IDi,C randomly chooses ri,ti∈Zq∗ and calculates PKIDi=ti·aP,RIDi=riP,kIDi=H1(PKIDi,Ri,IDi),sIDi=ri+kIDix mod q. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A2.
(iii) OtherwiseIDRi∉{ID1,⋯,IDn}; C randomly picks ti,ri,kIDi∈Zq∗ and computes RIDi=riP,sIDi=ri+kIDis mod q, PKIDi=ti·P. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A2.
(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns RIDi,PKIDi to A2.
(v)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A2.
(vi)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LR. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.
(vii)Decryption(IDRi,σi): C checks if IDRi∈{ID1,⋯,IDn} holds, where σi=(Si,Ci,ai),ai=(ai0,ai1,⋯,ai(n-1)). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID1,⋯,IDn},C responds according to the following steps.
(viii)C looks up L4list for (Si,ei,τi). If not, C outputs failure and stops.
(ix)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.
(x)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise, return mi to A2
Challenge
After making the above queries,A2 picks two messages m0 and m1 with length l2 and sends them to challenger C; C chooses λ∈{0,1} at random and implements the following process.
(i)C sets S∗←b·P.
(ii) LetUi=(kIDix+ri)S∗+ti·X, and compute μi=H3(Ui,IDi,pki).i=1,2,⋯,n
(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(6)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,…,n-1
(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).
Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).
Phase 3
In this phase,A2 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{ID1,ID2,⋯,IDn} and σ∗.
Guess
A 2 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A2 wins the game if and only if λ=λ′ holds.
According to the above oracle queries, we know that the simulation ofC is perfect. Now, we analyze the probability that C fails in Game I. Based on the above description, we know that C fails in decryption query if (Si,ei) is not in L4list. The probability that A2 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability that C fails in the game is less than qd/2l1+l2, where qd denotes the decryption queries involved in the game.
IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(7)Prc=1∣X=abP=Prλ=λ′∣X=abP=12+ϵ.
IfX≠abP, then the ciphertext distribution is random and uniform when λ=0orλ=1. So A2 cannot distinguish λ with any advantage.(8)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.
Therefore, ifA2 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. If A2 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then we know C can solve the CDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. Due to the fact that the CDH problem is hard, we know that the proposed CLAMRE scheme is IND-sMID-CCA secure against adversary A2.Theorem 6.
In the random oracle model, our proposed CLAMRE scheme is ANON-IND-sID-CCA secure against adversaryA1 with the difficulty assumption of DDH problem.Proof.
Assume that the adversaryA1 can breach our CLAMRE scheme, then we will be able to design a challenger C for solving an instance of DDH problem; that is, for given an instance (P,a·P,b·P,X) of DDH problem, challenger C can determine if X=abP holds by interacting with adversary A1. Similar to Theorem 4, let lists LHilist(i=1,2,3,4) and LRlist be maintained by challenger C.Phase 1.Assume that adversary A1 selects two target users with identities ID0,ID1. Challenger C randomly selects λ∈{0,1}Assume that adversaryA1 selects two target users with identities ID0,ID1. Challenger C randomly selects λ∈{0,1}C sets Ppub←x·P, and implements Setup algorithm to construct other parameters. At last, C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A1. Challenger C returns answers to the adversary A1s queries in the following ways.Hash queries toHi(i=1,2,3,4): these queries are the same as those performed in Theorem 4.Phase 2.Now, challenger C will respond to the queries made by the adversary A1 in the following ways.Now, challengerC will respond to the queries made by the adversary A1 in the following ways.(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A1. Otherwise, C executes the following processes.(ii) IfIDRi=IDj for j∈{0,1} holds, C randomly chooses ri,ti∈Zq∗, computes PKIDi=ti·P,RIDi=ri·aP,kIDi=H1(IDi,PKIDi,RIDi), and sets sIDi←⊥. C inserts (IDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.(iii) OtherwiseIDRi∉{ID0,ID1}; C randomly picks ti,sIDi,kIDi∈Zq∗ and computes RIDi=sIDiP-kIDiPpub,PKIDi=tiP. C inserts (IDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns (RIDi,PKIDi) to A1.(v)Public-key-ReplaceIDRi,RIDi′,PKIDi′: C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C replaces (RIDi,PKIDi) with (IDi,RIDi′,PKIDi′).(vi)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A1.(vii)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.(viii)Decryption(IDRi,σi): C checks if IDRi∈{ID0,ID1} holds, where σi=(Si,Ci,fi). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses full private key (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID0,ID1}, C responds as follows.(ix)C looks up LH4list for (Si,ei,τi). If not, C outputs failure and stops.(x)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.(xi)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise return mi to A1Challenge.After making the above queries, A1 picks plaintext m together with identities {ID2,⋯,IDn} on which he wants to be challenged. C chooses λ∈{0,1} at random and implements the following process.After making the above queries,A1 picks plaintext m together with identities {ID2,⋯,IDn} on which he wants to be challenged. C chooses λ∈{0,1} at random and implements the following process.(i)C sets S∗←b·P.(ii) LetUi=(kIDix+ti)S∗+riX, and compute μi=H3(Ui,IDi,pki),i=1,2,⋯,n.(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(9)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,⋯,n-1(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).Phase 3.In this phase, A1 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{IDλ,ID2,⋯,IDn} and σ∗.In this phase,A1 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{IDλ,ID2,⋯,IDn} and σ∗.Guess. A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A1 wins the game if and only if λ=λ′ holds.A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A1 wins the game if and only if λ=λ′ holds.Based on the above oracle queries, the simulation ofC is perfect. Next, we consider the probability that challenger C fails in Game I. Combined with the previous description, we know that C fails in Decryption query if (Si,ei) is not in LH4list. The probability that A1 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability of C failure in Game I is less than qd/2l1+l2, where qd denotes the decryption query times in the game.IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(10)Pr⁡c=1∣X=abP=Pr⁡λ=λ′∣X=abP=12+ϵ.IfX≠abP, then the ciphertext distribution is random and uniform when λ=0 or λ=1, so A1 cannot distinguish λ with any advantage.(11)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.Therefore, ifA1 can break the ANON-IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. Because the DDH problem is difficult, the proposed CLAMRE scheme is ANON-IND-sMID-CCA secure against A1.Theorem 7.
In the random oracle model, our proposed CLAMRE scheme is ANON-IND-sID-CCA secure against the adversaryA2 with the hardness assumption of CDH problem.Proof.
The proof of this theorem is similar to that of Theorem5. To save space, we will not give the details here.


## 5.1. Security Model

In order to prove the security of the CLAMRE scheme, we take into account of the malicious-but-passive KGC. The robust security model is proposed by Hung et al. [28] in the CLAMRE scheme. Two kinds of adversaries are defined as follows.Type I adversary A 1: A1 is a malicious outside adversary who can replace the users public key with a value chosen by himself/herself. However, A1 cannot access the master private key of KGC.Type II adversary A 2: A2 behaves as a honest-but-curious KGC who owns the master key. However it does not allow him/her to replace public key of any user. Define the security of a CLAMRE scheme as a game played between an adversary A∈{A1,A2} and a challenger C. During the game, A can make the following queries to C.C r e a t e - U s e r query: C generates private key and public key for the user Ui. C sends the user Ui ’s public key to A.P u b l i c - K e y - R e t r i e v e query: C returns the matching user Ui s public key to A.P u b l i c - K e y - R e p l a c e query: C replaces the associated users public key with new public key chosen by himself/herself.P a r t i a l - P r i v a t e - K e y - E x t r a c t query: C sends the users partial private key to A.S e c r e t - V a l u e - E x t r a c t query: C sends the users secret value to A.D e c r y p t i o n query: C decrypts the received ciphertext and sends plaintext to A.We define the confidentiality of a CLAMRE scheme as the indistinguishability against selective multi-identity chosen ciphertext attack (IND-sMID-CCA). The IND-sMID-CCA game is defined as follows.Game I.This game is to prove the confidentiality of the CLAMRE scheme.This game is to prove the confidentiality of the CLAMRE scheme.Phase 1.In this phase, adversary A selects n target users with identities IDR1,IDR2,⋯,IDRn and delivers them to C. C performs setup to generate system parameters and master key.In this phase, adversaryA selects n target users with identities IDR1,IDR2,⋯,IDRn and delivers them to C. C performs setup to generate system parameters and master key.Phase 2. A could adaptively make the aforementioned oracle query but does not allow him/her to make Partial-Private-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.A could adaptively make the aforementioned oracle query but does not allow him/her to make Partial-Private-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.Challenge. A chooses two plaintexts {m0,m1} with the same length, then delivers {m0,m1} to C. C randomly selects λ∈{0,1} and uses {IDR1,IDR2,⋯,IDRn} and the corresponding public key to encrypt the message mλ for generation the ciphertext CT∗. Then C sends CT∗ to A.A chooses two plaintexts {m0,m1} with the same length, then delivers {m0,m1} to C. C randomly selects λ∈{0,1} and uses {IDR1,IDR2,⋯,IDRn} and the corresponding public key to encrypt the message mλ for generation the ciphertext CT∗. Then C sends CT∗ to A.Phase 3.In this phase, A can make the same queries as he/she doesin Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDR1,IDR2,⋯,IDRn}.In this phase,A can make the same queries as he/she doesin Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDR1,IDR2,⋯,IDRn}.Guess.Finally, A outputs λ′∈{0,1}, that is, his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the CLAMRE scheme is defined by AdvCLAMREIND-sMID-CCA(A)=|Pr[λ′=λ]-1/2|.Finally,A outputs λ′∈{0,1}, that is, his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the CLAMRE scheme is defined by AdvCLAMREIND-sMID-CCA(A)=|Pr[λ′=λ]-1/2|.Definition 1.
We say a CLAMRE scheme is IND-sMID-CCA secure ifAdvCLAMREIND-sMID-CCA(A) is negligible for any polynomial-time-bounded adversary A.The receiver anonymity of a CLAMRE scheme is defined by the anonymous indistinguishability against selective identity chosen ciphertext attack (ANON-IND-sID-CCA). The ANON-IND-sID-CCA game is defined as follows.Game II.This game is to prove the anonymity of the CLAMRE schemeThis game is to prove the anonymity of the CLAMRE schemePhase 1.In this phase, A selects two target users with identities {ID0,ID1} and sends them to C. Then C runs setup to generate system parameters and the master key.In this phase,A selects two target users with identities {ID0,ID1} and sends them to C. Then C runs setup to generate system parameters and the master key.Phase 2.In this phase, A could adaptively make the aforementioned the oracle query. However he/she cannot make Create-User,Secret-Value-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.In this phase,A could adaptively make the aforementioned the oracle query. However he/she cannot make Create-User,Secret-Value-Extract/Public-Key-Replace query with ID∈{IDR1,IDR2,⋯,IDRn} if he/she is A1/A2.Challenge. A picks message m together with identities IDR2′,⋯,IDRn′ and sends them to C; C randomly selects λ∈{0,1} and uses {IDλ,IDR2′,⋯,IDRn′} and the corresponding public keys to generate a ciphertext CT∗ of a message mλ. Then C delivers CT∗ to A.A picks message m together with identities IDR2′,⋯,IDRn′ and sends them to C; C randomly selects λ∈{0,1} and uses {IDλ,IDR2′,⋯,IDRn′} and the corresponding public keys to generate a ciphertext CT∗ of a message mλ. Then C delivers CT∗ to A.Phase 3.In this phase, A can make the same queries as he/she does in Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDλ,IDR2′,⋯,IDRn′}.In this phase,A can make the same queries as he/she does in Phase 2 except that he/she cannot make Decryption query with CT∗ and {IDλ,IDR2′,⋯,IDRn′}.Guess.Finally, A returns λ′∈{0,1} as his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the game is defined by AdvCLAMREANON-IND-sID-CCA(A)=|Pr[λ′=λ]-1/2|.Finally,A returns λ′∈{0,1} as his/her guess value about λ. We say that A wins the game if λ′=λ. The advantage is that A against the game is defined by AdvCLAMREANON-IND-sID-CCA(A)=|Pr[λ′=λ]-1/2|.Definition 2.
We say a CLAMRE scheme is ANON-IND-sID-CCA secure ifAdvCLAMREANON-IND-sID-CCA(A) is negligible for any polynomial-time-bounded adversary A.


## 5.2. Security Theorems

In this subsection, we will analyze in detail security of the proposed CLAMRE scheme. Through the analysis, it is shown that the proposed CLAMRE scheme is IND-sMID-CCA secure and ANON-IND-sID-CCA secure against two types of adversariesA1,A2.Theorem 3.
The proposed CLMRE scheme correctly generates the ciphertextσ=(S,C,a), where a=(a1,a2,⋯,an-1) and receiver Ri(1≤i≤n) decrypts it appropriately.Proof.
Due to the fact that(ti+sIDi)S = (ti+ri+kIDix)sP = s(tiP+riP+kIDiPpub) = s(PKIDi+RIDi+kIDiPpub)=Ui, receiver Ri computes the following:μi=H3(Ui,IDi,pki) and e=f(μi).m∥ω=H4(S,e)⊕C, and s=H2(m,ω) is true.
So we proposed that CLAMRE scheme is correct and consistent.Theorem 4.
In the random oracle model, our CLAMRE scheme satisfies the IND-sMID-CCA against the adversaryA1 with the hardness assumption of DDH problem.Proof.
A 1 is the polynomial time-bounded adversary, if A1 has the ability to break the security of the proposed CLAMRE scheme. Then we can construct a probabilistic polynomial time-bounded challenger C to solve the DDH problem by interacting with the adversary A1; that is, given an instance (P,aP,bP,X) of the DDH problem, challenger C is able to determine if X=ab·P holds. Challenger C maintains the following initial-empty lists in order to achieve the consistency between queries made by the adversary A1:
Phase 1
In this phase,A1 selects n target identities; we denote these identities as ID1,⋯,IDn.
C sets Ppub←x·P, and executes setup algorithm to generate other parameters. Then C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A1. To achieve the random oracles, C maintains four lists LHilist, where LHilist is initialized empty (i=1,2,3,4). The four random oracles make the following answer for A1s queries.
(i)H1(IDi,PKIDi,RIDi):C checks if (IDi,PKIDi,RIDi,kIDi) exists in LH1list. If so, C sends kIDi to A1. Otherwise, C randomly chooses value kIDi∈Zq∗, inserts (IDi,PKIDi,RIDi,kIDi) into LH1list, and sends kIDi.
(ii)H2(m,ω): C checks if (m,ω,s) exists in LH1list. If so, C returns s to A1. Otherwise, C randomly chooses value s∈Zq∗, inserts (m,ω,s) into LH2list, and returns s.
(iii)H3(Ui,IDi,pki): C checks if (Ui,IDi,pki,μi) exists in LH3list. If so, C returns μi to A1. Otherwise, C randomly chooses value μi∈Zq∗, inserts (Ui,IDi,pki,μi) into LH3list, and returns μi.
(iv)H4(S,e): C checks if (S,e,τ) exists in LH4list. If so, C returns τ to A1. Otherwise, C randomly selects an element τ∈{0,1}l1+l2, inserts (S,e,τ) into LH4list, and returns τ.
Phase 2
A 1 can adaptively make queries to C.C maintains a list LRlist, which is initialized empty. Challenger C responded to these queries made by adversary A1 as follows.
(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A1. Otherwise, C executes the following processes.
(ii) IfIDRi∈{ID1,⋯,IDn} holds, without losing generality, we suppose IDRi=IDi, C randomly picks ri,ti∈Zq∗, computes PKIDi=tiP,RIDi=riaP,kIDi=H1(IDi,PKIDi,RIDi), and sets sIDi←⊥. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.
(iii) OtherwiseIDRi∉{ID1,⋯,IDn}; C randomly picks ti,sIDi,kIDi∈Zq∗ and computes RIDi=sIDiP-kIDiPpub,PKIDi=tiP. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.
(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns (RIDi,PKIDi) to A1.
(v)Public-key-Replace(IDRi,RIDi′,PKIDi′): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C replaces (RIDi,PKIDi) with (IDi,RIDi′,PKIDi′)
(vi)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A1.
(vii)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.
(viii)Decryption(IDRi,σi): C checks if IDRi∈{ID1,⋯,IDn} holds, where σi=(Si,Ci,fi). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID1,⋯,IDn},C responds according to the following steps.
(ix)C looks up LH4list for (Si,ei,τi). If not, C outputs failure and stops.
(x)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.
(xi)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise return mi to A1
Challenge.   After making the above queries, A1 picks two messages m0 and m1 with length l2 and sends them to challenger C,C chooses λ∈{0,1} at random and performs the following steps.
(i)C sets S∗←b·P.
(ii) LetUi=(kIDix+ti)S∗+riX, and compute μi=H3(Ui,IDi,pki),i=1,2,⋯,n
(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(3)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,…,n-1
(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).
Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).
Phase 3
In this phase,A1 can make the same queries in Phase 2 except that it cannot make decryption queries with ID∗∈{ID1,ID2,⋯,IDn} and σ∗.
Guess
A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise,C outputs 0. A1 wins the game if and only if λ=λ′ holds.
Based on the above oracle queries, the simulation ofC is perfect. Next, we consider the probability that challenger C fails in Game I. Combined with the previous description, we know that C fails in Decryption query if (Si,ei) is not in LH4list. The probability that A1 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability of C failure in game I is less than qd/2l1+l2, where qd denote the decryption query times in the game.
IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(4)Prc=1∣X=abP=Prλ=λ′∣X=abP=12+ϵ.
IfX≠abP, then the ciphertext distribution is random and uniform when λ=0 or λ=1, so A1 cannot distinguish λ with any advantage.(5)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.
Therefore, ifA1 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2, because the DDH problem is difficult. Therefore, the proposed CLAMRE scheme is IND-sMID-CCA secure against A1.Theorem 5.
Our CLAMRE scheme is IND-sMID-CCA secure against type II adversaryA2 under random oracle model with the difficulties of computational Diffie-Hellman problem.Proof.
A 2 is the polynomial time-bounded adversary, if A2 has the ability to break the security of the proposed CLAMRE scheme. Then we can construct a probabilistic polynomial time-bounded challenger C to solve the DDH problem by interacting with the adversary A2; that is, for given an instance (P,aP,bP,X) of the DDH problem, challenger C is able to determine if X=ab·P holds. Challenger C maintains the following initial-empty lists in order to achieve the consistency between queries made by adversary A2.
Phase 1
In this phase,A2 selects n target identities; we denote these identities as ID1,⋯,IDn.
C picks x∈Zq∗ at random as system private key and computes corresponding public key Ppub=x·P. C performs Setup algorithm to construct other parameters. At last, C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A2 and master private key x to A2. To achieve the random oracles, C maintains four lists LHilist, where initial LHilist is empty (i=1,2,3,4). The four random oracles make the following answer for A2s queries.
(i)H1(IDi,PKIDi,RIDi): C checks if (IDi,PKIDi,RIDi,kIDi) exists in LH1list. If so, C returns kIDi to A2. Otherwise, C randomly selects an element kIDi∈Zq∗, inserts (IDi,PKIDi,RIDi,kIDi) into LH1list, and returns kIDi.
(ii)H2(m,ω): C checks if (m,ω,s) exists in LH1list. If so, C returns s to A2. Otherwise, C randomly selects an element s∈Zq∗, inserts (m,ω,s) into LH2list, and returns s.
(iii)H3(Ui,IDi,pki): C checks if (Ui,IDi,pki,μi) exists in LH3list. If so, C returns μi to A2. Otherwise, C randomly selects an element μi∈Zq∗, inserts (Ui,IDi,pki,μi) into LH3list, and returns μi.
(iv)H4(S,e): C checks if (S,e,τ) exists in LH4list. If so, C returns τ to A2. Otherwise, C randomly selects an element τ∈{0,1}l1+l2, inserts (S,e,τ) into LH4list, and returns τ.
Phase 2
In this phase,A2 can adaptively make a lot of queries to C. C maintains a list LRlist, which is initialized empty. These queries are responded as follows.
(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A2. Otherwise, C performs the following steps.
(ii) IfIDRi∈{ID1,⋯,IDn} holds, without losing generality, we suppose IDRi=IDi,C randomly chooses ri,ti∈Zq∗ and calculates PKIDi=ti·aP,RIDi=riP,kIDi=H1(PKIDi,Ri,IDi),sIDi=ri+kIDix mod q. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A2.
(iii) OtherwiseIDRi∉{ID1,⋯,IDn}; C randomly picks ti,ri,kIDi∈Zq∗ and computes RIDi=riP,sIDi=ri+kIDis mod q, PKIDi=ti·P. C inserts (IDi,PKIDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A2.
(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns RIDi,PKIDi to A2.
(v)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A2.
(vi)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LR. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.
(vii)Decryption(IDRi,σi): C checks if IDRi∈{ID1,⋯,IDn} holds, where σi=(Si,Ci,ai),ai=(ai0,ai1,⋯,ai(n-1)). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID1,⋯,IDn},C responds according to the following steps.
(viii)C looks up L4list for (Si,ei,τi). If not, C outputs failure and stops.
(ix)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.
(x)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise, return mi to A2
Challenge
After making the above queries,A2 picks two messages m0 and m1 with length l2 and sends them to challenger C; C chooses λ∈{0,1} at random and implements the following process.
(i)C sets S∗←b·P.
(ii) LetUi=(kIDix+ri)S∗+ti·X, and compute μi=H3(Ui,IDi,pki).i=1,2,⋯,n
(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(6)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,…,n-1
(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).
Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).
Phase 3
In this phase,A2 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{ID1,ID2,⋯,IDn} and σ∗.
Guess
A 2 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A2 wins the game if and only if λ=λ′ holds.
According to the above oracle queries, we know that the simulation ofC is perfect. Now, we analyze the probability that C fails in Game I. Based on the above description, we know that C fails in decryption query if (Si,ei) is not in L4list. The probability that A2 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability that C fails in the game is less than qd/2l1+l2, where qd denotes the decryption queries involved in the game.
IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(7)Prc=1∣X=abP=Prλ=λ′∣X=abP=12+ϵ.
IfX≠abP, then the ciphertext distribution is random and uniform when λ=0orλ=1. So A2 cannot distinguish λ with any advantage.(8)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.
Therefore, ifA2 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. If A2 can break the IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then we know C can solve the CDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. Due to the fact that the CDH problem is hard, we know that the proposed CLAMRE scheme is IND-sMID-CCA secure against adversary A2.Theorem 6.
In the random oracle model, our proposed CLAMRE scheme is ANON-IND-sID-CCA secure against adversaryA1 with the difficulty assumption of DDH problem.Proof.
Assume that the adversaryA1 can breach our CLAMRE scheme, then we will be able to design a challenger C for solving an instance of DDH problem; that is, for given an instance (P,a·P,b·P,X) of DDH problem, challenger C can determine if X=abP holds by interacting with adversary A1. Similar to Theorem 4, let lists LHilist(i=1,2,3,4) and LRlist be maintained by challenger C.Phase 1.Assume that adversary A1 selects two target users with identities ID0,ID1. Challenger C randomly selects λ∈{0,1}Assume that adversaryA1 selects two target users with identities ID0,ID1. Challenger C randomly selects λ∈{0,1}C sets Ppub←x·P, and implements Setup algorithm to construct other parameters. At last, C delivers {p,q,l1,l2,E,G,Gq,P,Ppub,H1,H2,H3,H4} to A1. Challenger C returns answers to the adversary A1s queries in the following ways.Hash queries toHi(i=1,2,3,4): these queries are the same as those performed in Theorem 4.Phase 2.Now, challenger C will respond to the queries made by the adversary A1 in the following ways.Now, challengerC will respond to the queries made by the adversary A1 in the following ways.(i)Create-User(IDRi) query: C checks if (IDRi,ri,sIDi,ti,RIDi,PKIDi) exists in LRlist. If so, C returns (RIDi,PKIDi) to A1. Otherwise, C executes the following processes.(ii) IfIDRi=IDj for j∈{0,1} holds, C randomly chooses ri,ti∈Zq∗, computes PKIDi=ti·P,RIDi=ri·aP,kIDi=H1(IDi,PKIDi,RIDi), and sets sIDi←⊥. C inserts (IDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into LH1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.(iii) OtherwiseIDRi∉{ID0,ID1}; C randomly picks ti,sIDi,kIDi∈Zq∗ and computes RIDi=sIDiP-kIDiPpub,PKIDi=tiP. C inserts (IDi,RIDi,kIDi) and (IDi,ri,sIDi,ti,RIDi,PKIDi) into L1list and LRlist, respectively. At last, C returns (RIDi,PKIDi) to A1.(iv)Public-Key-Retrieve(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C returns (RIDi,PKIDi) to A1.(v)Public-key-ReplaceIDRi,RIDi′,PKIDi′: C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDi first. Then, C replaces (RIDi,PKIDi) with (IDi,RIDi′,PKIDi′).(vi)Partial-Private-Key-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns sIDi to A1.(vii)Secret-Value-Extract(IDRi): C checks if (IDRi,sIDi,ti,RIDi,PKIDi) exists in LRlist. If not, C makes the Create-User query with IDRi first. Then, C returns ti to A1.(viii)Decryption(IDRi,σi): C checks if IDRi∈{ID0,ID1} holds, where σi=(Si,Ci,fi). If not, C looks up LRlist for (IDRi,sIDi,ti,RIDi,PKIDi) and uses full private key (sIDi,ti) to decrypt the ciphertext. Otherwise IDRi∈{ID0,ID1}, C responds as follows.(ix)C looks up LH4list for (Si,ei,τi). If not, C outputs failure and stops.(x)C searches the tuple (mi,ωi,si) from LH2list and checks if Si=siP holds. If so, C keeps (mi,ωi); if not, C outputs failure and stops.(xi)C checks if Ci=τi⊕(mi∥ωi) holds. If not, C outputs failure and stops. Otherwise return mi to A1Challenge.After making the above queries, A1 picks plaintext m together with identities {ID2,⋯,IDn} on which he wants to be challenged. C chooses λ∈{0,1} at random and implements the following process.After making the above queries,A1 picks plaintext m together with identities {ID2,⋯,IDn} on which he wants to be challenged. C chooses λ∈{0,1} at random and implements the following process.(i)C sets S∗←b·P.(ii) LetUi=(kIDix+ti)S∗+riX, and compute μi=H3(Ui,IDi,pki),i=1,2,⋯,n.(iii)C chooses e∈Zq∗ at random and computes a polynomial f(x) with degree n as follows:(9)fx=∏i=1nx-μi+emod⁡q=xn+an-1∗xn-1+⋯+a1∗x+a0∗,whereai∈Zq∗i=0,1,⋯,n-1(iv)C chooses τ∗∈{0,1}l1+12 and ω∗∈{0,1}l2 at random and computes C∗=τ∗⊕(mλ∥ω∗).Final,C sends the ciphertext σ∗=(S∗,C∗,f∗).Phase 3.In this phase, A1 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{IDλ,ID2,⋯,IDn} and σ∗.In this phase,A1 can make the same queries in Phase 2 except that he cannot make decryption queries with ID∗∈{IDλ,ID2,⋯,IDn} and σ∗.Guess. A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A1 wins the game if and only if λ=λ′ holds.A 1 outputs λ′∈{0,1} as his/her guess value about λ. If λ=λ′, then C outputs 1; otherwise, C outputs 0. A1 wins the game if and only if λ=λ′ holds.Based on the above oracle queries, the simulation ofC is perfect. Next, we consider the probability that challenger C fails in Game I. Combined with the previous description, we know that C fails in Decryption query if (Si,ei) is not in LH4list. The probability that A1 can correctly guess the output of H4:{0,1}∗→{0,1}l1+l2 is 1/2l1+l2. Therefore, the probability of C failure in Game I is less than qd/2l1+l2, where qd denotes the decryption query times in the game.IfX=abP holds, then σ∗ is valid ciphertext. Thus, A1 is able to distinguish λ with nonnegligible advantage ϵ.(10)Pr⁡c=1∣X=abP=Pr⁡λ=λ′∣X=abP=12+ϵ.IfX≠abP, then the ciphertext distribution is random and uniform when λ=0 or λ=1, so A1 cannot distinguish λ with any advantage.(11)Prc=1∣X≠abP=Prλ=λ′∣X≠abP=12.Therefore, ifA1 can break the ANON-IND-sMID-CCA security of the proposed CLAMRE scheme with nonnegligible advantage ϵ, then challenger C can solve the DDH problem with a nonnegligible advantage ϵ-qd/2l1+l2. Because the DDH problem is difficult, the proposed CLAMRE scheme is ANON-IND-sMID-CCA secure against A1.Theorem 7.
In the random oracle model, our proposed CLAMRE scheme is ANON-IND-sID-CCA secure against the adversaryA2 with the hardness assumption of CDH problem.Proof.
The proof of this theorem is similar to that of Theorem5. To save space, we will not give the details here.


## 6. Performance Analysis

In this section, we mainly analyzed computational cost of the proposed CLAMRE scheme. The proposed CLAMRE scheme is compared with Hung et al.'s CLAMRE scheme (Hung et al. 2015) and He et al.'s CLAMRE scheme (He et al. 2017) to calculate cost.LetG1 be an additive group defined on a super singular elliptic curve over a prime field Fp with the prime order q, and the lengths of q and p are 512 bits and 160 bits, respectively. The Tate bilinear pairing e^:G1×G1→G2, in order to achieve the same security. For the CLAME scheme based on the elliptic curve cryptography, we also think about an additive group G^ defined on a nonsingular elliptic curve over a prime field Fp with the prime order q; lengths of p and q are 160 bits. For convenience, the concept of runtime for some cryptographic operations is defined as follows.(i)Tbp is the runtime required for computing a bilinear pairing.(ii)THTP is the runtime required for finishing a hash-to-point operation.(iii)Tsm-G1 is the runtime required for computing a scale multiplication in G1.(iv)Tadd-G1 is the runtime required for computing an addition in G1.(v)Tmul-G2 is the runtime required for computing a multiplication in G2.(vi)Texp-G2 is the runtime required for executing an exponentiation operation in G2.(vii)Tsm-G^ is the runtime required for computing a scale multiplication in G^.(viii)Tadd-G^ is the runtime required for computing an addition in G^.(ix)Tgh is the runtime required for executing a general hash operation.(x)Tsc is the runtime required for executing a symmetric cryptography operation.He et al.[30] have implemented related operations on a mobile phone (Samsung Galaxy S5 with a Quad-core 2.45G processor, 2G bytes memory, and the Google Android 4.4.2 operating system) using a famous cryptographic library (MIRACL). The implementation results are shown in Table 1.Table 1
Runtime of related operations.
Notations Runtime (milliseconds) Tbp 32.713 Thtp 33.582 Tsm-G1 13.405 Tadd-G1 0.056 Texp-G2 2.249 Tmul-G2 0.008 Tsm-G^ 3.335 Tadd-G^ 0.014 Tgh 0.006 Tsc 0.001We denoten the number of the receivers. In order to encrypt a given message m, in Hung et al.'s CLAMRE scheme, the sender needs to perform 2n scale multiplication operations in G1, n bilinear pairing operations, n exponentiation operations in G2, n hash-to-point operations, 3n+2 general hash operations, and one symmetric cryptography operation. Therefore, in Hung et al.'s CLAMRE scheme, the runtime of the sender is n×Tbp+n×Thtp+2n×Tsm-G1+n×Texp-G2+(3n+2)×Tgh+Tsc=n×32.713+n×33.582+2n×13.405+n×2.249+(3n+2)×0.006+0.001=(95.372×n+0.013) ms. For decrypting the received ciphertext, receiver needs to implement following operations: one scale multiplication in G1, one bilinear pairing, five general hash, and one symmetric cryptography operations. Therefore, the runtime of the receiver in Hung et al.'s CLAMRE scheme is Tbp+Tsm-G1+5×Tgh+Tsc=32.713+13.405+5×0.006+0.001=46.149ms.In He et al.’s [29] scheme, to encrypt a given message m, the sender needs to perform the following operations: n times addition in G^, 3n+1 times scale multiplication in G^, 4n+2 times general hash, and one symmetric encryption operation and n times exclusive or operation (here, exclusive or operation is approximately equal to symmetric encryption operation). Therefore, the runtime of encryption is (3n+1)×Tsm-G^+n×Tadd-G^+(4n+2)×Tgh+(n+1)Tsc=(3n+1)×3.335+n×0.014+(4n+2)×0.006+(n+1)0.001=(10.044n+3.348)ms. In order to get plaintext from the received ciphertext, the receiver needs to finish seven general hash operations, two scale multiplication operations in G^, one symmetric encryption operation, and one exclusive or operation. Therefore, the runtime of the receiver in our scheme is 2×Tsm-G^+7×Tgh+2Tsc=6.714ms.In the proposed CLAMRE scheme, to encrypt a given messagem, the sender needs to perform the following operations: 2n times addition in G^, 2n+1 times scale multiplication in G^, n+2 times general hash, and one exclusive or operation. Therefore, in our CLAMRE scheme, the runtime of the sender is (2n+1)×Tsm-G^+2n×Tadd-G^+(n+2)×Tgh+Tsc=(2n+1)×3.335+2n×0.014+(n+2)×0.006+0.001=(6.704n+3.348)ms. In order to get plaintext from the received ciphertext, the receiver needs to finish three general hash operations, two scale multiplication operations in G^, and one exclusive or operation. Therefore, the runtime of the receiver in our scheme is 2×Tsm-G^+3×Tgh+Tsc=6.689ms.We list the runtime of encryption and decryption in Huang et al.’s scheme, He et al.’s scheme, and our scheme in Table2. For a more intuitive understanding, we also present the runtime of multiencryption algorithms in Figure 2. According to comparisons in Table 2 and Figure 2, we can conclude that the proposed CLAMRE scheme has much less runtime in both encryption and decryption than the recent scheme. Therefore, our proposed CLAMRE scheme has better performance.Table 2
Comparison of runtime (milliseconds).
Encryption Decryption Hung’s scheme 95.372×n+0.013 46.149 He’ scheme 10.044 × n + 3.348 6.714 Our scheme 6.704×n+3.348 6.689Figure 2
Runtime comparison of multiencryption (milliseconds).


## 7. Conclusion

In order to keep up with the rapid development of mobile Internet, in this study, we proposed an efficient CLAMRE scheme using the elliptic curve cryptography. By comparing with recent literature, it shows that our scheme has better performance. We also demonstrate that the proposed CLAMRE scheme provides message confidentiality and protects the privacy of receiver under the random oracle model with the difficulties of decision Diffie-Hellman problem and against the adversaries defined in CL-PKC system.In summary, our CL-MRE scheme has the following merits: (1) in encryption and decryption process, not using bilinear pairing and probabilistic HTP hash function; (2) achieving confidentiality of message and protecting the privacy of receiver; (3) resisting all known security attacks; (4) low computation and communication costs; (5) avoidance of private key escrow problem and public key certificate management; (6) provable security against IND-sMID-CAA and ANON-IND-sID-CAA under the random oracle.



---

*Source: 1486437-2018-07-24.xml*