Certificate-based sequential aggregate signature

ABSTRACT

In this paper, we propose a new notion called Certificate-Based Sequential Aggregate Signature. Certificate-based cryptography proposed by Gentry [8] combines the merit of traditional public key cryptography and identity based cryptography, without use of the costly certificate chain verification process and the removal of key escrow security concern. Under this paradigm, we propose a first sequential aggregate signature. An aggregate signature scheme produces a short string that convinces any verifier that there are $n$ messages signed by $n$ parties, all of which may be distinct. The length of the string is a constant which is independent of $n$. Its compactness makes it particularly suitable to be employed in those environments where communication bandwidth is very limited, such as wireless network scenarios (e.g. MANETS, cellular networks, sensor networks, satellite communication). We provide a concrete construction of this new notion and prove its security in the random oracle model.

REFERENCES

• 1: S. S. Al-Riyami and K. Paterson. Certificateless public key cryptography. In ASIACRYPT '03, volume 2894 of LNCS, pages 452--473. Springer-Verlag, 2003.
• 2: Man Ho Au , Yi Mu , Jing Chen , Duncan S. Wong , Joseph K. Liu , Guomin Yang, Malicious KGC attacks in certificateless cryptography, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1266997]
• 3: M. Au, J. Liu, W. Susilo, and T. Yuen. Certificate based (linkable) ring signature. In ISPEC '07, volume 4464 of LNCS, pages 79--92. Springer-Verlag, 2007.
• 4: Alexandra Boldyreva , Craig Gentry , Adam O'Neill , Dae Hyun Yum, Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315280]
• 5: 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
• 6: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In CRYPTO 2003, volume 2656 of LNCS, pages 416--443, 2003.
• 7: 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
• 8: C. Gentry. Certificate-based encryption and the certificate revocation problem. In EUROCRYPT '03, pages 272--293. Springer-Verlag, 2003. LNCS No. 2656.
• 9: C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In PKC 2006, volume 3958 of LNCS, pages 257--273. Springer, 2006.
• 10: Y. Hwang, J. Liu, and S. Chow. Certificateless Public Key Encryption Secure against Malicious KGC Attacks in the Standard Model. Journal of Universal Computer Science, Special Issue on Cryptography in Computer System Security., 14(3):463--480, 2008.
• 11: B. G. Kang, J. H. Park, and S. G. Hahn. A certificate-based signature scheme. In CR--RSA '04, volume 2964 of LNCS, pages 99--111. Springer, 2004.
• 12: S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (secure-bgp). IEEE J. Selected Areas in Comm., 19(4):582--592, 2000.
• 13: J. Li, X. Huang, Y. Mu, W. Susilo, and Q. Wu. Certificate-based signature: Security model and efficient construction. In EuroPKI '07, volume 4582 of LNCS, pages 110--125. Springer, 2007.
• 14: Joseph K. Liu , Man Ho Au , Willy Susilo, Self-Generated-Certificate Public Key Cryptography and certificateless signature/encryption scheme in the standard model: extended abstract, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1266994]
• 15: Joseph K. Liu , Jianying Zhou, Efficient Certificate-Based Encryption in the Standard Model, Proceedings of the 6th international conference on Security and Cryptography for Networks, September 10-12, 2008, Amalfi, Italy [doi>10.1007/978-3-540-85855-3_10]
• 16: Joseph K. Liu , Joonsang Baek , Willy Susilo , Jianying Zhou, Certificate-Based Signature Schemes without Pairings or Random Oracles, Proceedings of the 11th international conference on Information Security, September 15-18, 2008, Taipei, Taiwan [doi>10.1007/978-3-540-85886-7_20]
• 17: S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters. Sequential aggregate signatures and multisignatures without random oracles. In EUROCRYPT '06, volume 4004 of LNCS, pages 465--485. Springer, 2006.
• 18: A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. In EUROCRYPT 2004, volume 3027 of LNCS, pages 514--532, 2004.
• 19: 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
• 20: F. Zhang, R. Safavi-Naini, and W. Susilo. An efficient signature scheme from bilinear pairings and its applications. In PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 277--290. Springer, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.0 GENERAL

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Security

Keywords:
cryptography, digital signature