Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing

ABSTRACT

We construct new multiparty signature schemes that allow multiple signers to sequentially produce a compact, fixed-length signature simultaneously attesting to the message(s) they want to sign. First, we introduce a new primitive that we call ordered multisignatures (OMS), which allow signers to attest to a common message as well as the order in which they signed. Our OMS construction substantially improves computational efficiency over any existing scheme with comparable functionality. Second, we design a new identity-based sequential aggregate signature scheme, where signers can attest to different messages and signature verification does not require knowledge of traditional public keys. The latter property permits savings on bandwidth and storage as compared to public-key solutions. In contrast to the only prior scheme to provide this functionality, ours offers improved security that does not rely on synchronized clocks or a trusted first signer. Security proofs according to the corresponding security definitions and under appropriate computational assumptions are provided for all the proposed schemes. We give several applications of our schemes to secure network routing, and we believe that they will find many other applications as well.

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: M.-H. Au, W. Susilo, and Y. Mu. Practical compact e-cash. Cryptology ePrint Archive, Report 2007/148, 2007. http://eprint.iacr.org/.
• 3: Mihir Bellare , Gregory Neven, Multi-signatures in the plain public-Key model and a general forking lemma, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180453]
• 4: M. Bellare and G. Neven. Identity-based multi-signatures from RSA. In CT-RSA, 2007.
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 6: John Bethencourt , Amit Sahai , Brent Waters, Ciphertext-Policy Attribute-Based Encryption, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.321-334, May 20-23, 2007 [doi>10.1109/SP.2007.11]
• 7: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 8: 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]
• 9: D. Boneh and X. Boyen. Efficient selective-ID secure identity-based encryption without random oracles. In EUROCRYPT, 2004.
• 10: D. Boneh and X. Boyen. Short signatures without random oracles. In EUROCRYPT, 2004.
• 11: D. Boneh, X. Boyen, and E.-J. Goh. Hierarchical identity based encryption with constant size ciphertext. In EUROCRYPT, 2005.
• 12: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In EUROCRYPT, 2003.
• 13: Mike Burmester , Yvo Desmedt , Hiroshi Doi , Masahiro Mambo , Eiji Okamoto , Mitsuru Tada , Yuko Yoshifuji, A Structured ElGamal-Type Multisignature Scheme, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.466-483, January 18-20, 2000
• 14: 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]
• 15: K. Butler, F. Farley, P. McDaniel, and J. Rexford. A survey of BGP security. Apr. 2005. http://www.research.att.com/jrex/.
• 16: J. Camenisch, S. Hohenberger, and M. Pedersen. Batch verification of short signatures. In EUROCRYPT, 2007.
• 17: J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO, 2004.
• 18: Haowen Chan , Debabrata Dash , Adrian Perrig , Hui Zhang, Modeling adoptability of secure BGP protocols, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
• 19: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 20: H. Doi, E. Okamoto, and M. Mambo. Multisignature schemes for various group structures. In Symposium on Cryptography and Information Security, 1994.
• 21: H. Doi, E. Okamoto, M. Mambo, and T. Uyematsu. Multisignature scheme with specified order. In Conference on Communication, Control, and Computing, 1999.
• 22: N. Feamster, H. Balakrishnan, and J. Rexford. Some foundational problems in interdomain routing. In HotNets, 2004.
• 23: D. Galindo, J. Herranz, and E. Kiltz. On the generic construction of identity-based signatures with additional properties. In ASIACRYPT, 2006.
• 24: C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In Public Key Cryptography, 2006.
• 25: 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
• 26: G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. Mcdanniel, and A. Rubin. Working around BGP: An incremental approach to improving security and accuracy in interdomain routing. In NDSS, 2003.
• 27: Javier Herranz, Deterministic Identity-Based Signatures for Partial Aggregation, The Computer Journal, v.49 n.3, p.322-330, May 2006 [doi>10.1093/comjnl/bxh153]
• 28: Yih-Chun Hu , Adrian Perrig , Marvin Sirbu, SPV: secure path vector routing for securing BGP, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 29: S. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure border gateway protocol (S-BGP) - Real world performance and deployment issues. In NDSS, 2000.
• 30: E. Kiltz, A. Mityagin, S. Panjwani, and B. Raghavan. Append-only signatures. In ICALP, 2005.
• 31: S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters. Sequential aggregate signatures and multisignatures without random oracles. In EUROCRYPT, 2006.
• 32: A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. In EUROCRYPT, 2004.
• 33: 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
• 34: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 35: Shirow Mitomi , Atsuko Miyaji, A Multisignature Scheme with Message Flexibility, Order Flexibility and Order Verifiability, Proceedings of the 5th Australasian Conference on Information Security and Privacy, p.298-312, July 10-12, 2000
• 36: M. Motiwala, A. Bavier, and N. Feamster. In-band network path diagnosis. Georgia Tech Technical Report GT-CS-07-07.
• 37: M. Motiwala and N. Feamster. Position paper: Network troubleshooting on data plane coattails. In WIRED, 2006.
• 38: E. Mykletun, M. Narasimha, and G. Tsudik. Signature bouquets: Immutability for aggregated/condensed signatures. In ESORICS, 2004.
• 39: A. Saxena and B. Soh. One-way signature chaining - a new paradigm for group cryptosystems. Cryptology ePrint Archive, Report 2005/335, 2005. http://eprint.iacr.org/.
• 40: V. Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, 1997.
• 41: K. Stange. The tate pairing via elliptic nets. In Pairing 2007, 2007.
• 42: Mitsuru Tada, An Order-Specified Multisignature Scheme Secure against Active Insider Attacks, Proceedings of the 7th Australian Conference on Information Security and Privacy, p.328-345, July 03-05, 2002
• 43: T. Wan, E. Kranakis, and P. van Oorschot. Pretty secure BGP, psBGP. In NDSS, 2005.
• 44: S. Xu and Y. and W. Susilo. Online/offline signatures and multisignatures for AODV and DSR routing security. In Australasian Conference on Information Security and Privacy, 2006.
• 45: Meiyuan Zhao , Sean W. Smith , David M. Nicol, Aggregated path authentication for efficient BGP security, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102139]

INDEX TERMS

Primary Classification:
  E. Data
  E.m MISCELLANEOUS

General Terms:
Algorithms, Design, Security, Theory