# Certificateless Proxy Signature from RSA

Authors: Lunzhi Deng; Jiwen Zeng; Yunyun Qu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Although some good results were achieved in speeding up the computation of pairing function in recent years, it is still interesting to design efficient cryptosystems with less bilinear pairing operation. A proxy signature scheme allows a proxy signer to sign messages on behalf of an original signer within a given context. We propose a certificateless proxy signature (CLPS) scheme from RSA and prove its security under the strongest security model where the Type I/II adversary is a super Type I/II adversary.


---

## Body

## 1. Introduction

Public key cryptography is an important technique to realize network and information security. Traditional public key infrastructure requires a trusted certification authority to issue a certificate binding the identity and the public key of an entity. Hence, the problem of certificate management arises. To solve the problem, Shamir defined a new public key paradigm called identity-based public key cryptography [1]. However, identity-based public key cryptography needs a trusted PKG to generate a private key for an entity according to its identity. So we are confronted with the key escrow problem. Fortunately, the two problems in traditional public key infrastructure and identity-based public key cryptography can be prohibited by introducing certificateless public key cryptography (CLPKC) [2], which can be conceived as an intermediate between traditional public key infrastructure and identity-based cryptography.


### 1.1. Certificateless Cryptography

In 2003, Al-Riyami and Paterson [2] introduced the notion of certificateless public key cryptography. Its goal is to remove the key escrow property from identity-based cryptography and has attracted a great extent of attention lately [3–11]. Certificateless cryptography not only eliminates the key escrow property but also removes certificates. It lets a semitrusted KGC issue a user partial key to a user with respect to his/her identity. By possessing both the user partial key and a self-generated user secret key, the user is able to carry out predefined cryptographic operations. Typically there are two types of attacks to consider in certificateless cryptography. One is called KGC Attack in which the KGC is malicious and targets forge signatures from its knowledge about the user’s partial key. The other one is called Key Replacement Attack in which the user’s public/secret key pair could be replaced by a third party but this user’s partial key issued by the KGC is not revealed. Au et al. [12] further investigated the types of malicious activities that the semitrusted KGC may be allowed to perform in practice and proposed a new strong security model called Malicious-but-Passive KGC Attack to replace original KGC Attack. A Malicious-but-Passive KGC may generate system parameters and the master key pair without following the scheme specification. Several certificateless signature schemes have been found vulnerable to this attack.


### 1.2. Cryptography from RSA

In 1985, Shamir [1] proposed the first identity-based signature scheme from the RSA primitive. In 1990, Guillou and Quisquater [13] proposed a similar RSA identity-based signature scheme, which is constructed from a zero-knowledge identification protocol. Herranz [14] proposed identity-based ring signatures from RSA whose security is based on the hardness of the RSA problem. After initial schemes, the following breakthrough result in the area of identity-based cryptography came in 2003, when Boneh and Franklin [15] designed an efficient identity-based public key encryption scheme. In the design, they used as a tool bilinear pairings, a kind of maps which can be constructed on some elliptic curves. Since the appearance of this work, a lot of cryptography schemes have been proposed for encryption, signature, key agreement, and so forth and they all employ such bilinear pairings. However, it is still desirable to find cryptography schemes which do not need to employ bilinear pairings.


### 1.3. Proxy Signature

The concept of proxy signatures was first introduced by Mambo et al. [16]. Based on the delegation type, they classified proxy signature schemes into three types: full delegation, partial delegation, and delegation by warrant. In a full delegation scheme, the original signer’s private key is given to the proxy signer. Hence, the proxy signer has the same signing right as the original signer. Obviously, such schemes are impractical and insecure for most of real-world settings. In a partial delegation scheme, a proxy signer has a new key, called proxy private key, which is different from the original’s private key. Although proxy signatures generated by using proxy private key are different from the original signers standard signatures, the proxy signer is not limited on the range of messages he can sign. This weakness is eliminated in delegation by warrant schemes. One of the main advantages of the use of warrants is that it is possible to include any type of security policy (that specifies what kinds of messages are delegated and may contain other information, such as the identities of the original signer, the proxy signer, the delegation period, etc.) in the warrant to describe the restrictions under which the delegation is valid. Therefore, proxy signature scheme which uses the method of this approach attracts a great interest, and it is often expected that new proxy signature schemes will implement the functionality of warrants.In order to adapt different situations, many proxy signature variants are produced, such as one-time proxy signature, proxy blind signature, and multiproxy signature. Since the proxy signature appears, it attracts many researchers’ great attention. Using bilinear pairings, people proposed many new ID-based proxy signature (IBPS) schemes [17–31] and certificateless proxy signature (CLPS) [32–38] schemes. All the above schemes are very practical, but they are based on bilinear pairings and the pairing is regarded as the most expensive cryptography primitive. The relative computation cost of a pairing is much higher than that of the scalar multiplication over elliptic curve group. Therefore, CLPS scheme without less bilinear pairing operations would be more appealing in terms of efficiency.


### 1.4. Motivations and Our Contributions

Although some good results were achieved in speeding up the computation of pairing function in recent years, it is still interesting to design cryptographic scheme without pairing operations.In this paper, we propose a certificateless proxy signature (CLPS) scheme, which has the following features.(i)
The proposed scheme is security under the strongest security model. Namely, in the scheme, the super Type I/II adversary can obtain the valid signatures for the replaced public key, without additional submission.(ii)
The proposed scheme not only enjoys a high security level but is also very efficient. The scheme does not need pairing operation. To the best of authors’ knowledge, our scheme is the first certificateless proxy signature scheme from RSA.


## 1.1. Certificateless Cryptography

In 2003, Al-Riyami and Paterson [2] introduced the notion of certificateless public key cryptography. Its goal is to remove the key escrow property from identity-based cryptography and has attracted a great extent of attention lately [3–11]. Certificateless cryptography not only eliminates the key escrow property but also removes certificates. It lets a semitrusted KGC issue a user partial key to a user with respect to his/her identity. By possessing both the user partial key and a self-generated user secret key, the user is able to carry out predefined cryptographic operations. Typically there are two types of attacks to consider in certificateless cryptography. One is called KGC Attack in which the KGC is malicious and targets forge signatures from its knowledge about the user’s partial key. The other one is called Key Replacement Attack in which the user’s public/secret key pair could be replaced by a third party but this user’s partial key issued by the KGC is not revealed. Au et al. [12] further investigated the types of malicious activities that the semitrusted KGC may be allowed to perform in practice and proposed a new strong security model called Malicious-but-Passive KGC Attack to replace original KGC Attack. A Malicious-but-Passive KGC may generate system parameters and the master key pair without following the scheme specification. Several certificateless signature schemes have been found vulnerable to this attack.


## 1.2. Cryptography from RSA

In 1985, Shamir [1] proposed the first identity-based signature scheme from the RSA primitive. In 1990, Guillou and Quisquater [13] proposed a similar RSA identity-based signature scheme, which is constructed from a zero-knowledge identification protocol. Herranz [14] proposed identity-based ring signatures from RSA whose security is based on the hardness of the RSA problem. After initial schemes, the following breakthrough result in the area of identity-based cryptography came in 2003, when Boneh and Franklin [15] designed an efficient identity-based public key encryption scheme. In the design, they used as a tool bilinear pairings, a kind of maps which can be constructed on some elliptic curves. Since the appearance of this work, a lot of cryptography schemes have been proposed for encryption, signature, key agreement, and so forth and they all employ such bilinear pairings. However, it is still desirable to find cryptography schemes which do not need to employ bilinear pairings.


## 1.3. Proxy Signature

The concept of proxy signatures was first introduced by Mambo et al. [16]. Based on the delegation type, they classified proxy signature schemes into three types: full delegation, partial delegation, and delegation by warrant. In a full delegation scheme, the original signer’s private key is given to the proxy signer. Hence, the proxy signer has the same signing right as the original signer. Obviously, such schemes are impractical and insecure for most of real-world settings. In a partial delegation scheme, a proxy signer has a new key, called proxy private key, which is different from the original’s private key. Although proxy signatures generated by using proxy private key are different from the original signers standard signatures, the proxy signer is not limited on the range of messages he can sign. This weakness is eliminated in delegation by warrant schemes. One of the main advantages of the use of warrants is that it is possible to include any type of security policy (that specifies what kinds of messages are delegated and may contain other information, such as the identities of the original signer, the proxy signer, the delegation period, etc.) in the warrant to describe the restrictions under which the delegation is valid. Therefore, proxy signature scheme which uses the method of this approach attracts a great interest, and it is often expected that new proxy signature schemes will implement the functionality of warrants.In order to adapt different situations, many proxy signature variants are produced, such as one-time proxy signature, proxy blind signature, and multiproxy signature. Since the proxy signature appears, it attracts many researchers’ great attention. Using bilinear pairings, people proposed many new ID-based proxy signature (IBPS) schemes [17–31] and certificateless proxy signature (CLPS) [32–38] schemes. All the above schemes are very practical, but they are based on bilinear pairings and the pairing is regarded as the most expensive cryptography primitive. The relative computation cost of a pairing is much higher than that of the scalar multiplication over elliptic curve group. Therefore, CLPS scheme without less bilinear pairing operations would be more appealing in terms of efficiency.


## 1.4. Motivations and Our Contributions

Although some good results were achieved in speeding up the computation of pairing function in recent years, it is still interesting to design cryptographic scheme without pairing operations.In this paper, we propose a certificateless proxy signature (CLPS) scheme, which has the following features.(i)
The proposed scheme is security under the strongest security model. Namely, in the scheme, the super Type I/II adversary can obtain the valid signatures for the replaced public key, without additional submission.(ii)
The proposed scheme not only enjoys a high security level but is also very efficient. The scheme does not need pairing operation. To the best of authors’ knowledge, our scheme is the first certificateless proxy signature scheme from RSA.


## 2. Preliminaries

Definition 1.
LetN=pq, where p and q are two k-bit prime numbers. Let b be a random prime number, greater than 2l for some fixed parameter l, such that gcd(b,φ(N))=1. Let Y be a random element in ZN*. We say that an algorithm C solves the RSA problem if it receives as input the tuple (N,b,Y) and outputs an element X such that Xb=Y mod N.Definition 2.
Given a generatorg of a group G of prime order b, and an element gx∈G, the discrete logarithm problem (DLP) is to compute x.


### 2.1. Model of Certificateless Proxy Signature Scheme

A certificateless proxy signature scheme consists of the following eight algorithms: setup, partial private key extraction, secret value setting, user public key generation, delegate, delegation verify, proxy sign, and proxy signature verify:(i)
Setup. This algorithm takes as input a security parameter k and returns params (system parameters) and a randomly chosen master secret key msk. After the algorithm is performed, the KGC publishes the system parameters params and keeps the master key msk secret.(ii)
Partial Private Key Extract. This algorithm takes as input params, msk, and an identity ID∈{0,1}* of an entity and returns a partial private key DID. The KGC carries out the algorithm to generate the partial private key DID and sends DID to the corresponding owner ID via a secure channel.(iii)
Secret Value Set. This algorithm takes the params, an identity ID, as input and outputs a secret value tID. This algorithm is run by the identity ID for itself.(iv)
User Public Key Generate. This algorithm takes the params, an identity ID and the identity’s secret value tID as input. It outputs the public key PKID for the identity ID. This algorithm is run by the identity ID for itself.(v)
Delegate. This algorithm takes as input the params, original signer’s full private key (to,Do), a warrant mw, and outputs the delegation π.(vi)
Delegation Verify. This algorithm takes as input params, π, and verifies whether π is a valid delegation from the original signer.(vii)
Proxy Sign. This algorithm takes as input the params, proxy signer’s full private key (tp,Dp), delegation π, a message m, and outputs the proxy signature σ.(viii)
Proxy Signature Verify. This algorithm takes as input the params, original signer’s identity/public key IDo/PKo, proxy signer’s identity/public key IDp/PKp, a proxy signature σ, and outputs 1 if the proxy signature is valid or 0 otherwise.Definition 3.
A certificateless proxy signature scheme (CLPS) is said to be existentially unforgeable against adaptive chosen message attacks (EUF-CLPS-CMA) if no polynomially bounded adversary has a nonnegligible advantage in the following two games against Type I and Type II adversaries.Game I. Now we illustrate the first game performed between a challenger C and a Type I adversary AI for a certificateless proxy signature scheme.Initialization. C runs the setup algorithm to generate a master secret key msk and the public system parameters params. C keeps msk secret and gives params to AI. We should bear in mind that AI does not know msk.Queries. AI performs a polynomially bounded number of queries. These queries may be made adaptively; that is, each query may depend on the answers to the previous queries.(i)
Create user: on inputting an identityID∈{0,1}*, if ID has already been created, nothing is to be carried out. Otherwise, C runs the algorithms partial private key extract, secret value set, and user public key generate to obtain the partial private key DID, secret value tID, and public key PKID. In this case, ID is said to be created and PKID is returned.(ii)
Partial private key extract: on inputting an identityID, it returns the partial private key DID if ID has been created. Otherwise, returns 0.(iii)
Public key replace: on inputting an identityID and a user public key PKID, the original user public key of ID is replaced with PKID if ID has been created. Otherwise, no action will be taken.(iv)
Secret value set: on inputting an identityID, it returns the corresponding user secret key tID if ID has been created. Otherwise, returns 0. Note that tID is the secret value associated with the original public key PKID. AI cannot query the secret value for ID whose public key has been replaced.(v)
Delegate: whenAI submits original signer’s identity/public key IDo/Po and a warrant mw to the challenger, C responds by running the delegate algorithm on the warrant mw and the original signer’s full private key (to,Do).(vi)
Proxy sign: whenAI submits a delegation π and a message m to the challenger, C responds by running the proxy sign algorithm on the delegation π, message m, and the proxy signer’s full private key (tp,Dp).Forge. AI outputs a tuple
(1)(π*,IDo,PKo)or(m*,mw*,σ*,IDo,PKo,IDp,PKp).AI wins the game, if one of the following cases is satisfied:(i)
Case 1: The final output is(π*,IDo,PKo) and it satisfies
(1)
π* is a valid delegation.(2)
π* is not generated from the delegation query on (IDo,PKo).(3)
AI does not query the original signer IDo’s partial private key.(4)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced.(ii)
Case 2: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
The tuple (IDo,PKo,IDp,PKp,mw*) does not appear in delegation query.(4)
AI does not query the original signer IDo’s partial private key.(5)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced.(iii)
Case 3: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
AI does not query the proxy signer IDp’s partial private key.(4)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced. The advantage of AI is defined as AdvAIEUF-CLPS-CMA=Pr[AIwin].Game II. A Type II adversary AII plays the second game with a challenger C as follows.Initialization. C runs the setup algorithm to obtain a master secret key msk and public system parameters params. C gives params and msk to AII. We should bear in mind that AII know msk.Queries. AII may adaptively make a polynomially bounded number of queries as in Game I.Forge. AII outputs a tuple(2)(π*,IDo,PKo)or(m*,mw*,σ*,IDo,PKo,IDp,PKp).AII wins the game, if one of the following cases is satisfied(i)
Case  1: The final output is(π*,IDo,PKo) and it satisfies
(1)
π* is a valid delegation.(2)
π* is not generated from the delegation query on (IDo,PKo).(3)
AII does not replace the original signer IDo’s public key.(4)
AII does not query the original signer IDo’s secret value.(5)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.(ii)
Case  2: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
The tuple (IDo,PKo,IDp,PKp,mw*) does not appear in delegation query.(4)
AII does not replace the original signer IDo’s public key.(5)
AII does not query the original signer IDo’s secret value.(6)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.(iii)
Case  3: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
AII does not replace the proxy signer IDp’s public key.(4)
AII does not query the proxy signer IDp’s secret value.(5)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.The advantage of AII is defined as AdvAIIEUF-CLPS-CMA=Pr[AIIwin].


## 2.1. Model of Certificateless Proxy Signature Scheme

A certificateless proxy signature scheme consists of the following eight algorithms: setup, partial private key extraction, secret value setting, user public key generation, delegate, delegation verify, proxy sign, and proxy signature verify:(i)
Setup. This algorithm takes as input a security parameter k and returns params (system parameters) and a randomly chosen master secret key msk. After the algorithm is performed, the KGC publishes the system parameters params and keeps the master key msk secret.(ii)
Partial Private Key Extract. This algorithm takes as input params, msk, and an identity ID∈{0,1}* of an entity and returns a partial private key DID. The KGC carries out the algorithm to generate the partial private key DID and sends DID to the corresponding owner ID via a secure channel.(iii)
Secret Value Set. This algorithm takes the params, an identity ID, as input and outputs a secret value tID. This algorithm is run by the identity ID for itself.(iv)
User Public Key Generate. This algorithm takes the params, an identity ID and the identity’s secret value tID as input. It outputs the public key PKID for the identity ID. This algorithm is run by the identity ID for itself.(v)
Delegate. This algorithm takes as input the params, original signer’s full private key (to,Do), a warrant mw, and outputs the delegation π.(vi)
Delegation Verify. This algorithm takes as input params, π, and verifies whether π is a valid delegation from the original signer.(vii)
Proxy Sign. This algorithm takes as input the params, proxy signer’s full private key (tp,Dp), delegation π, a message m, and outputs the proxy signature σ.(viii)
Proxy Signature Verify. This algorithm takes as input the params, original signer’s identity/public key IDo/PKo, proxy signer’s identity/public key IDp/PKp, a proxy signature σ, and outputs 1 if the proxy signature is valid or 0 otherwise.Definition 3.
A certificateless proxy signature scheme (CLPS) is said to be existentially unforgeable against adaptive chosen message attacks (EUF-CLPS-CMA) if no polynomially bounded adversary has a nonnegligible advantage in the following two games against Type I and Type II adversaries.Game I. Now we illustrate the first game performed between a challenger C and a Type I adversary AI for a certificateless proxy signature scheme.Initialization. C runs the setup algorithm to generate a master secret key msk and the public system parameters params. C keeps msk secret and gives params to AI. We should bear in mind that AI does not know msk.Queries. AI performs a polynomially bounded number of queries. These queries may be made adaptively; that is, each query may depend on the answers to the previous queries.(i)
Create user: on inputting an identityID∈{0,1}*, if ID has already been created, nothing is to be carried out. Otherwise, C runs the algorithms partial private key extract, secret value set, and user public key generate to obtain the partial private key DID, secret value tID, and public key PKID. In this case, ID is said to be created and PKID is returned.(ii)
Partial private key extract: on inputting an identityID, it returns the partial private key DID if ID has been created. Otherwise, returns 0.(iii)
Public key replace: on inputting an identityID and a user public key PKID, the original user public key of ID is replaced with PKID if ID has been created. Otherwise, no action will be taken.(iv)
Secret value set: on inputting an identityID, it returns the corresponding user secret key tID if ID has been created. Otherwise, returns 0. Note that tID is the secret value associated with the original public key PKID. AI cannot query the secret value for ID whose public key has been replaced.(v)
Delegate: whenAI submits original signer’s identity/public key IDo/Po and a warrant mw to the challenger, C responds by running the delegate algorithm on the warrant mw and the original signer’s full private key (to,Do).(vi)
Proxy sign: whenAI submits a delegation π and a message m to the challenger, C responds by running the proxy sign algorithm on the delegation π, message m, and the proxy signer’s full private key (tp,Dp).Forge. AI outputs a tuple
(1)(π*,IDo,PKo)or(m*,mw*,σ*,IDo,PKo,IDp,PKp).AI wins the game, if one of the following cases is satisfied:(i)
Case 1: The final output is(π*,IDo,PKo) and it satisfies
(1)
π* is a valid delegation.(2)
π* is not generated from the delegation query on (IDo,PKo).(3)
AI does not query the original signer IDo’s partial private key.(4)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced.(ii)
Case 2: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
The tuple (IDo,PKo,IDp,PKp,mw*) does not appear in delegation query.(4)
AI does not query the original signer IDo’s partial private key.(5)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced.(iii)
Case 3: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
AI does not query the proxy signer IDp’s partial private key.(4)
AI cannot query the secret value for any identity if the corresponding public key has already been replaced. The advantage of AI is defined as AdvAIEUF-CLPS-CMA=Pr[AIwin].Game II. A Type II adversary AII plays the second game with a challenger C as follows.Initialization. C runs the setup algorithm to obtain a master secret key msk and public system parameters params. C gives params and msk to AII. We should bear in mind that AII know msk.Queries. AII may adaptively make a polynomially bounded number of queries as in Game I.Forge. AII outputs a tuple(2)(π*,IDo,PKo)or(m*,mw*,σ*,IDo,PKo,IDp,PKp).AII wins the game, if one of the following cases is satisfied(i)
Case  1: The final output is(π*,IDo,PKo) and it satisfies
(1)
π* is a valid delegation.(2)
π* is not generated from the delegation query on (IDo,PKo).(3)
AII does not replace the original signer IDo’s public key.(4)
AII does not query the original signer IDo’s secret value.(5)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.(ii)
Case  2: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
The tuple (IDo,PKo,IDp,PKp,mw*) does not appear in delegation query.(4)
AII does not replace the original signer IDo’s public key.(5)
AII does not query the original signer IDo’s secret value.(6)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.(iii)
Case  3: The final output is(m*,mw*,σ*,IDo,PKo,IDp,PKp) and it satisfies
(1)
σ* is a valid proxy signature.(2)
σ* is not generated from the proxy signature query.(3)
AII does not replace the proxy signer IDp’s public key.(4)
AII does not query the proxy signer IDp’s secret value.(5)
AII cannot query the secret value for any identity if the corresponding public key has already been replaced.The advantage of AII is defined as AdvAIIEUF-CLPS-CMA=Pr[AIIwin].


## 3. Our Certificateless Proxy Signature Scheme

(i)
Setup: given the security parameter of the systemk, the KGC generates two random k-bit prime numbers p and q. Then it computes N=pq. For some fixed parameter l (for example l=160), it chooses at random a prime number b satisfying 2l<b<2l+1 and gcd(b,φ(N))=1. Then it chooses group G of prime order b, a generator g of G, and computes a=b-1 mod φ(N). Furthermore, KGC chooses five cryptographic hash functions described as follows: H0:{0,1}*→ZN*,  H1,H2,H3,H4:{0,1}*→Zb*. Finally, KGC outputs the set of public parameters: params = {N,b,G,g,H1,H2,H3}; the master secret key is (p,q,a).
(ii)
Partial private key extract: for an identityID∈{0,1}* his private key is DID=QIDa, QID=H0(ID). The KGC sends DID to the user ID via a secure channel.
(iii)
Set secret value: the user with identityID∈{0,1}* randomly chooses tID∈Zb*.
(iv)
User public key generation: the user with identityID∈{0,1}* computes his public key PID=gtID.
(v)
Delegate:mw is the warrant consisting of the identities/public keys of original signer and proxy signer, the delegation duration, and so on. On inputting the warrant mw, the original signer, whose identity/public key is IDo/Po, performs the following steps.
(vi)
Randomly selectsc∈Zb*, A∈ZN*, computes T1=gc, T2=Abmod⁡N, h1=H1(mw,T1,T2), h2=H2(mw,T1,T2).
(vii)
Computesr=c+toh1 mod b, R=ADoh2 mod N.
(viii)
Outputsπ=(mw,T1,T2,r,R) as the delegation.
(ix)
Delegation verify: to verify a delegationπ=(mw,T1,T2,r,R) for an identity/public key IDo/Po, the verifier performs the following steps.
Computesh1=H1(mw,T1,T2), h2=H2(mw,T1,T2).
Checking whethergr=T1Poh1, Rb=T2Qoh2mod⁡N, if both of equalities hold, accept the delegation. Otherwise, reject.
(x)
Proxy sign: for a messagem, the proxy signer (whose identity/public key is IDp/Pp) who owns the delegation π=(mw,T1,T2,r,R) does the following.
(1)
Randomly selectsd∈Zb*, B∈ZN*, computes S1=gd, S2=Bbmod⁡N, k1=H3(m,mw,T1,T2,S1,S2), k2=H4(m,mw,T1,T2,S1,S2).
(2)
Computesz=r+d+tpk1, Z=RBDpk2 mod N.
(3)
Outputs the signatureσ=(m,mw,T1,T2,S1,S2,z,Z).
(xi)
Proxy signature verify: to verify the validity of a proxy signature (where the original singer’s identity/public key isIDo/Po, the proxy singer’s identity/public key is IDp/Pp), a verifier first checks whether the original signer and proxy signer conform to mw and then performs the following steps.
(1)
Computesh1=H1(mw,T1,T2), h2=H2(mw,T1,T2).
(2)
Computesk1=H3(m,mw,T1,T2,S1,S2), k2=H4(m,mw,T1,T2,S1,S2).
(3)
Checking whethergz=T1S1Poh1Ppk1, Zb=T2S2Qoh2Qpk2 mod N, if both of equalities hold, outputs 1. Otherwise, outputs 0.
(xii)
On correctness, we have(3)gz=gr+d+tpk1=grgdgtpk1=T1Poh1S1Ppk1Zb=(RBDpk2)b=RbBbDpk2b=T2S2Qoh2Qpk2.


## 4. Security Results of Scheme 1

Theorem 4.
In the random oracle model, if there is an adversaryAI that can win the EUF-CLPS-CMA Game I with advantage ɛ and within time T, after making at most qH0H0 queries, qH1H1 queries, qH2  H2 queries, qH3H3 queries, qH4H4 queries, qU create user queries, qK partial private key extraction queries, qS set secret value queries, qR user public key replacement queries, qD delegation queries, and qP proxy signature queries, the RSA problem can be solved with probability ɛ/qH0 within time T+(qH0+2qD+2qP)Tm+(qU+qD+qP)Te, where Tm denotes the time for a modular operation and Te denotes the time for a exponentiation in G.Proof.
Suppose the challengerC receives a random instance (N,b,Y) of the RSA problem and has to find an element X∈ZN* such that Xb=Y. C will run AI as a subroutine and act as AI’s challenger in the EUF-CLPS-CMA game I.Setup. At the beginning of the game, C runs the setup program with the parameter k and gives A the system parameters: params = {N,b,G,g,H0,H1,H2,H3,H4}.Queries. Without loss of generality, we assume that all the queries are distinct and AI will make H0 query and create user query for ID before ID is used in any other queries.(i)
H0 queries: C maintains the list L0 of tuple (IDi,Ai). The list is initially empty. When AI makes a query H0(IDi), C responds as follows.
At thejth H0 query, C sets H0(ID*)=Y. For i≠j, C randomly picks a value Ai∈ZN* and sets H0(IDi)=Aib. Then, the query and the answer will be stored in the list L0.(ii)
H1 queries: C maintains the list L1 of tuple (αi,hi). The list is initially empty. When AI makes a query H1(αi), C randomly picks a value hi∈Zb* and sets H1(αi)=hi; the query and the answer will then be stored in the list L1.(iii)
H2 queries: C maintains the list L2 of tuple (αi,hi). The list is initially empty. When AI makes a query H2(αi), C randomly picks a value hi∈Zb* and sets H2(αi)=hi; the query and the answer will then be stored in the list L2.(iv)
H3 queries: C maintains the list L3 of tuple (βi,ki). The list is initially empty. When AI makes a query H3(βi), C randomly picks a value ki∈Zb* and sets H3(βi)=ki; the query and the answer will then be stored in the list L3.(v)
H4 queries: C maintains the list L4 of tuple (βi,ki). The list is initially empty. When AI makes a query H4(βi), C randomly picks a value ki∈Zb* and sets H4(βi)=ki; the query and the answer will then be stored in the list L4.(vi)
Create user queries:C maintains the list LU of tuple (IDi,ti,Di,Pi). AI makes creating user query for identity IDi and C first makes query H0(IDi) and gets (IDi,Ai) from list L0, then randomly chooses ti∈Zb*, sets Pi=gti. If IDi=ID*, C sets Di=0, otherwise sets Di=Ai. Then it sends the Pi to AI; the (IDi,ti,Di,Pi) will be stored in the list LU.(vii)
Partial private key extract:C maintains the list LK of tuple (IDi,Di). AI makes partial private key extraction query for identity IDi. If IDi=ID*, C fails and stops. Otherwise, C finds the tuple (IDi,ti,Di,Pi) in list LU and responds with the partial private key Di; the (IDi,Di) will be stored in the list LK.(viii)
User public key replace:C maintains the list LR of tuple (IDi,Pi,Pi′). AI makes user public key replacement request for identity IDi with a new valid public key value Pi′. C replaces the current public key value Pi with the value Pi′ and tuple (IDi,Pi,Pi′) will be stored in the list LR.(ix)
Set secret value:C maintains the list LS of tuple (IDi,ti). AI makes setting secret value query for identity IDi. C finds the tuple (IDi,ti,Di,Pi) in list LU and responds with the secret value ti; the (IDi,ti) will be stored in the list LS. (Note: AI cannot query the secret value for ID whose public key has been replaced.)(x)
Delegate:AI submits IDo/Po, IDp/Pp, and mw to challenger. C outputs a delegation as follows.
IfIDo≠ID* and IDo∉LR, C gives a delegation by calling the delegate algorithm. Otherwise, C does as follows.
(1)
Randomly selectsA∈ZN* and r,h1,h2∈Zb*.(2)
ComputesT1=Por-h1, T2=AbQo-h2 and R=A.(3)
Stores the relationsh1=H1(mw,T1,T2) and h2=H2(mw,T1,T2). If collision occurs, repeats the step (1)–(3).(4)
Outputsπ=(mw,T1,T2,r,R) as the delegation.(xi)
Proxy sign:AI submits a delegation π=(mw,T1,T2,r,R) message m to the challenger. C outputs a certificateless proxy signature as follows (where original signer’s identity/public key is IDo/Po, proxy signer’s identity/public key is IDp/Pp).
IfIDp≠ID* and IDp∉LR, C gives a signature by calling the proxy sign algorithm. Otherwise, C does as follows.
(1)
Randomly selectsB∈ZN* and y,k1,k2∈Zb*.(2)
ComputesS1=Ppy-k1, S2=BbQp-k2, z=r+y, and Z=RB.(3)
Stores the relationsk1=H3(m,mw,T1,T2,S1,S2) and k2=H4(m,mw,T1,T2,S1,S2). If collision occurs, repeats the step (1)–(3).(4)
Outputs the proxy signatureσ=(m,mw,T1,T2,S1,S2,z,Z).Forge. AI outputs a tuple
(4){π*=(mw,T1,T2,r,R),IDo,Po}or{σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp}.
If AI’s output satisfies none of the three cases in EUF-CLPS-CMA game I, C aborts; Otherwise, C can solve the RSA problem as follows.Case
1. The final output is {π*=(mw,T1,T2,r,R),IDo,Po} and the output satisfies the requirement of Case 1 as defined in EUF-CLPS-CMA game I. In fact, π* is the signature for mw by IDo. By the forking lemma for generic signature scheme, for the resemble construction we can get two delegations: (mw,T1,T2,r,R) and (mw,T1,T2,r,R′), where h1=h1′=H1(mw,T1,T2), h2=H2(mw,T1,T2), h2′=H2′(mw,T1,T2), and h2≠h2′. If IDo=ID*, we can solve RSA problem as follows. The relation becomes (R′R-1)b=Yh2′-h2 mod N. Since h2,h2′∈Zb, we have that |h2′-h2|<b. By the element b is a prime number. So gcd(b,h2′-h2)=1. This means that there exist two integers c and d such that cb+d(h2′-h2)=1. Finally, the value X=(R′R-1)dYc mod N is the solution of the given instance of the RSA problem. In effect, we have Xb=(R′R-1)bdYbc=Yd(h2′-h2)Ybc=Ycb+d(h2′-h2)=Y.Probability of Success. The probability that C does not fail during the queries is (qH0-qK)/qH0. The probability that IDo=ID* is 1/(qH0-qK). So the combined probability is ((qH0-qK)/qH0)·(1/(qH0-qK))=1/qH0. Therefore, the probability of C to solve the RSA problem is ϵ/qH0.Case
2. The final output is {σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp} and the output satisfies the requirement of Case 2 as defined in EUF-IBPS-CMA game I. By the forking lemma for generic signature scheme, for the resemble construction we can get two proxy signatures: (m,mw,T1,T2,S1,S2,z,Z) and (m,mw,T1,T2,S1,S2,z,Z′), where
(5)k1=k1′=H3(m,mw,T1,T2,S1,S2),k2=k2′=H4(m,mw,T1,T2,S1,S2)hhhhhhhh1=h1′=H1(mw,T1,T2),hhhhhhhhhhhh2=H2(mw,T1,T2),hhhhhhhhhhhh2′=H2′(mw,T1,T2),hhhhhhhhhhhhhhhhhhhhhhh2≠h2′.
If IDo=ID*, we can solve RSA problem as follows. The relation becomes (Z′Z-1)b=Yh2′-h2 mod N. Since h2,h2′∈Zb, we have that |h2′-h2|<b. By the element b is a prime number. So it holds gcd(b,h2′-h2)=1. This means that there exist two integers c and d such that cb+d(h2′-h2)=1. Finally, the value X=(Z′Z-1)dYc mod N is the solution of the given instance of the RSA problem. In effect, we have
(6)Xb=(Z′Z-1)bdYbc=Yd(h2′-h2)Ybc=Ycb+d(h2′-h2)=Y.Probability of success is the same as the probability in Case 1.Case
3. The final output is {σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp} and the output satisfies the requirement of Case 3 as defined in EUF-IBPS-CMA game I. By the forking lemma for generic signature scheme, for the resemble construction we can get two proxy signatures: (m,mw,T1,T2,S1,S2,z,Z) and (m,mw,T1,T2,S1,S2,z,Z′), where
(7)hhhhhhhh1=h1′=H1(mw,T1,T2),hhhhhhhh2=h2′=H2(mw,T1,T2),k1=k1′=H3(m,mw,T1,T2,S1,S2)hhhhk2=H4(m,mw,T1,T2,S1,S2),hhhhk2′=H4′(m,mw,T1,T2,S1,S2),hhhhhhhhhhhhhhhhhhhhhhk2≠k2′.
If IDp=ID*, we can solve RSA problem as follows. The relation becomes (Z′Z-1)b=Yk2′-k2 mod N. Since k2,k2′∈Zb, we have that |k2′-k2|<b. By the element b is a prime number. So it holds gcd(b,k2′-k2)=1. This means that there exist two integers c and d such that cb+d(k2′-k2)=1. Finally, the value X=(Z′Z-1)dYc mod N is the solution of the given instance of the RSA problem. In effect, we have
(8)Xb=(Z′Z-1)bdYbc=Yd(k2′-k2)Ybc=Ycb+d(k2′-k2)=Y.
Probability of success is the same as the probability in Case 1.Theorem 5.
In the random oracle model, if there is an adversaryAII that can win the EUF-CLPS-CMA game II with advantage ɛ and within time T, after making at most qH0  H0 queries, qH1H1 queries, qH2H2 queries, qH3H3 queries, qH4H4 queries, qU create user queries, qK partial private key extraction queries, qS set secret value queries, qR user public key replacement queries, qD delegate queries, qP proxy signature queries, the discrete logarithm problem DLP can be solved with probability ɛ/qU within time T+(qH0+2qD+2qP)Tm+(qU+qD+qP)Te, where Tm denote the time for a modular operation and Te denote the time for an exponentiation in G.Proof.
Suppose the challengerC receives a random instance (gx,g) of the DLP and has to compute the value of x. C will run AII as a subroutine and act as AII’s challenger in the EUF-CLPS-CMA game II.Setup. At the beginning of the game, C runs the setup program with the parameter k and gives A the system parameters: params = {N,b,G,g,H0,H1,H2,H3,H4} and master secret key (p,q,a).Queries. Without loss of generality, we assume that all the queries are distinct and AII will make H0 query and create user query for ID before ID is used in any other queries.(i)
H0 queries: C maintains the list L0 of tuple (IDi,Ai). The list is initially empty. When AII makes a query H0(IDi), C randomly picks a value Ai∈ZN* and sets H0(IDi)=Ai. Then, (IDi,Ai) will be stored in the list L0.(ii)
H1,H2,H3,H4 queries: same as that in the proof of Theorem 4.(iii)
Create user:C maintains the list LU of tuple (IDi,ti,Di,Pi). The list is initially empty. When AII makes creating user query for ID, C responds as follows.
At thejth create user query, C first makes query H0(ID*), gets (ID*,AID*) from list L0, sets DID*=AID*a and PID*=gx. i≠j, C first makes query H0(IDi), gets (IDi,Ai) from list L0, sets Di=Aia, then, randomly chooses ti∈Zb*, sets Pi=gti, then sends Pi to the AII; the query and the answer will be stored in the list LU.(iv)
Partial private key extract: SinceAII knows master secret key (p,q,a), he can compute partial private key for any identity by himself. Hence, C does not need making partial private key query.(v)
User public key replace:C maintains the list LR of tuple (IDi,Pi,Pi′). AII makes user public key replacement request for identity IDi with a new valid public key value Pi′. C replaces the current public key value Pi with the value Pi′ and tuple (IDi,Pi,Pi′) will be stored in the list LR.(vi)
Set secret value:C maintains the list LS of tuple (IDi,ti). AII makes partial private key query for identity IDi. If IDi=ID*, C fails and stops. Otherwise, C finds the tuple (IDi,ti,Di,Pi) in list LU and responds with the secret value ti; the (IDi,ti) will be stored in the list LS. (Note: AII cannot query the secret value for ID whose public key has been replaced.)(vii)
Delegate and proxy sign: Same as that in the proof of Theorem4.Forge. AII outputs a tuple
(9){π*=(mw,T1,T2,r,R),IDo,Po}or{σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp}.IfAII’s output satisfies none of the three cases in EUF-CLPS-CMA game II, C aborts; otherwise, C can solve the DLP in G as follows.Case
1. The final output is {π*=(mw,T1,T2,r,R),IDo,Po} and the output satisfies the requirement of Case 1 as defined in EUF-CLPS-CMA game II. In fact, π* is the signature for mw by IDo. By the forking lemma for generic signature scheme, for the resemble construction we can get two delegations: (mw,T1,T2,r,R) and (mw,T1,T2,r′,R), where
(10)hhiihh1=H1(mw,T1,T2),hhiihh1′=H1′(mw,T1,T2),h2=h2′=H2(mw,T1,T2),hhhhhhhhhhhiihhhh1≠h1′.
If IDo=ID*, we can solve DLP as follows: x=(r-r′)(h1-h1′)-1 mod b.Probability of Success. The probability that C does not fail during the queries is (qU-qS)/qU. The probability that IDo=ID* is 1/(qU-qS). So the combined probability is ((qU-qS)/qU)·(1/(qU-qS))=1/qU. Therefore, the probability of C to solve the DLP is ϵ/qU.Case
2. The final output is {σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp} and the output satisfies the requirement of Case 2 as defined in EUF-CLPS-CMA game II. By the forking lemma for generic signature scheme, for the resemble construction we can get two proxy signatures: (m,mw,T1,T2,S1,S2,z′,Z) and (m,mw,T1,T2,S1,S2,z′,Z), where
(11)hhiihh1=H1(mw,T1,T2),hiihhh1′=H1′(mw,T1,T2),h2=h2′=H2(mw,T1,T2),hhhhhhhhhhhhiihhh1≠h1′k1=k1′=H3(m,mw,T1,T2,S1,S2),k2=k2′=H4(m,mw,T1,T2,S1,S2).
If IDo=ID*, we can solve DLP as follows: x=(z-z′)(h1-h1′)-1 mod b.Probability of success is same as the probability in Case 1.Case
3. The final output is {σ*=(m,mw,T1,T2,S1,S2,z,Z),IDo,Po,IDp,Pp} and the output satisfies the requirement of Case 3 as defined in EUF-CLPS-CMA game II. By the forking lemma for generic signature scheme, for the resemble construction we can get two proxy signatures: (m,mw,T1,T2,S1,S2,z,Z) and (m,mw,T1,T2,S1,S2,z′,Z), where
(12)hhhhiihhh1=h1′=H1(mw,T1,T2),hhhhiihhh2=h2′=H2(mw,T1,T2),k2=k2′=H4(m,mw,T1,T2,S1,S2)hiihhk1=H3(m,mw,T1,T2,S1,S2),hhhhk1′=H3′(m,mw,T1,T2,S1,S2),hhhhhhhhhhhhhhhhhhhhhhk1≠k1′.
If IDp=ID*, we can solve DLP as follows: x=(z-z′)(k1-k1′)-1 mod b.Probability of success is same as the probability in Case 1.


## 5. Efficiency

Although some good results were achieved in speeding up the computation of pairing function in recent years, it is still desirable to find cryptography schemes which do not need to employ bilinear pairings. In this section, we compare the performance of our scheme with several CLPS schemes in Table2; we define some notations as follows.P: a pairing operation.EG a pairing-based scalar multiplication operation.ES: a scalar multiplication operation.EN: modular exponent in ZN.Cao et al. [39] obtained the running time for cryptographic operations through a PIV 3 GHZ processor with 512 M bytes memory and the Windows XP operating system. For the pairing-based scheme, to achieve the 1024-bit RSA level security, a supersingular curve E over a finite field Fp, with p=512 bits and a large prime order q=160 bits, was used. For the ECC-based schemes, to achieve the same security level, the ECC group on Koblitz elliptic curve y2=x3+ax2+b was used which is defined on F2163 with a=1 and b is a 163-bit random prime. The running times are listed in Table 1.Table 1
Cryptographic operation time (in milliseconds).
P
E
G
E
S
E
N
20.01
6.38
0.83
11.20Table 2
Comparison of several CLPS schemes.
Scheme
Delegate and verify
Sign and verify
Execution time
Li et al. [35]
4
P
+
3
E
G
7
P
+
4
E
G
265.87
Lu et al. [34]
4
P
+
3
E
G
7
P
+
4
E
G
265.87
Choi and Lee [32]
4
P
+
3
E
G
3
P
+
3
E
G
179.05
Seo et al. [36]
3
P
+
3
E
G
4
P
+
4
E
G
185.43
Zhang et al. [38]
4
P
+
3
E
G
5
P
+
2
E
G
212.89
Ours
3
E
S
+
4
E
N
3
E
S
+
4
E
N
94.58To evaluate the computation efficiency of different schemes, we use the simple method from [39]. For example, in Li et al. [35] scheme, eleven pairing operations and seven pairing-based scalar multiplication operation are needed. So the resulting computation time is 20.01×11+6.38×7=265.87. The detailed comparison results of several different CLPS schemes are illustrated in Table 2.


## 6. Conclusion

We proposed a certificateless proxy signature scheme and prove that our scheme is unforgeable under the strongest security model where the Type I/II adversary is a super Type I/II adversary. The analysis shows our scheme is more efficient than the related schemes. To the best of authors’ knowledge, our scheme is the first certificateless proxy signature scheme from RSA. Due to the good properties of our schemes, it is very useful for practical application.



---

*Source: 373690-2014-06-23.xml*