Certificateless One-Time Proxy Signature

HONG Dong-zhao

(College of Science, Hangzhou Normal University, Hangzhou 310036, China)

1 Introduction

In 1996, Mambo et al[1-2]proposed the concept of proxy signature. After that, several new proxy signature[3-8]schemes have been studied. To limit the power of the proxy signer, the notionof one-time proxy signature was introduced[9]. In this paradigm, the proxy signer uses the same proxy key to sign message more than once, then his private key will be leaked out. And then many one-time proxy signature schemes have been proposed[10-15]. Almost all one-time proxy signature schemes available in the literature are based on the traditional public key cryptography or the identity-based cryptography.

In 1984, Shamir[16]introduced the concept of Identity-based signature which avoids the necessity of certificates. However, an inherent problem of ID-based cryptosystems is the key escrow. To overcome the key escrow problem, Al-Riyami and Paterson[17]introduced the concept of certificateless signature (CLS) in 2003. Huang et al[18]formalized the security definition of certificateless signature. The security model of CLS schemes was further developed in[19-21].

In this paper, a certificateless one-time proxy signature scheme is proposed. The security model of certificateless one-time proxy signature scheme is formalized. The security model captures the notion of existential unforgeability of certificateless one-time proxy signature against Strong Type I and Super Type II adversaries[21]. The proposed scheme is provably secure in this model.

2 Definition and Security Model for CLOTPS

2.1 Definition

Definition1(Certificatelessone-timeproxysignature). Given an integerk, a certificateless one-time proxy signature scheme CLOTPS=(Setup, Partial-Private-Key-Extract, UserKeyGen, PSign, PVerify) with security parameterkis defined by the following:

1) Setup,KGCtakes as input a security parameterkand outputs public system parametersparamsand the master secret keymsk.

2) Partial-Private-Key-Extract,KGCtakes as inputparams,msk, and a user’s identityID, returns the partial private keysDID.

3) UserKeyGen, the user takes as inputparamsandDID, outputs the user’s public keyPKIDand corresponding secret keySKID.

4) PSign, the user takes as inputparams,msk, two identitiesIDo,IDp∈{0,1}*of the original signerUoand the proxy signerUp, a messagem, and a pair of public keys {PKIDo,PKIDp}, outputs a proxy signing keyoskforUp, at last, outputs a certificateless one-time proxy signatureσ.

5) Verify, the verifier takes as input a proxy signatureσ, returns 1 (accept) or 0 (reject).

For certificateless one-time proxy signature has also the following properties[22]: Correction, One timeness, Unforgeability, Identifiability, Undeniability, Prevention of misuse.

2.2 Security Model

Similar to the adversaries against certificateless signature scheme defined in [21], for the security of certificateless one-time proxy signature schemes, two types of adversaries are introduced, namely Strong Type I Adversary, Super Type II Adversary[23].

Strong Type I Adversary: A Type I AdversaryAIdoes not have access to the master-key, butAIis allowed to replace the public key of any user with his choice.

Super Type II Adversary: A Type II AdversaryAIIhas access to the master-key, butAIIisn’t allowed to replace the target user’s public key.

Two games are defined, one forAIand the other forAII.

GameI:The first game is performed between a challengerCand a Type I adversaryAIfor a certificateless one-time proxy signature scheme as follows.

Setup:Cruns the Setup algorithm of the CLOTPS scheme, takes as input a security parameterkto obtain amskandparams.Cthen sendsparamsto the adversaryAI.

Attack:The adversaryAIcan query the following oracles which are controlled byC.

Create-Useroracle: On input an identityID. IfIDhas not been created it runs the algorithms Partial-Private-Key-Extract, UserKeyGen to obtain the partial private keyDID, private keySKIDand public keyPKID. Then it adds (ID,*,DID,SKID,PKID) to the listL. In this case,IDis said to be created. In both cases,PKIDis returned.

Partial-Private-Keyoracle: On input an identityID, which has been created, returns the partial private keyDID; otherwise, returns ⊥.

Public-Key-Replacementoracle: On input an identityIDand a new public keyPKID′ and private keySKID′ if userIDhas been created,the oracle updates the corresponding information in the listL; otherwise, dose nothing.

Hashoracle:AIcan request the hash values for any input.

Public-Keyoracle: On input an identityID, which has been created, the oracle returns the public keyPKID.

Private-Keyoracle: On input an identityIDexcept the challenged identityID, which has been created, the oracle returnsSKID.

Proxy-Signoracle: On input a messagem, a warrantmw, an original signer’s identityIDo, a proxy signer’s identityIDp, the oracle outputs a proxy signatureσas answer.

Game2: The first game is performed between a challengerCand a Type II adversaryAIIfor a certificateless one-time proxy signature scheme as follows.

Setup:Cruns the Setup algorithm of the CLOTPS scheme, takes as input a security parameterkto obtainmskandparams.Cthen sendsparamsandmskto the adversaryAII.

Attack: The adversaryAIIcan query Create-User oracle, Hash oracle , Public-Key oracle, Public-Key-Replacement oracle, Private-Key oracle, Proxy-Sign oracle which are the same as that in Game I.

Due to the proxy warrantmwbinded in the signature, if only the unforgeability satisfies, other security requirements, such as identifiability, undeniability and prevention of misuse, obviously follow [14].

3 The New CLOTPS

3.1 Description of the New of CLOTPS

The new scheme CLOTPS which modifying the key generation algorithms of Lu et al.’s ID-based one-time proxy signature scheme is proposed as follows.

2)Partial-Private-Key-Extarct: GivenUo’s identityIDoandUp’sIDp∈{0,1}*.KGCsetsQIDo=H(IDo),DIDo=sH(IDo),QIDp=H(IDp) andDIDp=sH(IDp) and sends the partial private keyDIDotoUoandDIDptoUpvia some secure channel.

4)PSign: (identical with Lu et al.’s scheme)

a)Uomakes a warrantmwand sends it toUp.

d) To sign a messagem,Upcomputesσp=r2+r1·H2(R1,R2,m‖mw) modq. Finally,Upoutputs the proxy signatureσ=(σo,opk,mw,σp,m).

5)PVerify: (similar to Lu et al.’s scheme) Upon receiving the proxy signatureσ=(σo,opk,mw,σp,m), verifier checks that the following equations

Hold. If not, rejected. Otherwise, accepted.

The correctness of the scheme can be verified directly.

e(Yo,H(IDo))·e(Ro,H1(Ro,opk‖mw))=e(P,sxoH(IDo))·e(P,roH1(Ro,opk‖mw))=

e(P,sxoH(IDo)+roH1(Ro,opk‖mw))=e(P,SIDo+roH1(Ro,opk‖mw))=e(P,So)

3.2 Security Proof

Theorem1(One-timeness). The new CLOTPS scheme has the property of one-timeness.

This proof is similar to the proof of Theorem 1 in [14].

Theorem2Our CLOTPS scheme is secure against existential forgery under adaptively chosen message and chosen ID attacks in the random oracle model with the assumptions that CDH problem inGis intractable.

This theorem follows from the following Lemmas 1 and 2.

Lemma1Our CLOTPS scheme is unforgeable against a Strong Type I adversary in the random oracle model assuming the CDH problem is intractable.

Lemma2Our CLOTPS scheme is unforgeable against a Super Type II adversary in the random oracle model assuming the CDH problem is intractable.

Due to page limitation, the proof will be presented in the full version of this paper.

4 Conclusion

In this paper, an appropriate security model and a concrete construction of certificateless one-time proxy signature scheme are proposed. The security model takes into account the strong adversaries in certificateless public key settings. The security of the proposed scheme is provable secure in the random model with the intractability of the Computational Diffie-Hellman problem. The proposed scheme is as efficient as Lu et al.’s scheme.Due to its efficiency and certificateless, it can be widely used in areas such as E-cheque, etc.

[1] Mambo M, Usuda K, Okamoto E. Proxy signature: delegation of the power to sign messages[J]. IEICE Trans. Fundamentals,1996,E79-A(9):1338-1353.

[2] Mambo M, Usuda K, Okamoto E. Proxy signatures for delegating signing operation[C]//In Proc. 3rd ACM Conference on Computer and Communications Security-CCS’96. New York: ACM Press,1996:48-57.

[3] Sun Hungmin. An efficient nonrepudiable threshold proxy signatures with known signers[J]. Computer Communications,1999,22(8):717-722.

[4] Sun H, Lee N Y, Hwang T. Threshold proxy signatures[J]. IEE Proceedings-Computes and Digital Technique,1999,146:259-263.

[5] Hwang S J, Shi C H. A simple multi-proxy signature scheme[C]//In Proceedings of the Tenth National Conference on Information Security, Hualien:2000:134-138,.

[6] Yi Lijing, Bai Guoqiang, Xiao Guozheng. Proxy multi-signature scheme: a new type of proxy signature scheme[J]. Electroinics Letter,2000,36(6):527-528.

[7] Huang Xinyi, Mu Yi, Susilo W,etal.. Short designated verifier proxy signature from pairings[C]//In Proc. of the SecUbiq 2005, LNCS3823. Berlin: Springer-Verlag,2005:835-844.

[8] Zhang Fangguo, Kim K. Efficient ID-based blind signature and proxy signature from bilinear pairings[J]. Lecture Notes in Computer Science,2003,2727/2003:218-219.

[9] Kim H, Baek J, Lee B,etal. Secret computation with secrets for mobile agent using one-time proxy signature[C]//In Symp. on Cryptography and Information Security-SCIS 2000. New York: IEEE press,2001:845-850.

[10] Choi C, Kim Z, Kim K. Schnorr signature scheme with restricted signing capability and its application[C]//In Proc. Computer Security Symp-CSS’03. New York: ACM Press,2003:385-390.

[11] Al-Ibrahim M, Cerny A. Proxy and threshold one-time signatures[C]//In Applied Cryptography and Network Security-ACNS’03, LNCS 2846. Berlin: Springer-Verlag,2003:123-136.

[12] Wang H, Pieprzyk J. Efficient one-time proxy signaturesp[C]//In Advance of Cryptology-Asiacrypt’03, LNCS 2894. Berlin: Springer-Verlag,2003:507-522.

[13] Mehta M, Harn L. Efficient one-time proxy signatures[J]. IEE Proc Commun,2005,152(2):129-133.

[14] Lu Rongxing, Cao Zhenfu, Dong Xiaolei. Efficient ID-based one-time proxy signature and its application in E-Cheque[C]//The 5th International Conference on Cryptology and Network Security-CANS’06, LNCS 4301. Berlin: Springer-Verlag,2006:153-167.

[15] Bicakci K. One-time proxy signatures revisited[J]. Computer Standards & Interfaces,2007,29:499-505.

[16] Shamir A. Identity-based cryptosystems and signature schemes[C]//In Advances in Cryptology-Crypto’84, LNCS 196. Berlin: Springer-Verlag,1984:47-53.

[17] Al-Riyami S, Paterson K. Certificateless public key cryptography[C]//Advances in Cryptology- Asiacrypt’03, LNCS 2894. Berlin: Springer-Verlag,2003:452-473.

[18] Huang Xinyi, Susilo W, Mu Yi,etal. On the Security of Certificateless Signature Schemes from Asiacrypt 2003[C]//The 4th International Conference on Cryptology and Network Security-CANS’05, LNCS 3810. Berlin:Springer-Verlag,2005:13-25.

[19] Hu B C, Wong D S, Zhang Zhenfeng,etal. Key Replacement attack against a generic construction of certificateless signature[C]//The 11th Australasian Conference on Information Security and Privacy-ACISP 2006, LNCS 4058, Berlin: Springer-Verlag,2006:235-246.

[20] Zhang Zhenfeng, Wong D S, Xu Jing,etal. Certificateless public-key signature: security model and efficient construction[C]//The 4th International Conference on Applied Cryptography and Network Security-ACNS 2006,LNCS 3989. Berlin: Springer-Verlag,2006:293-308.

[21] Huang Xinyi, Mu Yi, Susilo W,etal. Certificateless signature Revisited[C]//The 12th Australasian Conference on Information Security and Privacy-ACISP 2007, LNCS 4586. Berlin: Springer-Verlag,2007:308-322.

[22] Lee B, Kim H, Kim K. Strong proxy signgture and its applications[C]//In Proceedings of SCIS 2001,2001:603-608.

[23] Chen Hui, Zhang Futai, Song Rushun. Certificateless proxy signature scheme with provable security[J]. Journal of Software,2009,20(3):692-701.