An efficient identity-based signature scheme with batch verifications

ABSTRACT

Mapping messages or a user's identity into a point on elliptic curves is required by many pairing-based cryptographic schemes. In most of pairing-based schemes, this requirement is realized by a special hash function, MapToPoint function. However, the efficiency of the MapToPoint function is much lower than the general hash functions. In this paper, we propose a new identity-based signature (IBS) scheme without MapToPoint function which speeds up extracting secret key and verifying the signatures. The security of the proposed scheme depends on a complex assumption similar to k-CAA. Furthermore, the proposed scheme also supports batch verifications such that multiple signatures on distinct messages for distinct users are verified simultaneously. The results show that batch verifications on the proposed IBS scheme is much faster than other IBS schemes.

REFERENCES

• 1: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 2: K. G. Paterson and G. Price, "A comparison between traditional PKIs and identity-based cryptography," Information Security Technical Report 8, 57--72, 2003.
• 3: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 4: D. Boneh, X. Boyen, "Efficient selective-ID secure identity based encryption without random oracles," Eurocrypt 2004, LNCS 3027, pp. 223--238, Springer-Verlag, 2004.
• 5: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 6: N. Smart, "A ID-based authenticated key agreement protocol based on the Weil pairings," Electron. Lett. 38(13), pp. 630--632, 2002.
• 7: L. Chen and C. Kudla, "Identity based authenticated key agreement from pairings," Cryptology ePrint Archive, Report 2002/184, 2002.
• 8: R. Sakai, K. Ohgishi and M. Kasahara. "Cryptosystems based on pairing," SCIS 2000, 2000.
• 9: K. G. Paterson, "ID-based signatures from pairings on elliptic curves," Cryptology ePrint Archive, Report 2002/003, 2002.
• 10: X. Chen, F. Zhang, K. Kim, "A new ID-based group signature scheme from bilinear pairings," WISA 2003, LNCS 2908, pp. 585--592, Springer-Verlag, 2003.
• 11: Florian Hess, Efficient Identity Based Signature Schemes Based on Pairings, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.310-324, August 15-16, 2002
• 12: Jae Choon Cha , Jung Hee Cheon, An Identity-Based Signature from Gap Diffie-Hellman Groups, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.18-30, January 06-08, 2003
• 13: X. Yi, "An identity-based signature scheme from the Weil pairing," IEEE Communications Letters 7(2), pp. 76--78, 2003.
• 14: H. Yoon, J. H. Cheon and Y. Kim, "Batch verifications with ID-based signatures," ICISC 2004, LNCS 3506, pp.223--248, Springer-Verlag, 2005.
• 15: Jari Arkko , Tuomas Aura , James Kempf , Vesa-Matti Mäntylä , Pekka Nikander , Michael Roe, Securing IPv6 neighbor and router discovery, Proceedings of the 3rd ACM workshop on Wireless security, p.77-86, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570690]
• 16: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 17: F. Zhang, R. Safavi-Naini and W. Susilo, "An efficient signature scheme from bilinear pairings and its applications," PKC 2004, LNCS 2947, pp.277--290, Springer-Verlag, 2004.
• 18: M. Bellare, J. Garay and T. Robin, "Fast batch verification for modular exponentiation and digital signatures,", Eurocrypt 1998, LNCS 1403, pp. 236--250, Springer-Verlag, 1998.
• 19: I. Blake , G. Seroussi , N. Smart , J. W. S. Cassels, Advances in Elliptic Curve Cryptography (London Mathematical Society Lecture Note Series), Cambridge University Press, New York, NY, 2005
• 20: S. Mitsunari, R. Sakai and M. Kasahara, "A new traitor tracing," IEICE Trans. Fundamentals, Vol. E85-A, No.2, pp.481--484, 2002.
• 21: F. Zhang, R. Safavi-Naini and W. Susilo, "ID-based Chameleon Hashes from Bilinear Pairings," Cryptology ePrint Archive, Report 2003/208, 2003.
• 22: Shamus Software Ltd. Miracl: Multiprecision integer and rational arithmetic C/C++ library. Avaible from http://indigo.ie/~mscott/.
• 23: N. Koblitz and A. Meneze, "Pairing-based cryptography at high security levels," Cryptography and Coding: 10th IMA International Conference, LNCS 3796, pp. 13--36, Springer-Verlag, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: User profiles and alert services

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Human Factors, Security