# Pairing-Free Certificateless Signature with Security Proof

Authors: Wenhao Liu; Qi Xie; Shengbao Wang; Lidong Han; Bin Hu
Journal: Journal of Computer Networks and Communications
 (2014)

---

## Abstract

Since certificateless public key cryptosystem can solve the complex certificate management problem in the traditional public key cryptosystem and the key escrow problem in identity-based cryptosystem and the pairing computation is slower than scalar multiplication over the elliptic curve, how to design certificateless signature (CLS) scheme without bilinear pairings is a challenge. In this paper, we first propose a new pairing-free CLS scheme, and then the security proof is presented in the random oracle model (ROM) under the discrete logarithm assumption. The proposed scheme is more efficient than the previous CLS schemes in terms of computation and communication costs and is more suitable for the applications of low-bandwidth environments.


---

## Body

## 1. Introduction

In 2003, Al-Riyami and Paterson [1] first introduced the concept of certificateless public key cryptosystem (CL-PKC). The basic idea of CL-PKC is to construct the user’s public/private key pair by combining a master key of the key generation center (KGC) with a random secret value generated by the user. Hence, the KGC is unable to compute the user’s private key, and each user has one additional random public key and this public key does not need to be certified by a trusted third party in CL-PKC. Thus, CL-PKC not only eliminates the certificates in PKC but also solves the key escrow problem in identity-based public key cryptosystem (ID-PKC). As a classical signature scheme, it should provide existential unforgeability, which ensures that the adversary cannot forge a valid signature. In the formal security model of CLS scheme, two types of adversaries should be considered. Type I adversary is allowed to replace user’s public key; however, it cannot access the master key of KGC, while Type II adversary is allowed to know the master key of KGC but cannot replace the target user’s public key.The first CLS scheme was proposed by Al-Riyami and Paterson [1]. Following their works, Huang et al. [2] pointed out that Al-Riyami et al.’s scheme is insecure against Type I adversary. Later, Yum and Lee [3] presented a generic construction of CLS scheme. Hu et al. [4] demonstrated that their scheme is also insecure against Type I adversary. Gorantla and Saxena [5] proposed an efficient CLS scheme, but Cao et al. [6] showed that their scheme is insecure against Type I adversary. Since then, many CLS schemes [7–15] have been proposed. However, only few of them, for example, [10–12], are secure against these two types of adversaries; others are vulnerable to the key replacement attack.With the rapid development of wireless network technology, more and more users use their mobile devices to deal with the transactions. However, almost all of the above-mentioned schemes cannot be used in the low-bandwidth communication and low-storage and less computation environments. Therefore, many researchers tried to design short CLS schemes. In 2007, Huang et al. [16] proposed the first CLSS scheme. After that, Du and Wen [17] and Choi et al. [18] proposed CLSS schemes, respectively. Unfortunately, all of them are vulnerable to the key replacement attack launched by a Type I adversary; what is more, they still need bilinear pairing computations. As we know, the computation cost of a pairing is approximately 20 times higher than that of the scalar multiplication over an elliptic curve group [19, 20]. Therefore, how to design a pairing-free CLSS scheme is an attractive topic.Recently, He et al. [21] proposed an efficient certificateless signature scheme without pairings; Tian and Huang [22] and Tsai et al. [23] pointed out that the scheme cannot withstand a Type II adversary’s attack. Tsai et al. [23] also proposed an improved new scheme in order to enhance security. Gong and Li [24] pointed out the new scheme is insecure against the super adversary in the random oracle model, and they proposed a real CLS scheme and demonstrated that their scheme is secure against the supper adversary. Yeh et al. [25] proposed a secure certificateless signature scheme without pairings in 2014. In this paper, we propose a new CLS scheme without bilinear pairings, and is provable secure in the random oracle model (ROM) under the discrete logarithm assumption.The rest of this paper is organized as follows. In Section2, we present the preliminaries including the elliptic curve, bilinear pairings, some hard problems, and complexity assumptions. A new CLS scheme and the security proof are presented in Sections 3 and 4, respectively. After that, we show the performance comparison among our scheme and other related schemes in Section 5. Finally, we conclude the paper in Section 6.


## 2. Preliminaries

In this section, we present some definitions and assumptions which are needed in the rest of the paper.


### 2.1. Elliptic Curve

Let the symbolE/Fp be an elliptic curve E over a prime finite field Fp; an equation y2=x3+ax+b, a,b∈Fp with the discriminant Δ=4a3+27b2≠0.  The point on E/Fp together with an extra point O, called the point at infinity, forms a group G={(x,y):x,y∈Fp,E(x,y)=0}∪{O}. We define tP=P+P+⋯+P (t times) as scalar multiplication. Let q be the order of G.


### 2.2. Bilinear Pairings

LetG be a cyclic additive group of prime order q and let G2 be a cyclic multiplicative group with the same order q; P is a generator. A bilinear pairing is a map e:G×G→G2 with the following properties.(1)
Bilinearity: ifP,Q,R∈G, then e(P+Q,R)=e(P,R)e(Q,R).(2)
Nondegeneracy: there exists aP∈G such that e(P,P)≠IG2, where IG2 is the identity element of G2.(3)
Computability: there exists an efficient algorithm to computee(P,Q) for all P,Q∈G.


### 2.3. Hard Problems and Complexity Assumptions

Discrete logarithm problem (DLP): letP be a generator of group G. Given a tuple (P,xP)∈G for x∈Zq*, it is hard to compute x.DL Assumption. There exists no algorithm running in expected polynomial time, which can solve the DLP with nonnegligible probability.


### 2.4. Security Model

The security model of CLS can be referred to [3, 7, 8]. There are two types of adversaries for a CLS scheme, aType I adversary A1 and aType II adversary A2. A1 represents an attacker who is not allowed access to the master key of KGC but he may replace public keys. A2 represents an attacker who is allowed access to the master key of KGC but he cannot replace public keys.In general, we use two games to define the existential unforgeability of a CLS scheme against aType I adversary A1 and aType II adversary A2.Game 1. A challenger C takes a security parameter k and generates a master private key s and public parameterparams and then sendsparams to A1 and keeps s secret. A1 executes the game according to the following steps.Create(ID). On input an identity ID∈{0,1}*, if ID has already been created, nothing is to be carried out. Otherwise, C generates the public/private key pair (PKID,SKID).Public-Key(ID). On input an identity ID,  C outputs the public key PKID to A1.Partial-Private-Key-Extract. On input an identity ID,  C outputs the partial key DID.Set-Secret-Key. On input a user’s identity ID,  C outputs the private key SKID=(xID,DID).Public-Key-Replacement(ID,
P
K
I
D
′
). For a participant whose identity is IDi, A1 chooses a new public key PKID′ and then sets PKID′ as the new public key of this participant. C will record this replacement, which will be used later.Sign(ID,
m
). On input (ID,m,PKID),  C uses the private key (xID,DID) to compute the signature σ and returns it to A1. If the public key PKID has been replaced by A1, then C cannot find (xID,DID); the answer of the signing oracle may be incorrect. In this situation, we assume that C submits a secret value r corresponding to the replaced public key PKID to the signing oracle.At the end,A1 outputs a signature σ on the message m corresponding to the public key PKID* for an identity ID*, which is the challenge identity. A1 wins the game if the following conditions hold.(1)
Verify(params,ID,m,PKID*,σ)=1.(2)
(ID*,m) has never been submitted to the oracleSign.(3)
ID* has never been submitted to thePartial-Private-Key-Extract query orSet-Secret-Key query.IfA1 has the advantage at least ε in the above game, runs in time at most t, and makes at most qC Create(ID) queries, qSSign queries, and qHhash queries, respectively, then A1 is said to be an (ε,t,qC,qS,qH)-forger. If there exists no such forger, then a signature scheme is said to be (ε,t,qC,qS,qH)-secure against Type I adversary.Game 2. A challenger C is playing the game with Type II adversary A2.A challengerC takes a security parameter k, generates a master private key s and public parameterparams, and then sendsparams and s to A2. C answersCreate(ID),Public-Key(ID),Set-Secret-Key,Partial-Private-Key-Extract, andSign(ID,m) queries from A2, like does inGame 1.At the end,A2 outputs a signature σ on the message m corresponding to the public key PKID* for an identity ID*, which is the challenge identity. A2 wins the game if the following conditions hold.(1)
Verify(params,ID,m,PKID*,σ)=1.(2)
(ID*,m) has never been submitted to the oracleSign.(3)
ID* has never been submitted to theSet-Secret-Key query.IfA2 has the advantage at least ε in the above game, runs in time at most t, and makes at most qCCreate(ID) queries, qSSign queries, and qHhash queries, respectively, then A2 is said to be an (ε,t,qC,qS,qH)-forger. If there exists no such forger, then a signature scheme is said to be (ε,t,qC,qS,qH)-secure against Type II adversary.


## 2.1. Elliptic Curve

Let the symbolE/Fp be an elliptic curve E over a prime finite field Fp; an equation y2=x3+ax+b, a,b∈Fp with the discriminant Δ=4a3+27b2≠0.  The point on E/Fp together with an extra point O, called the point at infinity, forms a group G={(x,y):x,y∈Fp,E(x,y)=0}∪{O}. We define tP=P+P+⋯+P (t times) as scalar multiplication. Let q be the order of G.


## 2.2. Bilinear Pairings

LetG be a cyclic additive group of prime order q and let G2 be a cyclic multiplicative group with the same order q; P is a generator. A bilinear pairing is a map e:G×G→G2 with the following properties.(1)
Bilinearity: ifP,Q,R∈G, then e(P+Q,R)=e(P,R)e(Q,R).(2)
Nondegeneracy: there exists aP∈G such that e(P,P)≠IG2, where IG2 is the identity element of G2.(3)
Computability: there exists an efficient algorithm to computee(P,Q) for all P,Q∈G.


## 2.3. Hard Problems and Complexity Assumptions

Discrete logarithm problem (DLP): letP be a generator of group G. Given a tuple (P,xP)∈G for x∈Zq*, it is hard to compute x.DL Assumption. There exists no algorithm running in expected polynomial time, which can solve the DLP with nonnegligible probability.


## 2.4. Security Model

The security model of CLS can be referred to [3, 7, 8]. There are two types of adversaries for a CLS scheme, aType I adversary A1 and aType II adversary A2. A1 represents an attacker who is not allowed access to the master key of KGC but he may replace public keys. A2 represents an attacker who is allowed access to the master key of KGC but he cannot replace public keys.In general, we use two games to define the existential unforgeability of a CLS scheme against aType I adversary A1 and aType II adversary A2.Game 1. A challenger C takes a security parameter k and generates a master private key s and public parameterparams and then sendsparams to A1 and keeps s secret. A1 executes the game according to the following steps.Create(ID). On input an identity ID∈{0,1}*, if ID has already been created, nothing is to be carried out. Otherwise, C generates the public/private key pair (PKID,SKID).Public-Key(ID). On input an identity ID,  C outputs the public key PKID to A1.Partial-Private-Key-Extract. On input an identity ID,  C outputs the partial key DID.Set-Secret-Key. On input a user’s identity ID,  C outputs the private key SKID=(xID,DID).Public-Key-Replacement(ID,
P
K
I
D
′
). For a participant whose identity is IDi, A1 chooses a new public key PKID′ and then sets PKID′ as the new public key of this participant. C will record this replacement, which will be used later.Sign(ID,
m
). On input (ID,m,PKID),  C uses the private key (xID,DID) to compute the signature σ and returns it to A1. If the public key PKID has been replaced by A1, then C cannot find (xID,DID); the answer of the signing oracle may be incorrect. In this situation, we assume that C submits a secret value r corresponding to the replaced public key PKID to the signing oracle.At the end,A1 outputs a signature σ on the message m corresponding to the public key PKID* for an identity ID*, which is the challenge identity. A1 wins the game if the following conditions hold.(1)
Verify(params,ID,m,PKID*,σ)=1.(2)
(ID*,m) has never been submitted to the oracleSign.(3)
ID* has never been submitted to thePartial-Private-Key-Extract query orSet-Secret-Key query.IfA1 has the advantage at least ε in the above game, runs in time at most t, and makes at most qC Create(ID) queries, qSSign queries, and qHhash queries, respectively, then A1 is said to be an (ε,t,qC,qS,qH)-forger. If there exists no such forger, then a signature scheme is said to be (ε,t,qC,qS,qH)-secure against Type I adversary.Game 2. A challenger C is playing the game with Type II adversary A2.A challengerC takes a security parameter k, generates a master private key s and public parameterparams, and then sendsparams and s to A2. C answersCreate(ID),Public-Key(ID),Set-Secret-Key,Partial-Private-Key-Extract, andSign(ID,m) queries from A2, like does inGame 1.At the end,A2 outputs a signature σ on the message m corresponding to the public key PKID* for an identity ID*, which is the challenge identity. A2 wins the game if the following conditions hold.(1)
Verify(params,ID,m,PKID*,σ)=1.(2)
(ID*,m) has never been submitted to the oracleSign.(3)
ID* has never been submitted to theSet-Secret-Key query.IfA2 has the advantage at least ε in the above game, runs in time at most t, and makes at most qCCreate(ID) queries, qSSign queries, and qHhash queries, respectively, then A2 is said to be an (ε,t,qC,qS,qH)-forger. If there exists no such forger, then a signature scheme is said to be (ε,t,qC,qS,qH)-secure against Type II adversary.


## 3. The Proposed CLS Scheme

In this section, we propose a new CLS scheme, which consists of seven algorithms:Setup,Partial-Private-Key-Extract,Set-Secret-Key,Set-Private-Key,Set-Public-Key,Sign, andVerify. The details are described as follows.Setup. On input a security parameter k, and return system parameters and master key:(1)
KGC generates a cyclic additive groupG and a cyclic multiplicative group G2 with the same order q;(2)
KGC chooses a generatorP∈G and two cryptographic secure hash functions H1:{0,1}*×G→Zq* and H2:{0,1}*→Zq*;(3)
KGC picks a random master private keyx∈Zq* and computes Ppub=xP;(4)
KGC publishes system parametersparams={e,P,G,G2,H1,H2,Ppub} and keeps x secret.Partial-Private-Key-Extract. On inputparams, system master key x and a random value rA, user A’s identity IDA, compute RA=rAP, QA=H1(IDA,RA), and DA=rA+xQA, output DA through a secret channel, and publish RA.Set-Secret-Key. On input the security parameter k and a user’s identity IDA, compute XA=xAP and set xA as his secret value.Set-Private-Key. On input xA,DA and a user’s identity IDA, output the user’s private key (xA,DA).Set-Public-Key. On input a user’s identity IDA, output the user’s public key (XA,QA).Sign. On input params, IDA, (xA,DA), and message m,  perform the following steps.(1)
Choose a random numbera∈Zq* to compute TA=aP.(2)
Computeh=H2(IDARAmTAXA).(3)
Computes=a/(hxA+DA).(4)
Returnσ=(s,h) as the signature on the message m.Verify. On inputparams, IDA, TA, RA, (XA,QA), m, and σ,  compute QA=H1(IDA,RA) and h=H2(IDARAmTAXA). Check whether H2(IDARAms(hXA+RA+QAPpub)XA)=h holds or not. If the equation holds, output 1, otherwise 0.We can easily see that the following equation is correct:(1)shXA+RA+QAPpub=ahxA+rA+xQA-1hxA+rAP+QAxP=aP=TA.Therefore, our CLS scheme is correct.


## 4. Security Analysis

In this section, we will show that the proposed scheme is secure in the random oracle model under the discrete logarithm assumption.Theorem 1.
IfType I andType II adversaries can forge a CLS scheme in probabilistic polynomial time t with nonnegligible probability ε, then the discrete logarithm problem can be solved with nonnegligible probability ϵ′≥ε/(q12q2), where qi (i=1,2) are denoted by the times of accessing Hi (i=1,2) oracles, respectively.Proof.
Firstly, we considerType I attack.
Suppose that there exists aType I adversary A1 which has a nonnegligible probability ε in attacking our CLS scheme; we construct a challenger C that uses A1 to solve the DLP. Challenger C receives a DL instance y=vP for randomly chosen v∈Zq* and P∈G and wants to compute v. C runs A1 as a subroutine and simulates its attack situations. C sets Ppub=y, where v is the master key, which is unknown to C, and returns system parameters to A1. C maintains initially empty lists LC, LH1, LH2, LD, LSK, LPK, LS, and LV in order to simulate the oracle queries of A1 as follows.
Create(
I
D
i
).  C maintains list LC of tuple (ID,Ri,Pi,Di,xi,hi). C responds with (ID,Ri,Pi,Di,xi,hi) if IDi is on LC. Otherwise, it chooses three random values ai,bi,xi∈Zq*, sets Ri=aiP-biPpub, Di=ai, hi=H1(IDi,Ri), hi=bi, and PKi=xiP, responds with (ID,Ri,PKi,Di,xi,hi), and inserts (ID,Ri,hi) into LH1. It is known that (ID,Ri,Di,hi) satisfies the equation DiP=Ri+hiPpub in thePartial-Private-Key-Extract algorithm.
H
1
Queries. Suppose that A1 makes at most q1 queries to the oracle H1. C chooses a random number j∈[1,q1]. When it makes a H1 query on IDi where 1≤i≤q1, if i=j (we let IDi=ID* at this point),  C randomly chooses u∈Zq* and returns u and then adds IDi,Ri to LH1. Otherwise, C picks a random number hi∈Zq*, returns hi to A1, and adds IDi,Ri,hi to LH1.
H
2
Queries. Suppose that A2 makes at most q2 queries to the oracle H2. If the list LH2 contains m,Ri,Xi,Ti,IDi,hi, C returns hi. Otherwise, C picks a random number hi∈Zq*, returns hi, and adds m,Ri,Xi,Ti,IDi,hi to LH2.
Request-Public-Key(
I
D
i
) Queries. Suppose that A2 makes this query to thePublic-Key-Request oracle. C looks up the list. C randomly chooses PKi=bP and then adds IDi,PKi,xi=⊥ to LHPK. Otherwise, C picks a random number ri∈Zq*, computes Xi=xiP, and adds IDi,PKi,xi to LPK.
Partial-Private-Key-Extract(
I
D
i
) Queries. When A1 makes this query, C does the following steps.
IfIDi=ID*, C terminates the session. Otherwise, C looks up LH1 for the tuple IDi,Ri,Di. If there exists such a tuple, C returns Di to A1. Otherwise, C makesReplace-Public-Key queries on itself and returns Di as the response.
Extract-Secret-Key(
I
D
i
) Queries. C picks a random xi∈Zq*, computes Xi=xiP, returns xi to A1, and adds IDi,Xi,xi to LSK.
Replace-Public-Key(
I
D
i
,
P
K
i
′
) Queries. If the list LPK contains IDi,PKi,xi, C sets PKi=PKi′, xi=⊥. Otherwise, C makesExtract-Secret-Key(IDi)query on IDi and then sets PKi=PKi′, xi=⊥, and returns PKi,⊥ to A1.
Sign(
m
,
I
D
i
) Queries. If the list LH1 contains IDi,Qi,ri and the list LPK contains IDi,PKi,xi, C does the following.
IfIDi=ID*, then C picks three random numbers a,xi,ri∈Zq*, computes T=aP, R=riP, X=xiP, h=H2(T∥X∥R∥IDi∥m), Di=ri+vH1(IDi,R)=ri+vhi, and s=a/(hxi+ri+vhi), returns h,s to A1, and adds m,PKi,IDi,ri,riP and m,PKi,IDi,hi to LH1 and LH2, respectively. The public key PKi may be replaced by A1. The following equation holds because the signature is valid:
(2)shXi+riP+h1y=ahxi+ri+vh1-1hxiP+riP+h1vP=aP=T.C computes (aP-shxiP-sriP)/sh1=vP.
Note thatC can solve the DL problem because he knows (a,s,h,xi,ri,P). Thus, we have ϵ′≥ε/(q12q2).
Then, we considerType II attack.
Suppose that there exists aType II adversary A2 which has a nonnegligible probability ε in attacking our CLS scheme; we construct a challenger C that uses A2 to solve the DLP. Challenger C receives a DL instance (vP,P) for randomly chosen v∈Zq* and P∈G and wants to compute v. C runs A2 as a subroutine and simulates its attack situation. C sets y=vP, where v is the master key, and returns system parameters and v to A2. C maintains initially empty lists LC, LH1, LH2, LD, LSK, LPK, LS, and LV in order to simulate the oracle queries of A2 as follows.
Create(
I
D
i
). C maintains list LC of tuple (ID,Ri,PKi,Di,xi,hi). C responds with (ID,Ri,PKi,Di,xi,hi) if IDi is on LC. Otherwise, if IDi=ID*, C chooses three random values ri,bi∈Zq* and sets Ri=riP, hi=H1(IDi,Ri), hi=bi, Di=ri+bismod⁡q, and Ppub=sP, xi=⊥. If IDi≠ID*, C chooses three random values xi,bi,ri∈Zq* and sets Ri=riP, hi=H1(IDi,Ri), hi=bi, Di=ri+bismod⁡q, Ppub=sP, and PKi=xiP; C responds with (ID,Ri,PKi,Di,xi,hi) and inserts (ID,Ri,hi) into LH1.
H
1
Queries. Suppose that A2 makes at most q1 queries to the oracle H1. C chooses a random j∈[1,q1]. When it makes a H1 query on IDi where 1≤i≤q1, if i=j (we let IDi=ID* at this point),  C randomly chooses ri∈Zq* and returns ri and then adds IDi,Ri,ri to LH1. Otherwise, C picks a random number hi∈Zq*, returns hi to A1, and adds IDi,Ri,hi to LH1.
H
2
Queries. Suppose that A2 makes at most q2 queries to the oracle H2. If the list LH2 contains m,Ri,Xi,Ti,IDi,hi, C returns hi. Otherwise, C picks a random number hi∈Zq*, returns hi, and adds m,Ri,Xi,Ti,IDi,hi to LH2.
Request-Public-Key(
I
D
i
) Queries. Suppose that A2 makes at most qPK queries to thePublic-Key-Request oracle. C chooses a random j∈[1,qPK]. If i=j (we let IDi=ID* at this point), C randomly chooses PKi=bP and then adds IDi,PKi,xi=⊥ to LHPK. Otherwise, C picks a random number ri∈Zq*, computes Xi=xiP, and adds IDi,PKi,xi to LPK.
Partial-Private-Key-Extract(
I
D
i
) Queries. When A2 makes this query, C looks up the tuple (IDi,Ri,Di); if there is the tuple, then C returns Di to A2. Otherwise, C makes theRequest-Public-Key(IDi) queries and returns Di to A2.
Extract-Secret-Key(
I
D
i
) Queries.
C picks a random xi∈Zq*, computes Xi=xiP, returns xi to A1, and adds IDi,Xi,xi to LSK. Otherwise, C aborts the simulation.
Sign(
m
,
I
D
i
) Queries. If the list LH1 contains IDi,Qi,ri and the list LPK contains IDi,PKi,xi, C does the following.
IfIDi=ID*, then C picks three random a,xi,ri∈Zq*, computes T=aP, X=xiP, h=H2(T∥X∥IDi∥m), Di=ri+vH1(IDi,R)=ri+vhi, and s=a/(hxi+Di)=a/(hxi+ri+vhi), returns h,s to A1, and adds m,PKi,IDi,ri,riP and m,PKi,IDi,hi to LH1 and LH2, respectively. The public key PKi may be replaced by A1. The following equation holds because the signature is valid:
(3)shXi+riP+h1y=ahxi+ri+vh1-1hxiP+riP+h1vP=aP=T.C computes (aP-shxiP-sriP)/sh1=vP.
Note thatC can solve the DL problems because he knows (a,s,h,xi,bP). Thus, we have ϵ′≥ε/(q12q2).


## 5. Performance Comparison

In order to achieve 1024-bit RSA level security, we used the Tate pairing defined over the supersingular elliptic curveE/Fp:y2=x3+x with embedding degree 2. q is a 160-bit Solinas prime q=2159+217+1 and p is a 512-bit prime such as p+1=12qr. The signature of Chen et al. [20] consists of a point of elliptic curve E/Fp:y2=x3+x; then, the signature size is 512/8 = 64 bytes. In order to achieve the same security level, we use the ECC group on Koblitz elliptic curve y2=x3+x2+b defined on F2163 with b=163 bit random prime. The signature size of our scheme is 163+163/8=41 bytes. The performance comparison among the proposed scheme and some related CLS schemes is given in Table 1. A pairing operation is denoted by P, scalar multiplication in the group G by M, a modular exponentiation in G2 by E, and pairing-based scalar multiplication by PM. Sign and Ver denote the computational costs required for signing and verification processes of CLS scheme. According to Table 1, it is known that our scheme is more efficient than the other CLS schemes.Table 1
Performance comparisons.
Schemes
Computational cost
Signature size (bytes)
Secure against Type I
Secure against Type II
Sign
Verify
Choi et al. [18]
3PM
2PM + 3P
64
Yes
No
He et al. [21]
1M
3M
41
Yes
No
Tsai et al. [23]
1M
4M
41
Yes
No
Gong and Li [24]
1M
4M
41
Yes
Yes
Yeh et al. [25]
1M
4M
41
Yes
Yes
Our scheme
1M
3M
41
Yes
Yes


## 6. Conclusion

In this paper, we proposed a new CLS scheme without pairings and also showed that the proposed scheme is secure in the random oracle model under the DL assumption. The proposed scheme is more efficient than the previous CLS schemes in terms of computation and communication costs and is more suitable for the applications of low-bandwidth environments.



---

*Source: 792063-2014-11-26.xml*