{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:18Z","timestamp":1760202678450,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2014,9,8]],"date-time":"2014-09-08T00:00:00Z","timestamp":1410134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"],"award-info":[{"award-number":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2008411"],"award-info":[{"award-number":["2008411"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004284","name":"Xerox","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004284","id-type":"DOI","asserted-by":"publisher"}]},{"name":"B. John Garrick Foundation Award"},{"name":"Teradata Research Award"},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"],"award-info":[{"award-number":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"],"award-info":[{"award-number":["0546614, 0716835, 0716389, 0830803, 0831281, 0916574, 1012910, 1012798, CNS-0546614, CNS-0831281, CNS-1118126, CNS-1136174, CCF-0916574, CCF-1016540, CCF-0916574, IIS-1065276"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004317","name":"Lockheed Martin Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004317","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11-1-0392, N00014-11-1-0392"],"award-info":[{"award-number":["N00014-11-1-0392, N00014-11-1-0392"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004399","name":"Okawa Foundation for Information and Telecommunications","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004399","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,9,8]]},"abstract":"<jats:p>\n            We study the problem of \u201cprivacy amplification\u201d: key agreement between two parties who both know a weak secret\n            <jats:italic>w<\/jats:italic>\n            , such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about\n            <jats:italic>w<\/jats:italic>\n            , so we assume only that\n            <jats:italic>w<\/jats:italic>\n            has some entropy from Eve\u2019s point of view. Thus, the goal of the protocol is to convert this nonuniform secret\n            <jats:italic>w<\/jats:italic>\n            into a uniformly distributed string\n            <jats:italic>R<\/jats:italic>\n            that is fully secret from Eve.\n            <jats:italic>R<\/jats:italic>\n            may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.).\n          <\/jats:p>\n          <jats:p>\n            Because we make no computational assumptions, the entropy in\n            <jats:italic>R<\/jats:italic>\n            can come only from\n            <jats:italic>w<\/jats:italic>\n            . Thus, such a protocol must minimize the entropy loss during its execution, so that\n            <jats:italic>R<\/jats:italic>\n            is as long as possible. The best previous results have entropy loss of \u0398(\n            <jats:italic>\u03ba<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), where\n            <jats:italic>\u03ba<\/jats:italic>\n            is the security parameter, thus requiring the password to be very long even for small values of\n            <jats:italic>\u03ba<\/jats:italic>\n            . In this work, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. The result is optimal up to constant factors. We achieve our improvement through a somewhat surprising application of error-correcting codes for the edit distance.\n          <\/jats:p>\n          <jats:p>\n            The protocol can be extended to provide also \u201cinformation reconciliation,\u201d that is, to work even when the two parties have slightly different versions of\n            <jats:italic>w<\/jats:italic>\n            (e.g., when biometrics are involved).\n          <\/jats:p>","DOI":"10.1145\/2630064","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T14:39:29Z","timestamp":1410273569000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Privacy amplification with asymptotically optimal entropy loss"],"prefix":"10.1145","volume":"61","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[{"name":"Microsoft Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhavana","family":"Kanukurthi","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Reyzin","sequence":"additional","affiliation":[{"name":"Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1137\/0217014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/18.476316"},{"key":"e_1_2_1_3_1","volume-title":"Bouman and Serge Fehr","author":"Niek","year":"2011","unstructured":"Niek J. Bouman and Serge Fehr . 2011 . Secure authentication from a weak key, without leaking information. In Proceedings of EUROCRYPT. 246--265. Niek J. Bouman and Serge Fehr. 2011. Secure authentication from a weak key, without leaking information. In Proceedings of EUROCRYPT. 246--265."},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/11426639_9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/0022-0000(79)90044-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1806689.1806796"},{"key":"e_1_2_1_7_1","volume-title":"Electron. Colloq. Computat. Complex. 18","author":"Cohen Gil","year":"2011","unstructured":"Gil Cohen , Ran Raz , and Gil Segev . 2011 . Non-malleable extractors with short seeds and applications to privacy amplification . Electron. Colloq. Computat. Complex. 18 , 96. Gil Cohen, Ran Raz, and Gil Segev. 2011. Non-malleable extractors with short seeds and applications to privacy amplification. Electron. Colloq. Computat. Complex. 18, 96."},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/TIT.2012.2200290"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/FOCS.2011.67"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/060651380"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1536414.1536496"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/CCC.2007.38"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1137\/S0097539793244708"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/FOCS.2009.56"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/3088723.3088748"},{"key":"e_1_2_1_16_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","author":"Levenshtein Vladimir I.","year":"1966","unstructured":"Vladimir I. Levenshtein . 1966 . Binary codes capable of correcting deletions, insertions and reversals . Soviet Phys. Dokl. 10 , 707 -- 710 . Vladimir I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707--710.","journal-title":"Soviet Phys. Dokl."},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/2213977.2214052"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Advances in Cryptology---EUROCRYPT\u201997, Walter Fumy Ed.","author":"Maurer Ueli","unstructured":"Ueli Maurer . 1997. Information-theoretically secure secret-key agreement by NOT authenticated public discussion . In Proceedings of Advances in Cryptology---EUROCRYPT\u201997, Walter Fumy Ed. , Lecture Notes in Computer Science , vol. 1233 , Springer-Verlag , 209--225. Ueli Maurer. 1997. Information-theoretically secure secret-key agreement by NOT authenticated public discussion. In Proceedings of Advances in Cryptology---EUROCRYPT\u201997, Walter Fumy Ed., Lecture Notes in Computer Science, vol. 1233, Springer-Verlag, 209--225."},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Advances in Cryptology---CRYPTO\u201997, Burton S. Kaliski, Jr. Ed.","author":"Maurer Ueli","unstructured":"Ueli Maurer and Stefan Wolf . 1997. Privacy amplification secure against active adversaries . In Proceedings of Advances in Cryptology---CRYPTO\u201997, Burton S. Kaliski, Jr. Ed. , Lecture Notes in Computer Science , vol. 1294 , Springer-Verlag , 307--321. Ueli Maurer and Stefan Wolf. 1997. Privacy amplification secure against active adversaries. In Proceedings of Advances in Cryptology---CRYPTO\u201997, Burton S. Kaliski, Jr. Ed., Lecture Notes in Computer Science, vol. 1294, Springer-Verlag, 307--321."},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/TIT.2003.809559"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1006\/jcss.1996.0004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Advances in Cryptology---CRYPTO\u201903, Dan Boneh Ed.","author":"Renner Renato","unstructured":"Renato Renner and Stefan Wolf . 2003. Unconditional authenticity and privacy from an arbitrarily weak secret . In Proceedings of Advances in Cryptology---CRYPTO\u201903, Dan Boneh Ed. , Lecture Notes in Computer Science , vol. 2729 , Springer-Verlag , 78--95. Renato Renner and Stefan Wolf. 2003. Unconditional authenticity and privacy from an arbitrarily weak secret. In Proceedings of Advances in Cryptology---CRYPTO\u201903, Dan Boneh Ed., Lecture Notes in Computer Science, vol. 2729, Springer-Verlag, 78--95."},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Advances in Cryptology---EUROCRYPT\u201904, Christian Cachin and Jan Camenisch Eds.","author":"Renner Renato","unstructured":"Renato Renner and Stefan Wolf . 2004. The exact price for unconditionally secure asymmetric cryptography . In Proceedings of Advances in Cryptology---EUROCRYPT\u201904, Christian Cachin and Jan Camenisch Eds. , Lecture Notes in Computer Science , vol. 3027 , Springer-Verlag , 109--125. Renato Renner and Stefan Wolf. 2004. The exact price for unconditionally secure asymmetric cryptography. In Proceedings of Advances in Cryptology---EUROCRYPT\u201904, Christian Cachin and Jan Camenisch Eds., Lecture Notes in Computer Science, vol. 3027, Springer-Verlag, 109--125."},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1109\/18.796406"},{"key":"e_1_2_1_27_1","first-page":"3","article-title":"Universal hash families and the leftover hash lemma, and applications to cryptography and computing","volume":"42","author":"Stinson D. R.","year":"2002","unstructured":"D. R. Stinson . 2002 . Universal hash families and the leftover hash lemma, and applications to cryptography and computing . J. Combinat. Math. Combinat. Comput. 42 , 3 -- 31 . http:\/\/www.cacr.math.uwaterloo.ca\/~dstinson\/publist.html. D. R. Stinson. 2002. Universal hash families and the leftover hash lemma, and applications to cryptography and computing. J. Combinat. Math. Combinat. Comput. 42, 3--31. http:\/\/www.cacr.math.uwaterloo.ca\/~dstinson\/publist.html.","journal-title":"J. Combinat. Math. Combinat. Comput."},{"doi-asserted-by":"crossref","unstructured":"Salil Vadhan. 2012. Pseudorandomness. Now publishers. http:\/\/people.seas.harvard.edu\/~salil\/pseudorandomness\/.   Salil Vadhan. 2012. Pseudorandomness . Now publishers. http:\/\/people.seas.harvard.edu\/~salil\/pseudorandomness\/.","key":"e_1_2_1_28_1","DOI":"10.1561\/9781601985958"},{"key":"e_1_2_1_29_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Advances in Cryptology---ASIACRYPT\u201998, Kazuo Ohta and Dingyi Pei Eds.","author":"Wolf Stefan","unstructured":"Stefan Wolf . 1998. Strong security against active attacks in information-theoretic secret-key agreement . In Proceedings of Advances in Cryptology---ASIACRYPT\u201998, Kazuo Ohta and Dingyi Pei Eds. , Lecture Notes in Computer Science , vol. 1514 , Springer-Verlag , 405--419. Stefan Wolf. 1998. Strong security against active attacks in information-theoretic secret-key agreement. In Proceedings of Advances in Cryptology---ASIACRYPT\u201998, Kazuo Ohta and Dingyi Pei Eds., Lecture Notes in Computer Science, vol. 1514, Springer-Verlag, 405--419."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2630064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2630064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:36Z","timestamp":1750231176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2630064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,8]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9,8]]}},"alternative-id":["10.1145\/2630064"],"URL":"https:\/\/doi.org\/10.1145\/2630064","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,9,8]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}