Universal forgery of the identity-based sequential aggregate signature scheme

ABSTRACT

At CCS'07, a novel identity-based sequential aggregate signature scheme was proposed and the security of the scheme was proven under the hardness assumption of a new computational problem called modified LRSW problem. In the paper, unfortunately, we show that the scheme is universally forgeable, i.e., anyone can generate forged signatures on any messages of its choice. In addition, we show that the computational assumption is not correct by concretely presenting a constant-time algorithm solving the problem. The contribution of the new scheme and assumption is a natural step in cryptologic research that calls for further investigation, which is a step we perform in the current work.

REFERENCES

• 1: William Aiello , John Ioannidis , Patrick McDaniel, Origin authentication in interdomain routing, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948133]
• 2: 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]
• 3: Alexandra Boldyreva , Craig Gentry , Adam O'Neill , Dae Hyun Yum, New Multiparty Signature Schemes for Network Routing Applications, ACM Transactions on Information and System Security (TISSEC), v.12 n.1, p.1-39, October 2008 [doi>10.1145/1410234.1410237]
• 4: D. Boneh and X. Boyen. Short signatures without random oracles. In Proc. Eurocrypt 2004, volume 3027 of LNCS, pages 56--73. Springer, 2004.
• 5: D. Boneh, X. Boyen, and E. Goh. Hierarchical identity based encryption with constant size ciphertext. In Proc. Eurocrypt 2005, volume 3494 of LNCS, pages 440--456. Springer, 2005.
• 6: D. Boneh, C. Gentry, B. Lynn, and M. Franklin. Aggregate and verifiably encrypted signatures from bilinear maps. In Proc. Eurocrypt 2003, volume 2656 of LNCS, pages 416--432. Springer, 2003.
• 7: Kevin Butler , Patrick McDaniel , William Aiello, Optimizing BGP security by exploiting path stability, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180442]
• 8: C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In Proc. PKC 2006, volume 3958 of LNCS, pages 257--273. Springer, 2006.
• 9: S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (secure-bgp). IEEE Journal on Selected Areas in Communications, 18(4):582--592, 2000.
• 10: Anna Lysyanskaya , Ronald L. Rivest , Amit Sahai , Stefan Wolf, Pseudonym Systems, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.184-199, August 09-10, 1999
• 11: A. Lysyanskya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. In Proc. Eurocrypt 2004, volume 3027 of LNCS, pages 74--90. Springer, 2004.
• 12: A. Lysyanskya, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters. Sequential aggregate signatures and multisignatures without random oracles. In Proc. Eurocrypt 2006, volume 4004 of LNCS, pages 465--485. Springer, 2006.
• 13: 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
• 14: V. Shoup. Lower bounds for discrete logarithms and related problems. In Proc. Eurocrypt 1997, volume 1592 of LNCS, pages 256--266. Springer, 1997.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
identity-based cryptography, sequential aggregate signature, universal forgery