# A Certificateless Ring Signature Scheme with High Efficiency in the Random Oracle Model

Authors: Yingying Zhang; Jiwen Zeng; Wei Li; Huilin Zhu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Ring signature is a kind of digital signature which can protect the identity of the signer. Certificateless public key cryptography not only overcomes key escrow problem but also does not lose some advantages of identity-based cryptography. Certificateless ring signature integrates ring signature with certificateless public key cryptography. In this paper, we propose an efficient certificateless ring signature; it has only three bilinear pairing operations in the verify algorithm. The scheme is proved to be unforgeable in the random oracle model.


---

## Body

## 1. Introduction

In the traditional cryptography, the communicating parties distribute a private key by sending the key in advance over some secure channels. But there is a major barrier that the key distribution will cost and delay large teleprocessing networks. In 1976, Diffie and Hellman [1] first introduced the concept of public key cryptography (PKC) and proposed some techniques to solve this longstanding problem in traditional cryptography. But the traditional public key infrastructure confronted with the problem of certificate management. In order to solve this problem, Shamir [2] proposed an identity-based cryptography scheme based on public key cryptography (ID-PKC) in 1995. In his scheme, every user chooses his fundamental information as his public key and the user’s private key is generated directly by a private key generation (PKG) referred as master key. But there is a problem that the third party PKG has the private keys of all users and must be fully trusted; we call it the key escrow problem.In 2003, Al-Riyami and Paterson [3] introduced the concept of certificateless public key cryptography (CL-PKC). CL-PKC not only overcomes key escrow problem but also does not lose some advantages of ID-PKC. Key generation cryptography (KGC) in CL-PKC only issues the partial private key to a user. Then, the user combines the private key from KGC with a self-generated secret key to generate his actual private key, so that the KGC does not access user’s private key fully like in ID-PKC. Moreover, the public key of a user is generated by user himself by computing the KGC’s public parameters and the secret values of the user. Over last years, the certificateless signature (CLS) has been investigated successfully and attracted great attention [4–8].In 2001, Rivest et al. [9] first proposed the concept of ring signature (RS). Ring signature is designed for the situation that a member in a group wants to sign messages on behalf of the group while keeping his identity anonymous. Therefore, ring signature can protect the identity of the signer. In a ring signature, the signer forms a group (called a ring) only by collecting the public keys of all the group members including himself to keep the singer’s identity anonymous. In addition, ring signature is characterized with spontaneity; it means that the singer can generate a valid signature without help of any other members of the ring. Due to above two characteristics of ring signature, it is now widely used in electronic voting.A ring signature should meet the following three properties:(i)
Verifiability. The verifier can be convinced of the signer’s agreement on the signed message.(ii)
Unforgeability. No one, even any member of the ring, can forge other ring members to generate a valid ring signature.(iii)
Unconditional Anonymity. No one can determine the identity of the signer through the final ring signature.After ring signature given by Rivest et al. [9], many researchers have been proposing ring signature schemes and their variants such as threshold ring signatures [10–12] and constant-size ring signatures [13–16]. Ring signature schemes based on standard assumptions without random oracles were proposed in [17–20].As we know ring signature has been studied greatly in traditional PKC [18, 21, 22] and ID-PKC [17, 23–27]. But the applications of ring signature in traditional PKC and ID-PKC are restricted since there are some flaws in them. In fact, in a ring signature based on PKC, the verifier must check the validity of certificates of some group members, which will make the signature scheme inefficient since the computational cost will increase with the group size. Moreover, the ring signature based on ID-PKC has the key escrow problem. As described before, certificateless cryptography can make up the drawbacks in traditional PKC and ID-PKC. Therefore, several certificateless ring signatures (CLRS) integrating ring signature with certificateless cryptography have been proposed [28–30].Over the last few decades, certificateless signature and ring signature have been studied extensively; however there is little work on certificateless ring signatures [28, 31–33]. Chow and Yap [32] presented a CLRS scheme based on a security model they proposed, but their scheme requires n+1 pairing operations and 2 exponentiation operations. Later, a CLRS scheme only requiring 5 pairing operations and 4n+1 exponentiation operations was proposed by Zhang et al. (see [33]). Two years later Chang et al. [31] constructed a concrete CLRS scheme, which reduces the pairing operations to 4 while it needs 4n+2 exponentiation operations.We know that it is always interesting to design a cryptographic scheme with less pairing operations to speed up the computation of pairing function in recent years. To the best of our knowledge, the most efficient certificateless ring signature scheme based on bilinear pairings requires at least four bilinear maps. In this paper, we will propose a certificateless ring signature. Our scheme only needs 3 bilinear maps in the verification phase. By the analysis in Section6, we know that our scheme is more efficient compared with other certificateless ring signature schemes [31–33].The rest of the paper is organized as follows. Section2 presents the basic concepts of bilinear pairings and some related mathematical problems. Section 3 presents a formal definition and security model of a certificateless ring signature scheme. Section 4 presents our certificateless ring signature scheme. We prove its security in Section 5. Schemes comparison will be given in Section 6. Finally, we give some conclusions in Section 7.


## 2. Preliminaries

### 2.1. Bilinear Pairing

LetG1 be a cyclic additive group of prime order and G2 be a cyclic multiplicative group of the same order.We calle a bilinear pairing if e:G1×G1→G2 is a map with the following three properties:(1)
Bilinearity:e(aP,bQ)=eP,Qab, and P,Q∈G1.(2)
Nondegeneracy: there existP,Q∈G1 such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for any two random elements P,Q∈G1.Security of the proposed scheme relies on the following questions and assumptions.Definition 1 (computational Diffie-Hellman (CDH) problem).
LetG=(E,+), where E is an elliptic curve over a finite field Fq and P∈E is a point having prime order d=E/2. Let G1=P≤G, the computational Diffie-Hellman (CDH) Problem is that given two random elements aP,bP∈G1 for unknown a,b∈Zd∗, to compute abP.Definition 2 (computational Diffie-Hellman (CDH) assumption).
LetG be a CDH parameter generator. We say that an algorithm A has advantage ε(k) in solving the CDH problem for G if, for a sufficiently large k, (1)AdvG,Ak=Pr⁡Aq,G1,aP,bP=abP∣q,G1⟵G1k,P⟵G1,a,b⟵Zd∗≥εk.Given an upper limitation time T, we say that G satisfies the CDH assumption if for any randomized polynomial-time algorithm A, we have that AdvG,A(k) is a negligible function. When G satisfies the CDH assumption, we say that the CDH problem is hard in G1 generated by G.Definition 3 (computational co-Diffie-Hellman (co-CDH) problem).
LetG=(E,+), where E is an elliptic curve over a finite field Fq and P∈E is a point having prime order d=E/2. Let G1=P≤G; the Computational co-Diffie-Hellman (co-CDH) Problem is that given two random elements aP,X∈G1 for unknown a∈Zd∗, to compute aX.Definition 4 (computational co-Diffie-Hellman (co-CDH) assumption).
LetG be a co-CDH parameter generator. We say that an algorithm A has advantage ε(k) in solving the co-CDH problem for G if, for a sufficiently large k, (2)AdvG,Ak=Pr⁡Aq,G1,aP,X=aX∣q,G1⟵G1k,P,X⟵G1,a⟵Zd∗≥εk.Given an upper limitation time T, we say that G satisfies the (co-CDH) assumption if for any randomized polynomial-time algorithm A, we have that AdvG,A(k) is a negligible function. When G satisfies the (co-CDH) assumption, we say that the (co-CDH) problem is hard in G1 generated by G.


## 2.1. Bilinear Pairing

LetG1 be a cyclic additive group of prime order and G2 be a cyclic multiplicative group of the same order.We calle a bilinear pairing if e:G1×G1→G2 is a map with the following three properties:(1)
Bilinearity:e(aP,bQ)=eP,Qab, and P,Q∈G1.(2)
Nondegeneracy: there existP,Q∈G1 such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for any two random elements P,Q∈G1.Security of the proposed scheme relies on the following questions and assumptions.Definition 1 (computational Diffie-Hellman (CDH) problem).
LetG=(E,+), where E is an elliptic curve over a finite field Fq and P∈E is a point having prime order d=E/2. Let G1=P≤G, the computational Diffie-Hellman (CDH) Problem is that given two random elements aP,bP∈G1 for unknown a,b∈Zd∗, to compute abP.Definition 2 (computational Diffie-Hellman (CDH) assumption).
LetG be a CDH parameter generator. We say that an algorithm A has advantage ε(k) in solving the CDH problem for G if, for a sufficiently large k, (1)AdvG,Ak=Pr⁡Aq,G1,aP,bP=abP∣q,G1⟵G1k,P⟵G1,a,b⟵Zd∗≥εk.Given an upper limitation time T, we say that G satisfies the CDH assumption if for any randomized polynomial-time algorithm A, we have that AdvG,A(k) is a negligible function. When G satisfies the CDH assumption, we say that the CDH problem is hard in G1 generated by G.Definition 3 (computational co-Diffie-Hellman (co-CDH) problem).
LetG=(E,+), where E is an elliptic curve over a finite field Fq and P∈E is a point having prime order d=E/2. Let G1=P≤G; the Computational co-Diffie-Hellman (co-CDH) Problem is that given two random elements aP,X∈G1 for unknown a∈Zd∗, to compute aX.Definition 4 (computational co-Diffie-Hellman (co-CDH) assumption).
LetG be a co-CDH parameter generator. We say that an algorithm A has advantage ε(k) in solving the co-CDH problem for G if, for a sufficiently large k, (2)AdvG,Ak=Pr⁡Aq,G1,aP,X=aX∣q,G1⟵G1k,P,X⟵G1,a⟵Zd∗≥εk.Given an upper limitation time T, we say that G satisfies the (co-CDH) assumption if for any randomized polynomial-time algorithm A, we have that AdvG,A(k) is a negligible function. When G satisfies the (co-CDH) assumption, we say that the (co-CDH) problem is hard in G1 generated by G.


## 3. Formal Definition and Security Model

### 3.1. Formal Definition of a Certificateless Ring Signature Scheme

A certificateless ring signature scheme (CLRS) can be specified by seven algorithms: Setup, Partial Private Key Extract, Set Secret Value, Set Private Key, Set Public Key, CLRS Generation, and CLRS Verification. Every algorithm is depicted as follows.(i)
Setup. Given a security parameter, it outputs a list of system parameters.(ii)
Partial Private Key Extract. On input a master key, a user’s identity IDi, and system parameters, it generates the user’s partial private key SIDi.(iii)
Set Secret Value. Given a user’s identity IDi, it outputs the user’s secret value xi∈Zd∗ and computes Yi=xiP.(iv)
Set Private Key. The user takes the pair (SIDi,xi) as its private key.(v)
Set Public Key. The user with identity IDi constructs his public key pair (Yi, QIDi) responding to xi and SIDi, respectively.(vi)
CLRS Generation. Given a message m, signer chooses n-1 other users to form a ring U; then it outputs a ring signature σ on behalf of the ring U.(vii)
CLRS Verification. Given a message m, a ring signature σ, and the public keys Y1,…,Yn of the n signers, it outputs “accept” if σ is a valid ring signature and “reject” otherwise.


### 3.2. Security Model of Certificateless Ring Signature Scheme

In our certificateless ring signature scheme, we consider the following two attackers.Type I Adversary. Adversary AI does not have access to the master key, but AI can replace the public keys of any entity with a value of his choice, because there is no certificate involved in CLRS.Type II Adversary. This type of adversary AII is a malicious KGC. Adversary AII is allowed to have access to the master key but does not replace any user’s public key. A type II adversary should also be allowed to change a user’s partial private key.Game 1 for Type I Adversary. Type I adversary advantage AdvCLRS,AI is defined as its probability of success in the following game between a challenger C and a type I adversary AI.(i)
Setup. Given a security parameter, challenger C runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to type I adversary AI.(ii)
Hash Queries. AI submits any value he chooses, and challenger C returns the corresponding hash value to him.(iii)
User Public Key Queries. AI requests any public key of a user IDi whom he chooses, and challenger C returns the corresponding public key Yi to him.(iv)
Partial Private Key Queries. AI requests any partial private key of a user IDi whom he chooses, and challenger C returns the corresponding partial private key SIDi to him.(v)
User Public Key Replacements. AI submits a new public key value Yi′ with respect to a user IDi. Challenger C replaces the current public key with the value Yi′.(vi)
Secret Value Queries. AI requests any secret value of a user IDi whose public key was not replaced, and challenger C returns the corresponding secret value xi to AI. If a user’s public key was replaced, AI cannot query the corresponding secret value.(vii)
Ring Signature Queries. AI submits any message he chooses, and challenger C returns a ring signature σ to him.(viii)
Forge. Eventually, AI outputs a certificateless ring signature σ∗ on a message m∗ such that
(1)
σ∗ is a valid certificateless ring signature;(2)
AI can not query the partial private key of anyone in U;(3)
m∗ has never been submitted to the ring signature queries.Definition 5.
A forgerAI(t,qH1,qH2,qD,qU,qRS,ε) breaks a certificateless ring signature scheme (CLRS) meaning that if AI runs in time at most t, AI makes at most qH1H1 Hash queries, at most qH2H2 Hash queries, at most qD partial private key queries, at most qU user public key queries, and qRS ring signature queries; then AdvCLRS,AI is at least ε. A certificateless ring signature scheme is (t,qH1,qH2,qD,qU,qRS,ε)-existentially unforgeable under an adaptively chosen-message attack if no forger (t,qH1,qH2,qD,qU,qRS,ε) breaks it.Game 2 for Type II Adversary. Type II adversary advantage AdvCLRS,AII is defined as its probability of success in the following game between a challenger C and a type II adversary AII.(i)
Setup. Given a security parameter, challenger C runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters and the master key θ to type II adversary AII.(ii)
Hash Queries. AII submits any value he chooses, and challenger C returns the corresponding hash value to him.(iii)
User Public Key Queries. AII requests any public key of a user IDi whom he chooses, and challenger C returns the corresponding public key Yi to him.(iv)
Partial Private Key Queries. Because AII has the system master key θ, so AII can compute the partial private key of any user by himself.(v)
User Public Key Replacements. AII submits a new public key value Yi′ with respect to a user IDi. Challenger C replaces the current public key with the value Yi′.(vi)
Secret Value Queries. AII requests any secret value of a user IDi whose public key was not replaced, and challenger C returns the corresponding secret value xi to AII. If a user’s public key was replaced, AII cannot query the corresponding secret value.(vii)
Ring Signature Queries. AII submits any message he chooses, and challenger C returns a ring signature σ to AII.(viii)
Forge. Eventually, AII outputs a certificateless ring signature σ∗ on a message m∗ such that
(1)
σ∗ is a valid certificateless ring signature;(2)
AII can not query the secret value of anyone in U;(3)
AII can not replace the user public key of anyone in U;(4)
m∗ has never been submitted to the ring signature queries.Definition 6.
A forgerAII(t,qH1,qH2,qE,qR,qU,qRS,ε) breaks a certificateless ring signature scheme (CLRS) means that if AII runs in time at most t, AII makes at most qH1H1 Hash queries, at most qH2H2 Hash queries, at most qE secret value queries, at most qR user public key replacement queries, at most qU user public key queries, and qRS ring signature queries; then AdvCLRS,AII is at least ε. A certificateless ring signature scheme is (t,qH1,qH2,qE,qR,qU,qRS,ε)-existentially unforgeable under an adaptively chosen-message attack if no forger (t,qH1,qH2,qE,qR,qU,qRS,ε) breaks it.Game 3 Anonymity of a Certificateless Ring Signature Scheme. Let U=(u1,u2,…,un) be n signers and W be the n signers’ identities. A be an adversary and C be a challenger whom are all involved in the game 3.(i)
The challengerC runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to adversary A.(ii)
The adversaryA adaptively make a polynomially bounded number of queries.(iii)
In the challenge phase, the adversary outputs a messagem, a group of n users’ identities W, and two different members ID0,ID1∈W to the challenger C. The challenger C randomly chooses a bit μ∈{0,1} and sends A to a ring signature σ=RS(m,W,xμ).(iv)
The adversaryA can make a polynomially bounded number of queries.(v)
Finally, adversaryA outputs a bit μ′∈{0,1}.The adversary A wins the above game if and only if μ=μ′.Definition 7.
Define the probability of success in the game3 of adversary A as succ(A)=Pr[μ=μ′]=1/2+ε. A certificateless ring signature scheme is said to have unconditional anonymity if no adversary has no nonnegligible advantage in winning the above game. That is to say, A certificateless ring signature scheme is said to have unconditional anonymity if ε=0.


## 3.1. Formal Definition of a Certificateless Ring Signature Scheme

A certificateless ring signature scheme (CLRS) can be specified by seven algorithms: Setup, Partial Private Key Extract, Set Secret Value, Set Private Key, Set Public Key, CLRS Generation, and CLRS Verification. Every algorithm is depicted as follows.(i)
Setup. Given a security parameter, it outputs a list of system parameters.(ii)
Partial Private Key Extract. On input a master key, a user’s identity IDi, and system parameters, it generates the user’s partial private key SIDi.(iii)
Set Secret Value. Given a user’s identity IDi, it outputs the user’s secret value xi∈Zd∗ and computes Yi=xiP.(iv)
Set Private Key. The user takes the pair (SIDi,xi) as its private key.(v)
Set Public Key. The user with identity IDi constructs his public key pair (Yi, QIDi) responding to xi and SIDi, respectively.(vi)
CLRS Generation. Given a message m, signer chooses n-1 other users to form a ring U; then it outputs a ring signature σ on behalf of the ring U.(vii)
CLRS Verification. Given a message m, a ring signature σ, and the public keys Y1,…,Yn of the n signers, it outputs “accept” if σ is a valid ring signature and “reject” otherwise.


## 3.2. Security Model of Certificateless Ring Signature Scheme

In our certificateless ring signature scheme, we consider the following two attackers.Type I Adversary. Adversary AI does not have access to the master key, but AI can replace the public keys of any entity with a value of his choice, because there is no certificate involved in CLRS.Type II Adversary. This type of adversary AII is a malicious KGC. Adversary AII is allowed to have access to the master key but does not replace any user’s public key. A type II adversary should also be allowed to change a user’s partial private key.Game 1 for Type I Adversary. Type I adversary advantage AdvCLRS,AI is defined as its probability of success in the following game between a challenger C and a type I adversary AI.(i)
Setup. Given a security parameter, challenger C runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to type I adversary AI.(ii)
Hash Queries. AI submits any value he chooses, and challenger C returns the corresponding hash value to him.(iii)
User Public Key Queries. AI requests any public key of a user IDi whom he chooses, and challenger C returns the corresponding public key Yi to him.(iv)
Partial Private Key Queries. AI requests any partial private key of a user IDi whom he chooses, and challenger C returns the corresponding partial private key SIDi to him.(v)
User Public Key Replacements. AI submits a new public key value Yi′ with respect to a user IDi. Challenger C replaces the current public key with the value Yi′.(vi)
Secret Value Queries. AI requests any secret value of a user IDi whose public key was not replaced, and challenger C returns the corresponding secret value xi to AI. If a user’s public key was replaced, AI cannot query the corresponding secret value.(vii)
Ring Signature Queries. AI submits any message he chooses, and challenger C returns a ring signature σ to him.(viii)
Forge. Eventually, AI outputs a certificateless ring signature σ∗ on a message m∗ such that
(1)
σ∗ is a valid certificateless ring signature;(2)
AI can not query the partial private key of anyone in U;(3)
m∗ has never been submitted to the ring signature queries.Definition 5.
A forgerAI(t,qH1,qH2,qD,qU,qRS,ε) breaks a certificateless ring signature scheme (CLRS) meaning that if AI runs in time at most t, AI makes at most qH1H1 Hash queries, at most qH2H2 Hash queries, at most qD partial private key queries, at most qU user public key queries, and qRS ring signature queries; then AdvCLRS,AI is at least ε. A certificateless ring signature scheme is (t,qH1,qH2,qD,qU,qRS,ε)-existentially unforgeable under an adaptively chosen-message attack if no forger (t,qH1,qH2,qD,qU,qRS,ε) breaks it.Game 2 for Type II Adversary. Type II adversary advantage AdvCLRS,AII is defined as its probability of success in the following game between a challenger C and a type II adversary AII.(i)
Setup. Given a security parameter, challenger C runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters and the master key θ to type II adversary AII.(ii)
Hash Queries. AII submits any value he chooses, and challenger C returns the corresponding hash value to him.(iii)
User Public Key Queries. AII requests any public key of a user IDi whom he chooses, and challenger C returns the corresponding public key Yi to him.(iv)
Partial Private Key Queries. Because AII has the system master key θ, so AII can compute the partial private key of any user by himself.(v)
User Public Key Replacements. AII submits a new public key value Yi′ with respect to a user IDi. Challenger C replaces the current public key with the value Yi′.(vi)
Secret Value Queries. AII requests any secret value of a user IDi whose public key was not replaced, and challenger C returns the corresponding secret value xi to AII. If a user’s public key was replaced, AII cannot query the corresponding secret value.(vii)
Ring Signature Queries. AII submits any message he chooses, and challenger C returns a ring signature σ to AII.(viii)
Forge. Eventually, AII outputs a certificateless ring signature σ∗ on a message m∗ such that
(1)
σ∗ is a valid certificateless ring signature;(2)
AII can not query the secret value of anyone in U;(3)
AII can not replace the user public key of anyone in U;(4)
m∗ has never been submitted to the ring signature queries.Definition 6.
A forgerAII(t,qH1,qH2,qE,qR,qU,qRS,ε) breaks a certificateless ring signature scheme (CLRS) means that if AII runs in time at most t, AII makes at most qH1H1 Hash queries, at most qH2H2 Hash queries, at most qE secret value queries, at most qR user public key replacement queries, at most qU user public key queries, and qRS ring signature queries; then AdvCLRS,AII is at least ε. A certificateless ring signature scheme is (t,qH1,qH2,qE,qR,qU,qRS,ε)-existentially unforgeable under an adaptively chosen-message attack if no forger (t,qH1,qH2,qE,qR,qU,qRS,ε) breaks it.Game 3 Anonymity of a Certificateless Ring Signature Scheme. Let U=(u1,u2,…,un) be n signers and W be the n signers’ identities. A be an adversary and C be a challenger whom are all involved in the game 3.(i)
The challengerC runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to adversary A.(ii)
The adversaryA adaptively make a polynomially bounded number of queries.(iii)
In the challenge phase, the adversary outputs a messagem, a group of n users’ identities W, and two different members ID0,ID1∈W to the challenger C. The challenger C randomly chooses a bit μ∈{0,1} and sends A to a ring signature σ=RS(m,W,xμ).(iv)
The adversaryA can make a polynomially bounded number of queries.(v)
Finally, adversaryA outputs a bit μ′∈{0,1}.The adversary A wins the above game if and only if μ=μ′.Definition 7.
Define the probability of success in the game3 of adversary A as succ(A)=Pr[μ=μ′]=1/2+ε. A certificateless ring signature scheme is said to have unconditional anonymity if no adversary has no nonnegligible advantage in winning the above game. That is to say, A certificateless ring signature scheme is said to have unconditional anonymity if ε=0.


## 4. Our Scheme

In this section, we propose a certificateless ring signature scheme. Participants in the program includen signers U=(u1,u2,…,un) and a verifier V. Our scheme is described as follows:(i)
Setup. Given a security parameter z, KGC outputs a large prime d. Let G1 be a cyclic additive group of prime order d. Let G2 be a cyclic multiplicative group of the same order. Let P,Q be two generators of G1. KGC chooses the master private key θ∈Zd∗ randomly and computes the master public key PPub=θP. Let e:G1×G1→G2 be a bilinear map. Let H1:{0,1}∗→G1, H2:{0,1}∗×G1×G1→Zd∗, and H3:{0,1}∗×G1×G1→Zd∗ be three secure cryptographic hash functions. KGC publishes system parameters (G1,G2,d,P,Q,PPub,e,H1,H2,H3) and secretly keeps the master key θ.(ii)
Partial Private Key Extract. Given a user’s identity IDi, KGC computes QIDi=H1(IDi) and SIDi=θQIDi. Then KGC sends the user’s partial private key SIDi to him. The user can check its correctness by checking whether e(SIDi,P)=e(QIDi,PPub).(iii)
Set Secret Value. User IDi selects xi∈Zd∗ randomly as her secret value. Then User computes the corresponding value Yi=xiP.(iv)
Set Private Key. User IDi takes the pair PRK=(xi,SIDi) as its private key.(v)
Set Public Key. User IDi takes the pair PUK=(Yi,QIDi) as its public key.(vi)
CLRS Generation. Given a message m, W={ID1,ID2,…,IDn} is a set of n users’ identities. An actual signer us∈U can propose a certificateless ring signature σ. The signer us operates as follows:
(1)
ChooseRi,Ki∈G1(i=1,2,…,n∖s) randomly and compute(3)ri=H2m∥W,Ri,Yi,i=1,2,…,s-1,s+1,…,n,ki=H3m∥ri∥W,Ki,Yi,i=1,2,…,s-1,s+1,…,n.(2)
Selectr,k∈Zq∗ and compute(4)Rs=rP-∑i≠sriQIDi+Ri,Ks=kP-∑i≠skiYi+Ki;then compute:(5)rs=H2m∥W,Rs,Ys,ks=H3m∥rs∥W,Ks,Ys.(3)
ComputeV=rPPub+rsSIDs+ksxsQ+kQ.(4)
Outputσ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V).(vii)
CLRS Verification. Given public keys of the n signer, a verifier V can verify a certificateless ring signature σ by checking if the following equation holds: (6)eP,V=e∑i=1nriQIDi+Ri,PPube∑i=1nkiYi+Ki,Q.If it holds, the verifier “accepts” the signature and “rejects” otherwise.


## 5. Security Analysis

In this section, we mainly focus on the unforgeability of the proposed certificateless ring signature scheme. Now, we give the following three theorems.


### 5.1. Unforgeability against Type I Adversary

Theorem 8.
The scheme is unforgeable against a type I adversaryAI in the random oracle model if the CDH problem is hard.Proof.
Suppose challengerC receives a random instance (P,aP,bP) of the CDH problem and has to compute the value of abP. Challenger C sets the system public key PPub=aP. C will run AI as a subroutine and act as AI’s challenger in game 1. Without loss of generality, we assume that all the queries are distinct. Now, we will show how challenger C answers a type I adversary AI’s queries in the following.Initialization. At the beginning of the game, challenger C runs the setup algorithm with the parameter z and then gives adversary AI the system parameters: (G1,G2,d,P,Q,PPub,e,H1,H2,H3).(i)
H1Queries. Challenger C maintains the list L1 of tuple (IDi,viP). The list is initially empty. When adversary AI makes a query H1(IDi), challenger C responds as follows. Challenger C chooses a random integer f in [1,qH1] firstly. At the ith H1 query, if i≠f, challenger C randomly selects a value vi∈Zd∗, and sets H1(IDi)=viP; otherwise, challenger C sets H1(ID∗)=bP.(ii)
H2Queries. Challenger C maintains the list L2 of tuple (βi,h2). The list is initially empty. When AI makes a query H2(βi), challenger C selects a value h2 randomly, and sets H2(βi)=h2. Then challenger C adds (βi,h2) to the H2 list and returns h2 to AI.(iii)
H3Queries. Challenger C maintains the list L3 of tuple (γi,h3). The list is initially empty. When AI makes a query H3(γi), challenger C selects a value h3 randomly and sets H3(γi)=h3. Then challenger C adds (γi,h3) to the H3 list and returns h3 to AI.(iv)
User Public Key Queries. Challenger C maintains the list LU of tuple (IDi,Yi,xi). The list is initially empty. When adversary AI makes a user public key query for IDi, challenger C selects a value xi∈Zd∗, and sets Yi=xiP. Then challenger C adds (IDi,Yi,xi) to the LU list and returns Yi to AI.(v)
Partial Private Key Queries. Challenger C maintains the list LS of tuple (IDi,SIDi). The list is initially empty. When adversary AI makes a user partial private key query for IDi, if IDi=ID∗, C fails and stops. Otherwise challenger C computes SIDi=viPPub. Then challenger C adds (IDi,SIDi) to the LS list and returns SIDi to AI.(vi)
User Public Key Replacements. Challenger C maintains the list LR of tuple (IDi,Yi,Yi′). The list is initially empty. When AI makes a user public key replacement request for ui with other public value Yi′, C replaces Yi with Yi′ and adds (IDi,Yi,Yi′) to the LR list.(vii)
Secret Value Queries. Challenger C maintains the list LE of tuple (IDi,xi). The list is initially empty. When adversary AI makes a user secret value query for IDi, C checks the lists LU firstly. If the tuple (IDi,xi) is found in the list LU, C returns xi to AI. Otherwise challenger C randomly chooses xi∈Zd∗, returns xi to AI, and adds (IDi,xi) to the LE list.(viii)
Ring Signature Queries. AI submits a message m and a set of n users’ identities W={ID1,ID2,…,IDn}. C outputs a ring signature as follows. If there exists a user IDs∈W such that IDs≠ID∗ and IDs∉LR, then challenger C returns the ring signature σ by calling the signing algorithm, where IDs is the actual signer. Otherwise, challenger C does as follows:
(1)
SelectsRi,Ki∈G1 randomly for all i∈(1,2,…,n) and i≠s.(2)
For alli∈(1,2,…,n), selects ri,ki∈Zd∗ randomly.(3)
Chooses two valuesr,k∈Zd∗ randomly and computes (7)Rs=rP-∑i=1nriQIDi-∑i≠sRi,Ks=kP-∑i=1nkiYi-∑i≠sKi.(4)
ComputesV=rPPub+kQ.(5)
Outputsσ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V).Forge. Adversary AI outputs a ring signature σ∗ on a message m∗ that fulfills the following conditions:(1)
σ∗ is a valid ring signature.(2)
AI cannot query the partial private key of anyone in U.(3)
The forged signatureσ∗ is not from signature query.Output. It follows from the forking lemma that if ε≥7CqH2n/2k, adversary AI can give a valid forged signature within time TA in the above interaction; then we can construct another algorithm AI′ that outputs two signed messages within time 2TA with probability at least ε2/66CqH2n. For the resemble construction, C can get two valid ring signature σ and σ′ satisfying(8)σ=R1,R2,…,Rs-1,Rs,Rs+1,…,Rn,K1,…,Kn,m,V,σ′=R1,R2,…,Rs-1,Rs′,Rs+1,…,Rn,K1,…,Kn,m,V′.So we have(9)V=rPPub+rsSIDs+ksxsQ+kQ,V′=rPPub+rs′SIDs+ksxsQ+kQ.Challenger C outputs(10)abP=SIDs=rs-rs′-1V-V′.Probability. Let qH1, qH2, qH3, qD, qU, and qRS be times of H1 queries, H2 queries, H3 queries, partial private key queries, user public key queries, and ring signature queries, respectively. The probability that ID∗’s partial private key was not queried by AI during the queries is qH1-qD/qH1. The probability that ID∗ belongs to the groups W is n/qH1-qD. The probability that ID∗ is the actual signer is 1/n. So the combined probability is qH1-qD/qH1·n/qH1-qD·1/n=1/qH1.Therefore, according to the forking lemma, if the attackerAI can succeed in making a valid ring signature with a probability ε, the advantage of challenger C solving an instance of CDH problem in game 1 is at least ε2/66CqH2n·1/qH1.


### 5.2. Unforgeability against Type II Adversary

Theorem 9.
The scheme is unforgeable against a type II adversaryAII in the random oracle model if the co-CDH problem is hard.Proof.
Suppose challengerC receives a random instance (aP,X) of the co-CDH and has to compute the value of aX. Challenger C sets Q=X. Challenger C will run adversary AII as a subroutine and act as AII’s challenger in the game 2. Without loss of generality, we assume that all the queries are distinct. Now, we will show how challenger C answers type II adversary AII’s queries in the following.
Initialization. At the beginning of the game, challenger C runs the setup algorithm with the parameter z and gives adversary AII the system parameters: (G1,G2,d,P,Q,PPub,e,H1,H2,H3) and the system master secret key θ.(i)
H1 Queries. Challenger C maintains the list L1 of tuple (IDi,viP). The list is initially empty. When adversary AII makes a query H1(IDi), challenger C selects a value vi∈Zd∗ randomly and computes H1(IDi)=viP. Then challenger C adds (IDi,viP) to the H1 list and returns viP to AII.(ii)
H2 Queries. Same as that in the proof of Theorem 8.(iii)
H3 Queries. Same as that in the proof of Theorem 8.(iv)
User Public Key Queries. Challenger C maintains the list LU of tuple (IDi,Yi,xi). The list is initially empty. When adversary AII makes a user public key query for IDi, challenger C responds as follows. Challenger C chooses a random integer j in [1,qU] firstly. At the ith qU query, if i≠j, challenger C selects a value xi∈Zd∗ randomly and sets Yi=xiP. Otherwise, challenger C sets IDj=ID∗ and Y∗=aP.(v)
Partial Private Key Queries. Adversary AII can compute the partial private keys of any identities by himself with the master secret key.(vi)
User Public Key Replacements. Same as that in the proof of Theorem 8.(vii)
Secret Value Queries. Challenger C maintains the list LE of tuple (IDi,xi). The list is initially empty. When adversary AII makes a user partial private key query for IDi, if IDi=ID∗, C fails and stops. Otherwise challenger C finds the tuple (IDi,xi) in the list LU. Then challenger C adds (IDi,xi) to the LE list and returns xi to AII.(viii)
Ring Signature Queries. Same as that in the proof of Theorem 8.
Forge. Eventually, AII outputs a ring signature σ∗ fulfilling the following conditions:(1)
σ∗ is a valid ring signature.(2)
AII cannot query the secret value of anyone in U.(3)
AII cannot replace any users’ public key in U.(4)
The forged signatureσ∗ is not from signature query.
Output. It follows from the forking lemma that if ε≥7CqH3n/2k, adversary AII can give a valid forged signature within time TA in the above interaction; then we can construct another algorithm AII′ that outputs two signed messages within time 2TA with probability at least ε2/66CqH3n. For the resemble construction, C can get two valid ring signature σ and σ′ satisfying(11)σ=R1,…,Rn,K1,K2,…,Ks-1,Ks,Ks+1,…,Kn,m,V,σ′=R1,…,Rn,K1,K2,…,Ks-1,Ks′,Ks+1,…,Kn,m,V′.
So we have(12)V=rPPub+rsSIDs+ksxsQ+kQ,V′=rPPub+rsSIDs+ks′xsQ+kQ.Challenger C outputs(13)aX=xsQ=ks-ks′-1V-V′.
Probability. Let qH1, qH2, qH3, qE, qR, qU, and qRS be the times of H1 queries, H2 queries, H3 queries, secret value queries, user public key replacement requests, user public key queries, and ring signature queries, respectively.
For simplification, we may assume thatLE∩LR=ϕ. The probability that ID∗’s secret value was not queried and ID∗’s public key was not replaced by AII during the queries is qU-qE-qR/qU. The probability that ID∗ belongs to the groups W is n/qU-qE-qR. The probability that ID∗ is the actual signer is 1/n. So the combined probability is: qU-qE-qR/qU·n/qU-qE-qR·1/n=1/qU.Therefore, according to the forking lemma, if the attackerAII can succeed in making a valid ring signature with a probability ε, the advantage of challenger C solving an instance of co-CDH problem in the game 2 is at least ε2/66CqH3n·1/qU.


### 5.3. Unconditional Anonymity

Theorem 10.
Our certificateless ring signature scheme has the property of unconditional anonymity. For any algorithmA, any set of signers U=(u1,u2,…,un) and a random us∈U, the probability Pr[μ=μ′]=1/2, where σ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V) is a ring signature on U generated by us.Proof.
(i) The challengerC runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to adversary A.
(ii) The adversaryA adaptively makes a polynomially bounded number of queries.
(iii) The adversaryA outputs a message m, two different members ID1,ID2∈W to the challenger C. The challenger C randomly chooses a bit μ∈{0,1} and sends A to a ring signature σ=RS(m,W,xμ).
(iv) The adversaryA can make a polynomially bounded number of queries.
(v) Finally, adversaryA outputs a bit μ′∈{0,1}.In our scheme, sinceRi,Ki are chosen randomly from G1,  ri,ki are also random elements from Zd∗. Moreover, rs,ks are chosen randomly from Zd∗, so V is also a random element from G1. For anyone of a set of signers U, message m, the distribution of σ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V) is independently and uniformly distributed no matter who the actual signer is. The fact illustrates that anyone has no advantage to know who signs the certificateless ring signature. Hence, Pr[μ=μ′]=1/2; the anonymity holds.


## 5.1. Unforgeability against Type I Adversary

Theorem 8.
The scheme is unforgeable against a type I adversaryAI in the random oracle model if the CDH problem is hard.Proof.
Suppose challengerC receives a random instance (P,aP,bP) of the CDH problem and has to compute the value of abP. Challenger C sets the system public key PPub=aP. C will run AI as a subroutine and act as AI’s challenger in game 1. Without loss of generality, we assume that all the queries are distinct. Now, we will show how challenger C answers a type I adversary AI’s queries in the following.Initialization. At the beginning of the game, challenger C runs the setup algorithm with the parameter z and then gives adversary AI the system parameters: (G1,G2,d,P,Q,PPub,e,H1,H2,H3).(i)
H1Queries. Challenger C maintains the list L1 of tuple (IDi,viP). The list is initially empty. When adversary AI makes a query H1(IDi), challenger C responds as follows. Challenger C chooses a random integer f in [1,qH1] firstly. At the ith H1 query, if i≠f, challenger C randomly selects a value vi∈Zd∗, and sets H1(IDi)=viP; otherwise, challenger C sets H1(ID∗)=bP.(ii)
H2Queries. Challenger C maintains the list L2 of tuple (βi,h2). The list is initially empty. When AI makes a query H2(βi), challenger C selects a value h2 randomly, and sets H2(βi)=h2. Then challenger C adds (βi,h2) to the H2 list and returns h2 to AI.(iii)
H3Queries. Challenger C maintains the list L3 of tuple (γi,h3). The list is initially empty. When AI makes a query H3(γi), challenger C selects a value h3 randomly and sets H3(γi)=h3. Then challenger C adds (γi,h3) to the H3 list and returns h3 to AI.(iv)
User Public Key Queries. Challenger C maintains the list LU of tuple (IDi,Yi,xi). The list is initially empty. When adversary AI makes a user public key query for IDi, challenger C selects a value xi∈Zd∗, and sets Yi=xiP. Then challenger C adds (IDi,Yi,xi) to the LU list and returns Yi to AI.(v)
Partial Private Key Queries. Challenger C maintains the list LS of tuple (IDi,SIDi). The list is initially empty. When adversary AI makes a user partial private key query for IDi, if IDi=ID∗, C fails and stops. Otherwise challenger C computes SIDi=viPPub. Then challenger C adds (IDi,SIDi) to the LS list and returns SIDi to AI.(vi)
User Public Key Replacements. Challenger C maintains the list LR of tuple (IDi,Yi,Yi′). The list is initially empty. When AI makes a user public key replacement request for ui with other public value Yi′, C replaces Yi with Yi′ and adds (IDi,Yi,Yi′) to the LR list.(vii)
Secret Value Queries. Challenger C maintains the list LE of tuple (IDi,xi). The list is initially empty. When adversary AI makes a user secret value query for IDi, C checks the lists LU firstly. If the tuple (IDi,xi) is found in the list LU, C returns xi to AI. Otherwise challenger C randomly chooses xi∈Zd∗, returns xi to AI, and adds (IDi,xi) to the LE list.(viii)
Ring Signature Queries. AI submits a message m and a set of n users’ identities W={ID1,ID2,…,IDn}. C outputs a ring signature as follows. If there exists a user IDs∈W such that IDs≠ID∗ and IDs∉LR, then challenger C returns the ring signature σ by calling the signing algorithm, where IDs is the actual signer. Otherwise, challenger C does as follows:
(1)
SelectsRi,Ki∈G1 randomly for all i∈(1,2,…,n) and i≠s.(2)
For alli∈(1,2,…,n), selects ri,ki∈Zd∗ randomly.(3)
Chooses two valuesr,k∈Zd∗ randomly and computes (7)Rs=rP-∑i=1nriQIDi-∑i≠sRi,Ks=kP-∑i=1nkiYi-∑i≠sKi.(4)
ComputesV=rPPub+kQ.(5)
Outputsσ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V).Forge. Adversary AI outputs a ring signature σ∗ on a message m∗ that fulfills the following conditions:(1)
σ∗ is a valid ring signature.(2)
AI cannot query the partial private key of anyone in U.(3)
The forged signatureσ∗ is not from signature query.Output. It follows from the forking lemma that if ε≥7CqH2n/2k, adversary AI can give a valid forged signature within time TA in the above interaction; then we can construct another algorithm AI′ that outputs two signed messages within time 2TA with probability at least ε2/66CqH2n. For the resemble construction, C can get two valid ring signature σ and σ′ satisfying(8)σ=R1,R2,…,Rs-1,Rs,Rs+1,…,Rn,K1,…,Kn,m,V,σ′=R1,R2,…,Rs-1,Rs′,Rs+1,…,Rn,K1,…,Kn,m,V′.So we have(9)V=rPPub+rsSIDs+ksxsQ+kQ,V′=rPPub+rs′SIDs+ksxsQ+kQ.Challenger C outputs(10)abP=SIDs=rs-rs′-1V-V′.Probability. Let qH1, qH2, qH3, qD, qU, and qRS be times of H1 queries, H2 queries, H3 queries, partial private key queries, user public key queries, and ring signature queries, respectively. The probability that ID∗’s partial private key was not queried by AI during the queries is qH1-qD/qH1. The probability that ID∗ belongs to the groups W is n/qH1-qD. The probability that ID∗ is the actual signer is 1/n. So the combined probability is qH1-qD/qH1·n/qH1-qD·1/n=1/qH1.Therefore, according to the forking lemma, if the attackerAI can succeed in making a valid ring signature with a probability ε, the advantage of challenger C solving an instance of CDH problem in game 1 is at least ε2/66CqH2n·1/qH1.


## 5.2. Unforgeability against Type II Adversary

Theorem 9.
The scheme is unforgeable against a type II adversaryAII in the random oracle model if the co-CDH problem is hard.Proof.
Suppose challengerC receives a random instance (aP,X) of the co-CDH and has to compute the value of aX. Challenger C sets Q=X. Challenger C will run adversary AII as a subroutine and act as AII’s challenger in the game 2. Without loss of generality, we assume that all the queries are distinct. Now, we will show how challenger C answers type II adversary AII’s queries in the following.
Initialization. At the beginning of the game, challenger C runs the setup algorithm with the parameter z and gives adversary AII the system parameters: (G1,G2,d,P,Q,PPub,e,H1,H2,H3) and the system master secret key θ.(i)
H1 Queries. Challenger C maintains the list L1 of tuple (IDi,viP). The list is initially empty. When adversary AII makes a query H1(IDi), challenger C selects a value vi∈Zd∗ randomly and computes H1(IDi)=viP. Then challenger C adds (IDi,viP) to the H1 list and returns viP to AII.(ii)
H2 Queries. Same as that in the proof of Theorem 8.(iii)
H3 Queries. Same as that in the proof of Theorem 8.(iv)
User Public Key Queries. Challenger C maintains the list LU of tuple (IDi,Yi,xi). The list is initially empty. When adversary AII makes a user public key query for IDi, challenger C responds as follows. Challenger C chooses a random integer j in [1,qU] firstly. At the ith qU query, if i≠j, challenger C selects a value xi∈Zd∗ randomly and sets Yi=xiP. Otherwise, challenger C sets IDj=ID∗ and Y∗=aP.(v)
Partial Private Key Queries. Adversary AII can compute the partial private keys of any identities by himself with the master secret key.(vi)
User Public Key Replacements. Same as that in the proof of Theorem 8.(vii)
Secret Value Queries. Challenger C maintains the list LE of tuple (IDi,xi). The list is initially empty. When adversary AII makes a user partial private key query for IDi, if IDi=ID∗, C fails and stops. Otherwise challenger C finds the tuple (IDi,xi) in the list LU. Then challenger C adds (IDi,xi) to the LE list and returns xi to AII.(viii)
Ring Signature Queries. Same as that in the proof of Theorem 8.
Forge. Eventually, AII outputs a ring signature σ∗ fulfilling the following conditions:(1)
σ∗ is a valid ring signature.(2)
AII cannot query the secret value of anyone in U.(3)
AII cannot replace any users’ public key in U.(4)
The forged signatureσ∗ is not from signature query.
Output. It follows from the forking lemma that if ε≥7CqH3n/2k, adversary AII can give a valid forged signature within time TA in the above interaction; then we can construct another algorithm AII′ that outputs two signed messages within time 2TA with probability at least ε2/66CqH3n. For the resemble construction, C can get two valid ring signature σ and σ′ satisfying(11)σ=R1,…,Rn,K1,K2,…,Ks-1,Ks,Ks+1,…,Kn,m,V,σ′=R1,…,Rn,K1,K2,…,Ks-1,Ks′,Ks+1,…,Kn,m,V′.
So we have(12)V=rPPub+rsSIDs+ksxsQ+kQ,V′=rPPub+rsSIDs+ks′xsQ+kQ.Challenger C outputs(13)aX=xsQ=ks-ks′-1V-V′.
Probability. Let qH1, qH2, qH3, qE, qR, qU, and qRS be the times of H1 queries, H2 queries, H3 queries, secret value queries, user public key replacement requests, user public key queries, and ring signature queries, respectively.
For simplification, we may assume thatLE∩LR=ϕ. The probability that ID∗’s secret value was not queried and ID∗’s public key was not replaced by AII during the queries is qU-qE-qR/qU. The probability that ID∗ belongs to the groups W is n/qU-qE-qR. The probability that ID∗ is the actual signer is 1/n. So the combined probability is: qU-qE-qR/qU·n/qU-qE-qR·1/n=1/qU.Therefore, according to the forking lemma, if the attackerAII can succeed in making a valid ring signature with a probability ε, the advantage of challenger C solving an instance of co-CDH problem in the game 2 is at least ε2/66CqH3n·1/qU.


## 5.3. Unconditional Anonymity

Theorem 10.
Our certificateless ring signature scheme has the property of unconditional anonymity. For any algorithmA, any set of signers U=(u1,u2,…,un) and a random us∈U, the probability Pr[μ=μ′]=1/2, where σ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V) is a ring signature on U generated by us.Proof.
(i) The challengerC runs the setup algorithm to obtain a list of system parameters. And challenger C sends system parameters to adversary A.
(ii) The adversaryA adaptively makes a polynomially bounded number of queries.
(iii) The adversaryA outputs a message m, two different members ID1,ID2∈W to the challenger C. The challenger C randomly chooses a bit μ∈{0,1} and sends A to a ring signature σ=RS(m,W,xμ).
(iv) The adversaryA can make a polynomially bounded number of queries.
(v) Finally, adversaryA outputs a bit μ′∈{0,1}.In our scheme, sinceRi,Ki are chosen randomly from G1,  ri,ki are also random elements from Zd∗. Moreover, rs,ks are chosen randomly from Zd∗, so V is also a random element from G1. For anyone of a set of signers U, message m, the distribution of σ=(R1,R2,…,Rn,K1,K2,…,Kn,m,V) is independently and uniformly distributed no matter who the actual signer is. The fact illustrates that anyone has no advantage to know who signs the certificateless ring signature. Hence, Pr[μ=μ′]=1/2; the anonymity holds.


## 6. Comparison

### 6.1. Comparison of the Efficiency

We will compare the performance of our scheme with several certificateless ring signature schemes; see Table2. The running times are listed in Table 1. We define some notations as follows:(i)
PO: a pairing operation.(ii)
TPO: a pairing-based scalar multiplication operation.(iii)
TE: an ECC-based scalar multiplication operation.(iv)
TN: a modular exponent operation in G2.Table 1
Cryptographic operation time (in milliseconds).
PO
T
P
O
T
E
T
N
20.01
6.38
0.83
5.31Table 2
Comparison of the efficiency of several certificateless ring signature schemes.
Schemes
Sign phase
Verify phase
Time(n=10)
Scheme [32]
P
O
+
(
3
n
-
2
)
T
E
+
T
N
n
P
O
+
n
T
E
+
T
N
256.96
Scheme [33]
2
P
O
+
3
n
T
E
+
(
2
n
+
1
)
T
N
3
P
O
+
2
n
T
E
253.06
Scheme [31]
2
P
O
+
T
P
O
+
(
2
n
+
1
)
T
N
2
P
O
+
T
P
O
+
(
2
n
+
1
)
T
N
315.82
Our scheme
(
2
n
+
4
)
T
E
3
P
O
+
T
P
O
+
2
n
T
E
102.93


### 6.2. Comparison of the Security

We will give the comparison of the security of our scheme and several previous certificateless ring signature schemes [31–33] from the hard problems that these schemes rely on and the models these schemes depend on; see Table 3.Table 3
Comparison of the security of several certificateless ring signature schemes.
Schemes
Hard problems
Models
Scheme [32]
k-CAA problem and mICDH problem
Random oracle model (ROM)
Scheme [33]
DL problem and CDH problem
ROM
Scheme [31]
DL problem and CDH problem
ROM
Our scheme
CDH problem and co-CDH problem
ROM


## 6.1. Comparison of the Efficiency

We will compare the performance of our scheme with several certificateless ring signature schemes; see Table2. The running times are listed in Table 1. We define some notations as follows:(i)
PO: a pairing operation.(ii)
TPO: a pairing-based scalar multiplication operation.(iii)
TE: an ECC-based scalar multiplication operation.(iv)
TN: a modular exponent operation in G2.Table 1
Cryptographic operation time (in milliseconds).
PO
T
P
O
T
E
T
N
20.01
6.38
0.83
5.31Table 2
Comparison of the efficiency of several certificateless ring signature schemes.
Schemes
Sign phase
Verify phase
Time(n=10)
Scheme [32]
P
O
+
(
3
n
-
2
)
T
E
+
T
N
n
P
O
+
n
T
E
+
T
N
256.96
Scheme [33]
2
P
O
+
3
n
T
E
+
(
2
n
+
1
)
T
N
3
P
O
+
2
n
T
E
253.06
Scheme [31]
2
P
O
+
T
P
O
+
(
2
n
+
1
)
T
N
2
P
O
+
T
P
O
+
(
2
n
+
1
)
T
N
315.82
Our scheme
(
2
n
+
4
)
T
E
3
P
O
+
T
P
O
+
2
n
T
E
102.93


## 6.2. Comparison of the Security

We will give the comparison of the security of our scheme and several previous certificateless ring signature schemes [31–33] from the hard problems that these schemes rely on and the models these schemes depend on; see Table 3.Table 3
Comparison of the security of several certificateless ring signature schemes.
Schemes
Hard problems
Models
Scheme [32]
k-CAA problem and mICDH problem
Random oracle model (ROM)
Scheme [33]
DL problem and CDH problem
ROM
Scheme [31]
DL problem and CDH problem
ROM
Our scheme
CDH problem and co-CDH problem
ROM


## 7. Conclusion

There are some certificateless ring signature schemes based on bilinear pairings, which have been proposed over last years. But the computation cost of the pairings is very high. Therefore it is always interesting to design a cryptographic scheme with less pairing operations to speed up the computation of pairing function. In this paper, we propose an efficient certificateless ring signature scheme with only three bilinear parings. We also prove the unforgeability of our signature scheme against type I and type II adversaries in the random oracle based on the hardness of Computational Diffe-Hellman problem and co-Computational Diffe-Hellman problem. From Table2, we can see that our scheme is more efficient than the previous related schemes. Due to the good properties of our scheme, it is very useful for practical applications.



---

*Source: 7696858-2017-06-21.xml*