An Identity-Based Signature from Gap Diffie-Hellman Groups

  • Jae Cha Choon
  • Jung Hee Cheon
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


In this paper we propose an identity(ID)-based signature scheme using gap Diffie-Hellman (GDH) groups. Our scheme is proved secure against existential forgery on adaptively chosen message and ID attack under the random oracle model. Using GDH groups obtained from bilinear pairings, as a special case of our scheme, we obtain an ID-based signature scheme that shares the same system parameters with the IDbased encryption scheme (BF-IBE) by Boneh and Franklin [BF01], and is as efficient as the BF-IBE. Combining our signature scheme with the BF-IBE yields a complete solution of an ID-based public key system. It can be an alternative for certificate-based public key infrastructures, especially when efficient key management and moderate security are required.


ID-based signature GDH group Elliptic curve Weil pairing 


  1. [BF01]
    D. Boneh and M. Franklin, Identity Based Encryption from the Weil Pairing, Proc. of Crypto’ 01, Lecture Notes in Computer Science, Vol. 2139, pp. 213–229, Springer-Verlag, 2001. (A full version is available from dabo/pubs.html) 18, 19, 21, 22, 26, 27, 28, 29Google Scholar
  2. [BK02]
    P. Barreto and H. Kim, Fast Hashing onto Elliptic Curves over Fields of Characteristic 3, Available from, 2002.
  3. [BKS02]
    P. Barreto, H. Kim, and M. Scott, Efficient Algorithms for Pairing-based Cryptosystems, Available from, 2002. 28
  4. [BLS01]
    D. Boneh, B. Lynn, and H. Shacham, Short Signatures from the Weil Pairing, Proc. of Asiacrypt’ 01, Lecture Notes in Computer Sciences, Vol. 2248, pp. 514–532, Springer-Verlag, 2001. 20, 26, 27, 28Google Scholar
  5. [CC01]
    J. Cheon and J. Cha, Identity-based Signatures from the Weil Pairing, Available from jhcheon/publications.html, 2001. 19
  6. [DQ86]
    Y. Desmedt and J. Quisquater, Public-key Systems based on the Difficulty of Tampering, Proc. of Crypto’ 86, Lecture Notes in Computer Sciences, Vol. 263, pp. 111–117, Springer-Verlag, 1987. 18Google Scholar
  7. [FFS88]
    U. Feige, A. Fiat, and A. Shamir, Zero-knowledge proofs of identity, J. Cryptology, Vol. 1, pp. 77–94, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  8. [FS86]
    A. Fiat and A. Shamir, How to prove youself: Practical solutions to identi fication and signature problems, Proc. of Crypto’ 86, Lecture Notes in Computer Sciences, Vol. 263, pp. 186–194, Springer-Verlag, 1987.Google Scholar
  9. [Hes02]
    F. Hess, Exponent group signature schemes and efficient identity based signature schemes based on pairings, Available from, 2002. 19
  10. [Gal01]
    S. Galbraith, Supersingular curves in cryptography, Proc. of Asiacrypt’ 01, Lecture Nores in Computer Sciences, Vol. 2248, pp. 495–513, Springer-Verlag, 2001. 26, 27Google Scholar
  11. [Men93]
    A. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993. 26Google Scholar
  12. [MY91]
    U. Maurer and Y. Yacobi, Non-interective public-key cryptography, Proc. of Eurocrypto’ 91, Lecture Nores in Computer Sciences, Vol. 547, pp. 498–507, Springer-Verlag, 1992. 18Google Scholar
  13. [OP01]
    T. Okamoto and D. Pointcheval, The gap-problems: a new class of problems for the security of cryptographic Schemes, Proc. of PKC’ 01, Lecture Nores in Computer Sciences, Vol. 1992, pp. 104–118, Springer-Verlag, 2001. 20Google Scholar
  14. [Pat02]
    K. Paterson, ID-based signatures from pairings on elliptic curves, Available from, 2002. 19
  15. [PS96]
    D. Pointcheval and J. Stern, Security proofs for signature schemes, Proc. of Eurocrypt’ 96, Lecture Notes in Computer Sciences, Vol. 1070, pp. 387–398, Springer-Verlag, 1996. 25Google Scholar
  16. [PS00]
    D. Pointcheval and J. Stern, Security arguments for digital signatures and blind signatures, J. of Cryptology, Vol. 13, pp. 361–396, 2000. 23, 25, 26zbMATHCrossRefGoogle Scholar
  17. [Sha84]
    A. Shamir, Identity-base cryptosystems and signature schemes, Proc. of Crypto’ 84, Lecture Notes in Computer Science, Vol. 196, pp. 47–53, Springer-Verlag, 1985. 18, 19, 29Google Scholar
  18. [SOK01]
    R. Sakai, K. Ohgishi, and M. Kasahara, Cryptosystems based on pairing, Proc. of SCIS’ 00, Okinawa, Japan, Jan. pp. 26–28, 2001. 18Google Scholar
  19. [Tan87]
    H. Tanaka, A realization scheme for the identity-based cryptosystem, Proc. of Crypto’ 87, Lecture Nores in Computer Sciences, Vol. 293, pp. 341–349, Springer-Verlag, 1987. 18Google Scholar
  20. [TI89]
    S. Tsuji and T. Itoh, An ID-based cryptosystem based on the discrete logarithm problem, IEEE Journal of Selected Areas in Communications, Vol. 7, No. 4, pp. 467–473, 1989. 18CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Jae Cha Choon
    • 1
  • Jung Hee Cheon
    • 2
  1. 1.Department of MathematicsKorea Advanced Institute of Science and TechnologyTaejonKorea
  2. 2.Information and Communications University (ICU)TaejonKorea

Personalised recommendations