{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:34:29Z","timestamp":1750307669644,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>\n            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\n            <jats:italic>ordered multisignature<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/1410234.1410237","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["New Multiparty Signature Schemes for Network Routing Applications"],"prefix":"10.1145","volume":"12","author":[{"given":"Alexandra","family":"Boldyreva","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Craig","family":"Gentry","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"O'Neill","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dae Hyun","family":"Yum","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"<\/scp>","author":"Au M.-H.","year":"2007","unstructured":"<scp> Au , M.-H. , Susilo , W. , and Mu , Y . <\/scp> 2007 . Practical compact e-cash. Information Security and Privacy , 431--445. <scp>Au, M.-H., Susilo, W., and Mu, Y.<\/scp> 2007. Practical compact e-cash. Information Security and Privacy, 431--445."},{"key":"e_1_2_1_2_1","volume-title":"<\/scp>","author":"Bellare M.","year":"2007","unstructured":"<scp> Bellare , M. , Namprempre , C. , and Neven , G . <\/scp> 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. <scp>Bellare, M., Namprempre, C., and Neven, G.<\/scp> 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."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11967668_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_2_1_5_1","unstructured":"<scp>Bellovin S.<\/scp> 2006. Position paper: Workable routing security. WIRED.  <scp>Bellovin S.<\/scp> 2006. Position paper: Workable routing security. WIRED ."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/648120.747061"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315280"},{"volume-title":"Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04)","author":"Boneh D.","key":"e_1_2_1_8_1","unstructured":"<scp> Boneh , D. and Boyen , X . <\/scp> 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. <scp>Boneh, D. and Boyen, X.<\/scp> 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."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04)","volume":"3027","author":"Boneh D.","unstructured":"<scp> Boneh , D. and Boyen , X . <\/scp> 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. <scp>Boneh, D. and Boyen, X.<\/scp> 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."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO'01)","volume":"2139","author":"Boneh D.","unstructured":"<scp> Boneh , D. and Franklin , M. K . <\/scp> 2001. Identity-based encryption from the Weil pairing . In Proceedings of the Annual International Cryptology Conference (CRYPTO'01) . Lecture Notes in Computer Science , vol. 2139 . Springer, 213--229. <scp>Boneh, D. and Franklin, M. K.<\/scp> 2001. Identity-based encryption from the Weil pairing. In Proceedings of the Annual International Cryptology Conference (CRYPTO'01). Lecture Notes in Computer Science, vol. 2139. Springer, 213--229."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'03)","volume":"2656","author":"Boneh D.","unstructured":"<scp> Boneh , D. , Gentry , C. , Shacham , H. , and Lynn , B . <\/scp> 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 . <scp>Boneh, D., Gentry, C., Shacham, H., and Lynn, B.<\/scp> 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."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'01)","volume":"2248","author":"Boneh D.","unstructured":"<scp> Boneh , D. , Lynn , B. , and Shacham , H . <\/scp> 2001. Short signatures from the weil pairing . In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'01) . Lecture Notes in Computer Science , vol. 2248 . <scp>Boneh, D., Lynn, B., and Shacham, H.<\/scp> 2001. Short signatures from the weil pairing. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'01). Lecture Notes in Computer Science, vol. 2248."},{"volume-title":"Proceedings of the 3rd International Workshop on Practice and Theory in Public Key Cryptography (PKC'00)","author":"Burmester M.","key":"e_1_2_1_13_1","unstructured":"<scp> Burmester , M. , Desmedt , Y. , Doi , H. , Mambo , M. , Okamoto , E. , Tada , M. , and Yoshifuji , Y . <\/scp> 2000. A structured ElGamal-type multisignature scheme . In Proceedings of the 3rd International Workshop on Practice and Theory in Public Key Cryptography (PKC'00) . Springer, 466--483. <scp>Burmester, M., Desmedt, Y., Doi, H., Mambo, M., Okamoto, E., Tada, M., and Yoshifuji, Y.<\/scp> 2000. A structured ElGamal-type multisignature scheme. In Proceedings of the 3rd International Workshop on Practice and Theory in Public Key Cryptography (PKC'00). Springer, 466--483."},{"key":"e_1_2_1_14_1","volume-title":"<\/scp>","author":"Butler K.","year":"2005","unstructured":"<scp> Butler , K. , Farley , F. , McDaniel , P. , and Rexford , J . <\/scp> 2005 . A survey of BGP security. http:\/\/www.research.att.com\/jrex\/. <scp>Butler, K., Farley, F., McDaniel, P., and Rexford, J.<\/scp> 2005. A survey of BGP security. http:\/\/www.research.att.com\/jrex\/."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO'04)","volume":"3152","author":"Camenisch J.","unstructured":"<scp> Camenisch , J. and Lysyanskaya , A . <\/scp> 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. <scp>Camenisch, J. and Lysyanskaya, A.<\/scp> 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."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.704121"},{"volume-title":"Proceedings of the Conference on Communication, Control, and Computing (CCCM'94)","author":"Doi H.","key":"e_1_2_1_17_1","unstructured":"<scp> Doi , H. , Mambo , M. , Okamoto , E. <\/scp>, , <scp>and Uyematsu , T . <\/scp> 1994. Multisignature scheme with specified order . In Proceedings of the Conference on Communication, Control, and Computing (CCCM'94) . <scp>Doi, H., Mambo, M., Okamoto, E.<\/scp>, , <scp>and Uyematsu, T.<\/scp> 1994. Multisignature scheme with specified order. In Proceedings of the Conference on Communication, Control, and Computing (CCCM'94)."},{"volume-title":"Proceedings of the Symposium on Cryptography and Information Security (CIS'94)","author":"Doi H.","key":"e_1_2_1_18_1","unstructured":"<scp> Doi , H. , Mambo , M. , and Okamoto , E . <\/scp> 1994. Multisignature schemes for various group structures . In Proceedings of the Symposium on Cryptography and Information Security (CIS'94) . <scp>Doi, H., Mambo, M., and Okamoto, E.<\/scp> 1994. Multisignature schemes for various group structures. In Proceedings of the Symposium on Cryptography and Information Security (CIS'94)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11935230_12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11745853_17"},{"volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'02)","author":"Gentry C.","key":"e_1_2_1_21_1","unstructured":"<scp> Gentry , C. and Silverberg , A . <\/scp> 2002. Hierarchical ID-based cryptography . In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'02) . Springer, 548--566. <scp>Gentry, C. and Silverberg, A.<\/scp> 2002. Hierarchical ID-based cryptography. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'02). Springer, 548--566."},{"key":"e_1_2_1_22_1","volume-title":"<\/scp>","author":"Granger R.","year":"2006","unstructured":"<scp> Granger , R. and Smart , N . <\/scp> 2006 . On computing products of pairings. Cryptology ePrint Archive, Report 2006\/172. <scp>Granger, R. and Smart, N.<\/scp> 2006. On computing products of pairings. Cryptology ePrint Archive, Report 2006\/172."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxh153"},{"volume-title":"Proceedings of the Network and Distribution System Security Symposium (NDSS'00)","author":"Kent S. T.","key":"e_1_2_1_24_1","unstructured":"<scp> Kent , S. T. , Lynn , C. , Mikkelson , J. , and Seo , K . <\/scp> 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) . <scp>Kent, S. T., Lynn, C., Mikkelson, J., and Seo, K.<\/scp> 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)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_36"},{"key":"e_1_2_1_26_1","volume-title":"<\/scp>","author":"Lin C.-Y.","year":"2003","unstructured":"<scp> Lin , C.-Y. , Wu , T.-C. , and Zhang , F . <\/scp> 2003 . A structured multisignature scheme from the Gap Diffie-Hellman group. Cryptology ePrint Archive, Report 2003\/090. <scp>Lin, C.-Y., Wu, T.-C., and Zhang, F.<\/scp> 2003. A structured multisignature scheme from the Gap Diffie-Hellman group. Cryptology ePrint Archive, Report 2003\/090."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_28"},{"key":"e_1_2_1_28_1","unstructured":"<scp>Lynn B.<\/scp> The pairing-based crypto library. http:\/\/crypto.stanford.edu\/pbc.  <scp>Lynn B.<\/scp> The pairing-based crypto library. http:\/\/crypto.stanford.edu\/pbc."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04)","volume":"3027","author":"Lysyanskaya A.","unstructured":"<scp> Lysyanskaya , A. , Micali , S. , Reyzin , L. , and Shacham , H . <\/scp> 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. <scp>Lysyanskaya, A., Micali, S., Reyzin, L., and Shacham, H.<\/scp> 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."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ACM Symposium on Applied Computing (SAC'00)","volume":"1758","author":"Lysyanskaya A.","unstructured":"<scp> Lysyanskaya , A. , Rivest , R. L. , Sahai , A. , and Wolf , S . <\/scp> 2000. Pseudonym systems . In Proceedings of the ACM Symposium on Applied Computing (SAC'00) . Vol. 1758 . <scp>Lysyanskaya, A., Rivest, R. L., Sahai, A., and Wolf, S.<\/scp> 2000. Pseudonym systems. In Proceedings of the ACM Symposium on Applied Computing (SAC'00). Vol. 1758."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/646037.678151"},{"key":"e_1_2_1_32_1","volume-title":"<\/scp>","author":"Motiwala M.","year":"2006","unstructured":"<scp> Motiwala , M. and Feamster , N . <\/scp> 2006 . Position paper: Network troubleshooting on data plane coattails. WIRED. <scp>Motiwala, M. and Feamster, N.<\/scp> 2006. Position paper: Network troubleshooting on data plane coattails. WIRED."},{"volume-title":"Proceedings of the Conference on Database and Applications Security (DBSEC'06)","author":"Mykletun E.","key":"e_1_2_1_34_1","unstructured":"<scp> Mykletun , E. and Tsudik , G . <\/scp> 2006. Aggregation queries in the database-as-a-service model . In Proceedings of the Conference on Database and Applications Security (DBSEC'06) . <scp>Mykletun, E. and Tsudik, G.<\/scp> 2006. Aggregation queries in the database-as-a-service model. In Proceedings of the Conference on Database and Applications Security (DBSEC'06)."},{"key":"e_1_2_1_35_1","volume-title":"<\/scp>","author":"Feamster H. B.","year":"2004","unstructured":"<scp>N. Feamster , H. B. and Rexford , J . <\/scp> 2004 . Some foundational problems in interdomain routing. HotNets . <scp>N. Feamster, H. B. and Rexford, J.<\/scp> 2004. Some foundational problems in interdomain routing. HotNets."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788414.1788418"},{"key":"e_1_2_1_37_1","volume-title":"<\/scp>","author":"Saxena A.","year":"2005","unstructured":"<scp> Saxena , A. and Soh , B . <\/scp> 2005 . One-way signature chaining - a new paradigm for group cryptosystems. Cryptology ePrint Archive, Report 2005\/335. <scp>Saxena, A. and Soh, B.<\/scp> 2005. One-way signature chaining - a new paradigm for group cryptosystems. Cryptology ePrint Archive, Report 2005\/335."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO'84)","author":"Shamir A.","year":"1984","unstructured":"<scp> Shamir , A. <\/scp> 1984 . Identity-based cryptosystems and signature schemes . In Proceedings of the Annual International Cryptology Conference (CRYPTO'84) . Springer, 47--53. <scp>Shamir, A.<\/scp> 1984. Identity-based cryptosystems and signature schemes. In Proceedings of the Annual International Cryptology Conference (CRYPTO'84). Springer, 47--53."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1754542.1754568"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/646039.678316"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780656_9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102120.1102139"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1410234.1410237","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1410234.1410237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:36Z","timestamp":1750253376000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1410234.1410237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1410234.1410237"],"URL":"https:\/\/doi.org\/10.1145\/1410234.1410237","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2007-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}