New Multiparty Signature Schemes for Network Routing Applications

ABSTRACT

We construct two new multiparty digital signature schemes that allow multiple signers to sequentially and non-interactively produce a compact, fixed-length signature. First, we introduce a new primitive that we call ordered multisignature (OMS) scheme, which allows signers to attest to a common message as well as the order in which they signed. Our OMS construction substantially improves computational efficiency and scalability over any existing scheme with suitable 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. We provide formal security definitions and support the proposed schemes with security proofs under appropriate computational assumptions. We focus on applications of our schemes to secure network routing, but we believe that they will find other applications as well.

REFERENCES

• 1: Au, M.-H., Susilo, W., and Mu, Y. 2007. Practical compact e-cash. Information Security and Privacy, 431--445.
• 2: Bellare, M., Namprempre, C., and Neven, G. 2007. Unrestricted aggregate signatures. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP'07). Lecture Notes in Computer Science, vol. 4596. Springer, 411--422.
• 3: Bellare, M. and Neven, G. 2007. Identity-based multi-signatures from RSA. In CT-RSA. LNCS, vol. 4377. Springer, 145--162.
• 4: 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]
• 5: Bellovin, S. 2006. Position paper: Workable routing security. WIRED.
• 6: 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
• 7: 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]
• 8: Boneh, D. and Boyen, X. 2004a. Efficient selective-ID secure identity-based encryption without random oracles. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04). Lecture Notes in Computer Science. Springer, 223--238.
• 9: Boneh, D. and Boyen, X. 2004b. Short signatures without random oracles. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04). Lecture Notes in Computer Science, vol. 3027. Springer, 56--73.
• 10: 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
• 11: Boneh, D., Gentry, C., Shacham, H., and Lynn, B. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'03). Lecture Notes in Computer Science, vol. 2656.
• 12: 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
• 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: Butler, K., Farley, F., McDaniel, P., and Rexford, J. 2005. A survey of BGP security. http://www.research.att.com/jrex/.
• 15: Camenisch, J. and Lysyanskaya, A. 2004. Signature schemes and anonymous credentials from bilinear maps. In Proceedings of the Annual International Cryptology Conference (CRYPTO'04). Lecture Notes in Computer Science, vol. 3152. Springer, 56--72.
• 16: 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
• 17: Doi, H., Mambo, M., Okamoto, E., , and Uyematsu, T. 1994. Multisignature scheme with specified order. In Proceedings of the Conference on Communication, Control, and Computing (CCCM'94).
• 18: Doi, H., Mambo, M., and Okamoto, E. 1994. Multisignature schemes for various group structures. In Proceedings of the Symposium on Cryptography and Information Security (CIS'94).
• 19: Galindo, D., Herranz, J., and Kiltz, E. 2006. On the generic construction of identity-based signatures with additional properties. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'06). Lecture Notes in Computer Science, vol. 4284. Springer, 178--193.
• 20: Gentry, C. and Ramzan, Z. 2006. Identity-based aggregate signatures. In Proceedings of the International Workshop on Practice and Theory in Public Key Cryptography (PKC'06). Lecture Notes in Computer Science, vol. 3958. Springer, 257--273.
• 21: 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
• 22: Granger, R. and Smart, N. 2006. On computing products of pairings. Cryptology ePrint Archive, Report 2006/172.
• 23: 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]
• 24: Kent, S. T., Lynn, C., Mikkelson, J., and Seo, K. 2000. Secure border gateway protocol (S-BGP) - real world performance and deployment issues. In Proceedings of the Network and Distribution System Security Symposium (NDSS'00).
• 25: Kiltz, E., Mityagin, A., Panjwani, S., and Raghavan, B. 2005. Append-only signatures. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP'05). Lecture Notes in Computer Science, vol. 3580. Springer, 434--445.
• 26: Lin, C.-Y., Wu, T.-C., and Zhang, F. 2003. A structured multisignature scheme from the Gap Diffie-Hellman group. Cryptology ePrint Archive, Report 2003/090.
• 27: Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., and Waters, B. 2006. Sequential aggregate signatures and multisignatures without random oracles. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06). Lecture Notes in Computer Science, vol. 4004. Springer, 465--485.
• 28: Lynn, B. The pairing-based crypto library. http://crypto.stanford.edu/pbc.
• 29: Lysyanskaya, A., Micali, S., Reyzin, L., and Shacham, H. 2004. Sequential aggregate signatures from trapdoor permutations. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04). Lecture Notes in Computer Science, vol. 3027. Springer, 74--90.
• 30: Lysyanskaya, A., Rivest, R. L., Sahai, A., and Wolf, S. 2000. Pseudonym systems. In Proceedings of the ACM Symposium on Applied Computing (SAC'00). Vol. 1758.
• 31: 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
• 32: Motiwala, M. and Feamster, N. 2006. Position paper: Network troubleshooting on data plane coattails. WIRED.
• 33: Motiwala, M., Bavier, A., and Feamster, N. 2007. In-band network path diagnosis. Georgia Tech Technical Report GT-CS-07-07 3.
• 34: Mykletun, E. and Tsudik, G. 2006. Aggregation queries in the database-as-a-service model. In Proceedings of the Conference on Database and Applications Security (DBSEC'06).
• 35: N. Feamster, H. B. and Rexford, J. 2004. Some foundational problems in interdomain routing. HotNets.
• 36: Neven, G. 2008. Efficient sequential aggregate signed data. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'08). Lecture Notes in Computer Science, vol. 4965. Springer, 52--69.
• 37: Saxena, A. and Soh, B. 2005. One-way signature chaining - a new paradigm for group cryptosystems. Cryptology ePrint Archive, Report 2005/335.
• 38: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 39: 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
• 40: Shoup, V. 1997. Lower bounds for discrete logarithms and related problems. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'97). Lecture Notes in Computer Science, vol. 1233. Springer, 256--266.
• 41: 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
• 42: Xu, S., Mu, Y., and Susilo, W. 2006. Online/offline signatures and multisignatures for AODV and DSR routing security. In Proceedings of the Australasian Conference on Information Security and Privacy (ACISP'06). LNCS, vol. 4058. Springer, 99--110.
• 43: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security

Keywords:
aggregate signatures, digital signatures, identity-based signatures, multisignatures, network security, pairings