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.

Key words： identity (ID)-based signature scheme; bilinear pairing; discrete-log problem; ROS problem; Diffie- Hellman problem

Acknowledgements

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

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