ID-based signature schemes from bilinear pairing: A survey

Abstract

In identity (ID)-based cryptosystems, a user can use his/her identity as the public key, which simplifies the key management procedure compared to certificate-based cryptosystems. Authentication is a desired property in cryptographic protocols. The signature scheme provides this property. Notion of pairing reduces the computation overheads and makes the system simple and efficient. In this survey, we have tried to cover some ID-based signature schemes based on bilinear pairings with their protocol and security analysis to the best of our knowledge. We hope this survey will provide a ready reference to work in the related area.

Keywords

identity (ID)-based signature scheme / bilinear pairing / discrete-log problem / ROS problem / Diffie- Hellman problem

References

[1] Shamir A. Identity based cryptosystem and signature scheme. Advances in Cryptology, 1984, 196: 47-53

[2] Boneh D, Franklin M. Identity based encryption from the Weil pairing. Advances in Cryptology, 2001, 2139: 213-229

[3] Sakai R, Ohgishi K, Kasahara M. Cryptosystem based on pairings. In: Proceedings of 2000 Symposium on Cryptography and Information Security. 2000, 26-28

[4] Paterson K G. ID-based signatures from pairings on elliptic curves. IEEE Electronic Letters, 2002, 38(18): 1025-1026

[5] Hess F. Efficient identity based signature scheme based on pairings. Lecture Notes in Computer Science, 2003, 2595: 310-324

[6] Cha J C, Cheon J H. An identity based signature from gap Diffie-Hellman groups. Lecture Notes in Computer Science, 2003, 2567: 18-30

[7] Chaum D.Blind signatures for untraceable payments. Advances in Cryptology, 1983, 199-203

[8] Rivest R, Shamir A, Tauman Y. How to leak a secret. Lecture Notes in Computer Science, 2001, 2248: 552-565

[9] Zhang F, Kim K. ID-based blind signature and ring signature from pairings. Lecture Notes in Computer Science, 2002, 2501: 533-547

[10] Chaum D, van Heijst E. Group signatures. Lecture Notes in Computer Science, 1991, 547: 257-265

[11] Popescu C. An efficient ID-based group signature. Studia Universitatis Babes-Bolyai Informatica, 2002, 47(2): 29-38

[12] Desmedt Y. Society and group oriented cryptography: A new concept. Lecture Notes in Computer Science, 1987, 293: 120-127

[13] Baek J, Zheng Y. Identity based threshold signature scheme from the bilinear pairings. In: Proceedings of the International Conference on Information Technology: Coding and Computing. 2004, 124-128

[14] Mambo M, Usuda K, Okmamoto E. Proxy signatures: Delegation of the power to sign message. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1996, 79-A(9): 1338-1354

[15] Zhang F, Kim K. Efficient ID-based blind signature and proxy signature from bilinear pairings. In: Proceedings of the 8th Australasian Conference on Information Security and Privacy. 2003, 312-323

[16] Chaum D, Antwerpen H V. Undeniable signatures. Lecture Notes in Computer Science, 1990, 435: 212-216

[17] Han S, Yeung W K Y, Wang J. Identity-based confirmer signatures from pairings over elliptic curves. In: Proceedings of the 4th ACM Conference on Electronic Commerce. 2003, 262-263

[18] Jakobsson M, Sako K, Impagliazzo R. Designated verifier proofs and their applications. Lecture Notes in Computer Science, 1996, 1070: 143-154

[19] Saeednia S, Kramer S, Markovitch O. An efficient strong designated verifier signature scheme. In: Proceedings of the 6th International Conference on Information Security and Cryptology. 2003, 40-54

[20] Susilo W, Zhang F, Mu Y. Identity based strong designated verifier signature schemes. Lecture Notes in Computer Science, 2004, 3108: 313-324

[21] Huang X, Susilo W, Mu Y, Zhang F. Short (identity-based) strong designated verifier signature schemes. Lecture Notes in Computer Science, 2006, 3903: 214-225

[22] Dutta R, Barua R, Sarkar P. Pairing-based cryptographic protocols: A survey. Cryptology ePrint Archive. Report 2004/064, 2004. http://eprint.iacr.org/2004/064.pdf

[23] Libert B, Quisquater J. The exact security of an identity based signature and its application. Cryptology ePrint Archive. Report 2004/102, 2004. http://eprint.iacr.org/2004/102.ps

[24] Pointcheval D, Stern J. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2003, 13(3): 361-396

[25] Pointcheval D, Stern J. Security proofs for signature schemes. Lecture Notes in Computer Science, 1996, 1992: 387-398

[26] Yi X. An identity based signature scheme from the Weil pairing. IEEE Communications Letters, 2003, 7(2): 76-78

[27] Guillou L C, Quisquater J J. A paradoxial identity-based signature scheme resulting from zero knowledge. In: Proceedings of Crypto 1988. 1988, 216-231

[28] Xie Y, Zhang F, Chen X, Kim K. ID-based distributed magic ink signature from pairings. Lecture Notes in Computer Science, 2003, 2836: 249-259

[29] Jakobson M, Yung M. Distributed magic ink signatures. Lecture Notes in Computer Science, 1997, 1233: 450-464

[30] Schnorr C P. Security of blind discrete log signatures against interactive attacks. Lecture Notes in Computer Science, 2001, 2229: 1-12.

[31] Dong Z, Zheng H, Chen K F. ID-based proxy blind signature. In: Proceedings of the 18th International Conference on Advanced Information Networking and Application. 2004, 380-383

[32] Huang Z, Chen K, Wang Y. Efficient identity-based signature and blind signatures. Lecture Notes in Computer Science, 2005, 3810: 120-133

[33] Han S, Chang E. A pairing-based blind signature scheme with message recovery. In: Proceedings of the sixth International Enformatika Conference. 2005, 303-308

[34] Boldyreva A. Efficient threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme. Lecture Notes in Computer Science, 2003, 2567: 31-46

[35] Chow S S M, Hui L C K, Yiu S M, Chow K P. Two improved partially blind signature schemes from bilinear pairings. Lecture Notes in Computer Science, 2005, 3574: 316-328

[36] Hu X, Huang S. An efficient ID-based partially blind signature scheme. In: Proceedings of the Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. 2007, 291-296

[37] Tseng Y M, Wu T Y,Wu J D. Forgery attacks on an ID-based partially blind signature scheme. IAENG International Journal of Computer Science, 2008, 35(3): 301-304

[38] Tian X X, Li H J, Xu J P, Wang Y. A security enforcement ID-based partially blind signature scheme. In: Proceedings of International Conference on Web Information Systems and Mining. 2009, 488-492

[39] Chen X, Zhang F, Liu S. ID-based restrictive partially blind signatures and application. Journal of Systems and Software, 2007, 80(2): 164-171

[40] Brands S. Untraceable off-line cash in wallet with observers. Lecture Notes in Computer Science, 1993, 773: 302-318

[41] Brands S. An efficient off-line electronic cash system based on the representation problem. Technical Report CS-R 9323, 1993

[42] Gao W, Wang G, Wang X, Li F. One round ID-based blind signature scheme without-ROS assumption. Lecture Notes in Computer Science, 2008, 5209: 316-331

[43] Chow S S M, Lui W C, Hui L C K, Yui S M. Identity-based ring signature: Why, how and what next. Lecture Notes in Computer Science, 2005, 3545: 144-161

[44] Abe M, Ohkubo M, Suzuki K. 1-out-of-n signatures from a variety of keys. Lecture Notes in Computer Science, 2002, 2501: 415-432

[45] Lin C, Wu T C. An identity based ring signature scheme from bilinear pairings. Cryptology ePrint Archive. Report 2003/117, 2003http://eprint.iacr.org/2003/117.pdf

[46] Herranz J, Saez G. New identity-based ring signature schemes. Lecture Notes in Computer Science, 2004, 3269: 27-39

[47] Awasthi A K, Lal S.ID-based ring signature and proxy ring signature schemes from bilinear pairings. Cryptology ePrint Archive. Report 2004/184, 2004. http://eprint.iacr.org/2004/184.pdf

[48] Chow S S M, Hui L C K, Yiu S M. Identity-based threshold ring signature. Lecture Notes in Computer Science, 2004, 3506: 218-232

[49] Chow S S M, Yiu S M, Hui L C K. Efficient identity based ring signature. Lecture Notes in Computer Science, 2005, 3531: 499-512

[50] Au M H, Liu J K, Yuen T H, Wong D S. ID-based ring signature scheme secure in the standard model. Lecture Notes in Computer Science, 2006, 4266: 1-16

[51] Zhang J. An efficient identity based ring signature and its extension. Lecture Notes in Computer Science, 2007, 4706: 63-74

[52] Wang L, Zhang G, Ma C. A survey of ring signature. Frontiers of Electrical and Electronic Engineering in China, 2008, 3(1): 10-19

[53] Han S, Wang J, Liu W. An efficient identity-based group signature scheme over elliptic curves. Lecture Notes in Computer Science, 2004, 3262: 417-429

[54] Lauter K.The advantages of elliptic curve cryptography for wireless security. IEEE Wireless Communications, 2004, 11(1): 62-67

[55] Chen X, Zhang F, Kim K.A new ID-based group signature scheme from bilinear pairings. Journal of Electronics, 2006, 23(6): 892-900

[56] Tan Z W, Liu Z J.A novel identity-based group signature scheme from bilinear maps. MM Research Preprint, MMRC, AMSS, Academia, Sinica, 2003, 22: 250-255

[57] Boyen X, Waters B. Compact group signatures without random oracles. Lecture Notes in Computer Science, 2006, 4004: 427-444

[58] Waters B. Efficient identity based encryption without random oracles. Lecture Notes in Computer Science, 2005, 3494:. 114-127

[59] Groth J, Ostrovsky R, Sahai A. Perfect non-interactive zero knowledge for NP. Cryptology ePrint Archive. Report 2005/290, 2005. http://eprint.iacr.org/2005/290.ps.gz

[60] Boyen X, Waters B. Full-domain subgroup hiding and constant-size group signatures. Lecture Notes in Computer Science, 2007, 4450: 1-15

[61] Ibraimi L, Nikova S. Hartel P, Jonker W. An identity-based group signature with membership revocation in the standard model. Enschede: University of Twente, 2010. http://purl.org/utwente/72270.

[62] Gennaro R, Jarecki S, Krawczyk H, Rabin T. Robust threshold DSS signature. Lecture Notes in Computer Science, 1996, 1070: 354-371

[63] Chen X, Zhang F, Konidala D M, Kim K. New ID-based threshold signature scheme from bilinear pairings. Lecture Notes in Computer Science, 2004, 3348: 371-383

[64] Cheng X, Liu J, Wang X. An identity based signature and its threshold version. In: Proceedings of the 19th International Conference on Advanced Information Networking and Applications. 2005, 1: 973-977

[65] Yu Y, Yang B, Sun Y. Identity-based threshold signature and mediated proxy signature. Journal of China Universities of Posts and Telecommunications, 2007, 14(2): 69-74

[66] Zhou H, Li X, Yang J. A secure identity-based threshold signature scheme from Tate pairings. In: Proceedings of International Conference on Advanced Infocomm technology. 2008

[67] Lu D, Zhang B, Zhao H, Wang Y, Li X. ID-based threshold proxy signature scheme from bilinear pairings. In: Proceedings of International Conference on Management and Service Science. 2009, 1-4

[68] Lu D J, Zhang B R, Wang Y, Li X.A efficient (t,n) threshold proxy signature scheme based on elliptic curve cryptosystems. In: Proceedings of the 4th International Conference on Wireless Communications, Networking and Mobile. 2008, 1-5

[69] Kim S, Park S, Won D. Proxy signatures, revisited. Lecture Notes in Computer Science, 1997, 1334: 223-232

[70] Lee B, Kim H, Kim K. Strong proxy signature and its applications. In: Proceedings of the 2001 Symposium on Cryptography and Information Security. 2001, 603-608

[71] Xu J, Zhang Z, Feng D. ID-based proxy signature using bilinear pairings. Lecture Notes in Computer Science, 2005, 3759: 359-367

[72] Li X, Chen K. ID-based multi-proxy signature, proxy multi-signature and multi-proxy multi-signature scheme from bilinear pairings. Applied Mathematics and Computation, 2005, 169(1): 1429-1435

[73] Zhang Q, Wen Q, Chen G. Efficient ID-based proxy blind signature scheme. Wuhan University Journal of Natural Sciences, 2007, 12(1): 105-108

[74] Wang Q, Cao Z. Identity-based proxy multi-signature. Journal of Systems and Software, 2007, 80(7): 1023-1029

[75] Gentry C, Ramzan Z. Identity-based aggregate signatures. Lecture Notes in Computer Science, 2006, 3958: 257-273

[76] Shao Z. Improvement of identity-based proxy multi-signature scheme. Journal of Systems and Software, 2009, 82(5): 794-800

[77] Cao F, Cao Z. A secure identity based multi-proxy signature scheme. Computers & Electrical Engineering, 2009, 35(1): 86-95

[78] Cao F, Cao Z. A secure identity-based proxy multi-signature scheme. Information Sciences, 2009, 179(3): 292-302

[79] Boldyreva A, Palacio A, Warinschi B.Secure proxy signature schemes for delegation of signing rights. Cryptology ePrint Archive. Report 2003/096/, 2003. http://eprint.iacr.org/2003/096.pdf

[80] Wang Q, Cao Z.Security arguments for partial delegation with warrant proxy signature schemes. Cryptology ePrint Archive. Report 2004/315/, 2004. http://eprint.iacr.org/2004/315.pdf

[81] Wang Q, Cao Z, Wang S. Formalized security model of multi-proxy signature schemes. In: Proceedings of the Fifth International Conference on Computer and Information Technology. 2005, 668-672

[82] Zhang F, Safavi-Naini R, Susilo W. Attack on Han et al.’s ID-based confirmer (undeniable) signature. In: Proceedings of the 4th ACM Conference on Electronic Commerce. 2003, 262-263

[83] Chow S S M, Hui L C K, Yiu S M, Chow K P. A secure modified ID-based undeniable signature scheme. Cryptography ePrint Archive. Report 2003/262, 2003. http://eprint.iacr.org/2003/262.pdf.

[84] Libert B, Quisquater J. ID-based undeniable signatures. Lecture Notes in Computer Science, 2004, 2694: 112-125

[85] Galbraith S, Mao W. Invisibility and anonymity of undeniable and confirmer signatures. Lecture Notes in Computer Science, 2003, 2612: 80-97

[86] Guo X Y, Tang C J. Identity based group oriented undeniable signature scheme. Applied Mathematics and Computation, 2005, 169(2): 1448-1457

[87] Wu W, Mu Y, Susilo W, Huang X. Provably secure identity-based undeniable signatures with selective and universal convertibility. Lecture Notes in Computer Science, 2008, 4990: 25-39

[88] Chow S M. Verifiable pairing and its applications. Lecture Notes in Computer Science, 2005, 3325: 170-187

[89] Galindo D, Herranz J, Kiltz E. On the generic construction of identity-based signatures with additional properties. Lecture Notes in Computer Science, 2006, 4284: 178-193

[90] Guo X Y, Tang C J. Identity based designated multiconfirmer signature: A new type signature. Applied Mathematics and Computation, 2005, 169(2): 1076-1085

[91] Zhang F, Susilo W, Mu Y, Chen X. Identity-based universal designated verifier signatures. Lecture Notes in Computer Science, 2005, 3823: 825-834

[92] Seo S H, Hwang J Y, Choi K Y, Lee D H. Identity based universal designated multi-confirmer signatures scheme. Computer Standards & Interfaces, 2008, 30(5): 288-295

[93] Garay J, MacKenzie P, Yang K. Strengthening zero-knowledge protocols using signatures. Lecture Notes in Computer Science, 2003, 2656: 177-194

[94] Zhang J, Mao J. A novel ID-based designated verifier signature scheme. Information Sciences, 2008, 178(3): 766-773

[95] Lipmma H, Wang G, Bao F. Designated verifier signature scheme: attacks, new security notions and new construction. Lecture Notes in Computer Science, 2005, 3580: 459-471

[96] Kumar K, Shailja G, Saxena A. Identity-based strong designated verifier signature scheme. Cryptography ePrint Archive. Report 2006/134, 2006. http://eprint.iacr.org/2006/134.pdf

[97] Kang B, Boyd C, Dawson E. Dawson identity-based strong designated verifier signature schemes: Attacks and new construction. Computers & Electrical Engineering, 2009, 35(1): 49-53

[98] Lal S, Verma V. Identity-based strong designated verifier proxy signature schemes. Cryptography ePrint Archive. Report 2006/394, 2006. http://eprint.iacr.org/2006/394.pdf

[99] Kang B, Boyd C,Dawson E. A novel identity-based strong designated verifier signature scheme. Journal of Systems and Software, 2009, 82(2): 270-273

[100] Paterson K G, Schuldt J C N. Efficient identity based signature secure in the standard model. Lecture Notes in Computer Science, 2006, 4058: 207-222

[101] Cao F, Cao Z. Identity-based universal designated verifier signature schemes secure in the standard model. Journal of Systems and Software, 2009, 82(4): 643-649

Acknowledgements

The authors are thankful to the anonymous referees for the suggestions that improved the presentation of the material in this article.

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg