{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:12Z","timestamp":1750308792954,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000105","name":"Office of Cyberinfrastructure","doi-asserted-by":"publisher","award":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"],"award-info":[{"award-number":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"]}],"id":[{"id":"10.13039\/100000105","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"],"award-info":[{"award-number":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"],"award-info":[{"award-number":["CCR-0311510IIS-0324846IIS-0713403OCI-0724806"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>We consider the problem of authenticating a stream of packets transmitted over a network controlled by an adversary who may perform arbitrary attacks on the stream: He may drop or modify chosen packets, rearrange the order of the packets in any way, and inject new, random, or specially crafted packets into the stream. In contrast, prior work on the multicast authentication problem has focused on a less powerful adversarial network model or has examined a considerably more restrictive setting with specific timing or structural assumptions about the network.<\/jats:p>\n          <jats:p>\n            We model the ability of the network to modify a stream of\n            <jats:italic>n<\/jats:italic>\n            packets with two parameters: the\n            <jats:italic>survival rate<\/jats:italic>\n            \u03b1 (0 &lt;\u03b1\u2264 1) denoting the fraction of the packets that are guaranteed to reach any particular receiver unmodified and the\n            <jats:italic>flood rate<\/jats:italic>\n            \u03b2 (\u03b2 \u2265 1) indicating the factor by which the size of the received stream at any particular receiver may exceed the size of the transmitted stream. Combining error-correcting codes with standard cryptographic primitives, our approach gives almost the same security guarantees as if each packet were individually signed, but requires only one signature operation for the entire stream and adds to each transmitted packet only a small amount of authentication information, proportional to \u03b2\/\u03b1\n            <jats:sup>2<\/jats:sup>\n            . We prove the security and correctness of our scheme and analyze its performance in terms of communication overhead and computational effort at the sender and the receiver. Our results demonstrate how list decoding can be transformed into unambiguous decoding in the public-key model and the bounded computational model for the underlying communication channel. Overall, our technique provides an authenticated error-correcting code of independent interest that may be useful in other settings.\n          <\/jats:p>","DOI":"10.1145\/1698750.1698757","type":"journal-article","created":{"date-parts":[[2010,3,9]],"date-time":"2010-03-09T16:34:59Z","timestamp":1268152499000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Authenticated error-correcting codes with applications to multicast authentication"],"prefix":"10.1145","volume":"13","author":[{"given":"Anna","family":"Lysyanskaya","sequence":"first","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Triandopoulos","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,3,5]]},"reference":[{"volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'01)","author":"Boneh D.","key":"e_1_2_1_1_1","unstructured":"Boneh , D. , Durfee , G. , and Franklin , M . 2001. Lower bounds for multicast message authentication . In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'01) . Springer, Berlin, 437--452. Boneh, D., Durfee, G., and Franklin, M. 2001. Lower bounds for multicast message authentication. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'01). Springer, Berlin, 437--452."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398521"},{"volume-title":"Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security(ASIACRYPT'01)","author":"Boneh D.","key":"e_1_2_1_3_1","unstructured":"Boneh , D. , Lynn , B. , and Shacham , H . 2001. Short signatures from the Weil pairing . In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security(ASIACRYPT'01) . Springer, Berlin, 514--532. Boneh, D., Lynn, B., and Shacham, H. 2001. Short signatures from the Weil pairing. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security(ASIACRYPT'01). Springer, Berlin, 514--532."},{"volume-title":"Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM'99)","author":"Canetti R.","key":"e_1_2_1_4_1","unstructured":"Canetti , R. , Garay , J. , Itkis , G. , Micciancio , D. , Naor , M. , and Pinkas , B . 1999. Multicast security: A taxonomy and some efficient constructions . In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM'99) . IEEE, Los Alamitos, CA, 708--716. Canetti, R., Garay, J., Itkis, G., Micciancio, D., Naor, M., and Pinkas, B. 1999. Multicast security: A taxonomy and some efficient constructions. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM'99). IEEE, Los Alamitos, CA, 708--716."},{"key":"e_1_2_1_5_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/357830.357847"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM'92)","author":"Desmedt Y.","year":"2045","unstructured":"Desmedt , Y. , Frankel , Y. , and Yung , M . 1992. Multi-receiver\/multi-sender network security: Efficient authenticated multicast\/feedback . In Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM'92) . IEEE, Los Alamitos, CA , 2045 --2054. Desmedt, Y., Frankel, Y., and Yung, M. 1992. Multi-receiver\/multi-sender network security: Efficient authenticated multicast\/feedback. In Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM'92). IEEE, Los Alamitos, CA, 2045--2054."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/648120.746930"},{"volume-title":"Proceedings of the 17th Annual International Cryptology Conference (CRYPTO'97)","author":"Gennaro R.","key":"e_1_2_1_9_1","unstructured":"Gennaro , R. and Rohatgi , P . 1997. How to sign digital streams . In Proceedings of the 17th Annual International Cryptology Conference (CRYPTO'97) . Springer, Berlin, 180--197. Gennaro, R. and Rohatgi, P. 1997. How to sign digital streams. In Proceedings of the 17th Annual International Cryptology Conference (CRYPTO'97). Springer, Berlin, 180--197."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.23"},{"volume-title":"Foundations of Cryptography, vol II","author":"Goldreich O.","key":"e_1_2_1_11_1","unstructured":"Goldreich , O. 2004. Foundations of Cryptography, vol II . Cambridge University Press , Cambridge, MA . Goldreich, O. 2004. Foundations of Cryptography, vol II. Cambridge University Press, Cambridge, MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198344540"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"volume-title":"Proceedings of the Network and Distributed System Security Symposium. Internet Society","author":"Golle P.","key":"e_1_2_1_14_1","unstructured":"Golle , P. and Modadugu , N . 2001. Authenticating streamed data in the presence of random packet loss . In Proceedings of the Network and Distributed System Security Symposium. Internet Society , Reston, VA, 13--22. Golle, P. and Modadugu, N. 2001. Authenticating streamed data in the presence of random packet loss. In Proceedings of the Network and Distributed System Security Symposium. Internet Society, Reston, VA, 13--22."},{"volume-title":"Proceedings of the Network and Distributed System Security Symposium. Internet Society","author":"Gunter C.","key":"e_1_2_1_15_1","unstructured":"Gunter , C. , Khanna , S. , Tan , K. , and Venkatesh , S . 2004. DoS protection for reliably authenticated broadcast . In Proceedings of the Network and Distributed System Security Symposium. Internet Society , Reston, VA, 17--36. Gunter, C., Khanna, S., Tan, K., and Venkatesh, S. 2004. DoS protection for reliably authenticated broadcast. In Proceedings of the Network and Distributed System Security Symposium. Internet Society, Reston, VA, 17--36."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"volume-title":"Proceedings of the Network and Distributed System Security Symposium. Internet Society","author":"Karlof C.","key":"e_1_2_1_18_1","unstructured":"Karlof , C. , Sastry , N. , Li , Y. , Perrig , A. , and Tygar , J . 2004. Distillation codes &amp; applications to DoS resistant multicast authentication . In Proceedings of the Network and Distributed System Security Symposium. Internet Society , Reston, VA, 37--56. Karlof, C., Sastry, N., Li, Y., Perrig, A., and Tygar, J. 2004. Distillation codes &amp; applications to DoS resistant multicast authentication. In Proceedings of the Network and Distributed System Security Symposium. Internet Society, Reston, VA, 37--56."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/164051.164075"},{"volume-title":"Proceedings of the Symposium on Security &amp;  Privacy. IEEE","author":"Krohn M.","key":"e_1_2_1_20_1","unstructured":"Krohn , M. , Freedman , M. , and Mazieres , D . 2004. On-the-fly verification of rateless erasure codes for efficient content distribution . In Proceedings of the Symposium on Security &amp; Privacy. IEEE , Los Alamitos, CA, 226--240. Krohn, M., Freedman, M., and Mazieres, D. 2004. On-the-fly verification of rateless erasure codes for efficient content distribution. In Proceedings of the Symposium on Security &amp; Privacy. IEEE, Los Alamitos, CA, 226--240."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"volume-title":"Proceedings of the Symposium on Security &amp;  Privacy. IEEE","author":"Lysyanskaya A.","key":"e_1_2_1_22_1","unstructured":"Lysyanskaya , A. , Tamassia , R. , and Triandopoulos , N . 2004. Multicast authentication in fully adversarial networks . In Proceedings of the Symposium on Security &amp; Privacy. IEEE , Los Alamitos, CA, 241--255. Lysyanskaya, A., Tamassia, R., and Triandopoulos, N. 2004. Multicast authentication in fully adversarial networks. In Proceedings of the Symposium on Security &amp; Privacy. IEEE, Los Alamitos, CA, 241--255."},{"key":"e_1_2_1_23_1","unstructured":"McEliece R. J. 2003. The Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Tech. rep. JPL Interplanetary Network Progress Report IPN PR 42--153.  McEliece R. J. 2003. The Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Tech. rep. JPL Interplanetary Network Progress Report IPN PR 42--153."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_1"},{"volume-title":"Proceedings of the Symposium on Security &amp;  Privacy. IEEE","author":"Miner S.","key":"e_1_2_1_25_1","unstructured":"Miner , S. and Staddon , J . 2001. Graph-based authentication of digital streams . In Proceedings of the Symposium on Security &amp; Privacy. IEEE , Los Alamitos, CA, 232--246. Miner, S. and Staddon, J. 2001. Graph-based authentication of digital streams. In Proceedings of the Symposium on Security &amp; Privacy. IEEE, Los Alamitos, CA, 232--246."},{"volume-title":"Proceedings of the Network and Distributed System Security Symposium. Internet Society","author":"Pannetrat A.","key":"e_1_2_1_26_1","unstructured":"Pannetrat , A. and Molva , R . 2003. Efficient multicast packet authentication . In Proceedings of the Network and Distributed System Security Symposium. Internet Society , Reston, VA. Pannetrat, A. and Molva, R. 2003. Efficient multicast packet authentication. In Proceedings of the Network and Distributed System Security Symposium. Internet Society, Reston, VA."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/762476.762480"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/501983.501988"},{"volume-title":"Proceedings of the Network and Distributed System Security Symposium. Internet Society","author":"Perrig A.","key":"e_1_2_1_29_1","unstructured":"Perrig , A. , Canetti , R. , Song , D. , and Tygar , J . 2001. Efficient and secure source authentication for multicast . In Proceedings of the Network and Distributed System Security Symposium. Internet Society , Reston, VA, 35--46. Perrig, A., Canetti, R., Song, D., and Tygar, J. 2001. Efficient and secure source authentication for multicast. In Proceedings of the Network and Distributed System Security Symposium. Internet Society, Reston, VA, 35--46."},{"volume-title":"Proceedings of the Symposium on Security &amp;  Privacy. IEEE","author":"Perrig A.","key":"e_1_2_1_30_1","unstructured":"Perrig , A. , Canetti , R. , Tygar , J. , and Song , D . 2000. Efficient authentication and signing of multicast stream over lossy channels . In Proceedings of the Symposium on Security &amp; Privacy. IEEE , Los Alamitos, CA, 56--73. Perrig, A., Canetti, R., Tygar, J., and Song, D. 2000. Efficient authentication and signing of multicast stream over lossy channels. In Proceedings of the Symposium on Security &amp; Privacy. IEEE, Los Alamitos, CA, 56--73."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62050"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/319709.319722"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Theory of Cryptology Conference (CRYPTO'84)","author":"Simmons G. J.","year":"1984","unstructured":"Simmons , G. J. 1984 . Authentication theory\/coding theory . In Proceedings of the Theory of Cryptology Conference (CRYPTO'84) . Springer, Berlin, 411--431. Simmons, G. J. 1984. Authentication theory\/coding theory. In Proceedings of the Theory of Cryptology Conference (CRYPTO'84). Springer, Berlin, 411--431."},{"volume-title":"Proceedings of the Symposium on Security and Privacy. IEEE","author":"Song D.","key":"e_1_2_1_35_1","unstructured":"Song , D. , Zuckerman , D. , and Tygar , J. D . 2002. Expander graphs for digital stream authentication and robust overlay networks . In Proceedings of the Symposium on Security and Privacy. IEEE , Los Alamitos, CA, 258--270. Song, D., Zuckerman, D., and Tygar, J. D. 2002. Expander graphs for digital stream authentication and robust overlay networks. In Proceedings of the Symposium on Security and Privacy. IEEE, Los Alamitos, CA, 258--270."},{"key":"e_1_2_1_36_1","unstructured":"Welch L. and Berlekamp E. 1986. Error correction of algebraic block codes. U.S. Patent Number 4 633 470 issued December 1986.  Welch L. and Berlekamp E. 1986. Error correction of algebraic block codes. U.S. Patent Number 4 633 470 issued December 1986."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.793005"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/508791.508834"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698750.1698757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1698750.1698757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:58Z","timestamp":1750278178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698750.1698757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1698750.1698757"],"URL":"https:\/\/doi.org\/10.1145\/1698750.1698757","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2010,2]]},"assertion":[{"value":"2006-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}