{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T22:40:48Z","timestamp":1708987248998},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T00:00:00Z","timestamp":1697587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T00:00:00Z","timestamp":1697587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>A wiretap coding scheme<\/jats:italic> (Wyner in Bell Syst Tech J 54(8):1355\u20131387, 1975) enables Alice to reliably communicate a message m<\/jats:italic> to an honest Bob by sending an encoding c<\/jats:italic> over a noisy channel $$\\textsf{ChB}$$<\/jats:tex-math>\n ChB<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, while at the same time hiding m<\/jats:italic> from Eve who receives c<\/jats:italic> over another noisy channel $$\\textsf{ChE}$$<\/jats:tex-math>\n ChE<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Wiretap coding is clearly impossible when $$\\textsf{ChB}$$<\/jats:tex-math>\n ChB<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a degraded<\/jats:italic> version of $$\\textsf{ChE}$$<\/jats:tex-math>\n ChE<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, in the sense that the output of $$\\textsf{ChB}$$<\/jats:tex-math>\n ChB<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be simulated using only the output of $$\\textsf{ChE}$$<\/jats:tex-math>\n ChE<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A classic work of Csisz\u00e1r and Korner (IEEE Trans Inf Theory 24(3):339\u2013348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $$(\\textsf{ChB},\\textsf{ChE})$$<\/jats:tex-math>\n \n (<\/mml:mo>\n ChB<\/mml:mi>\n ,<\/mml:mo>\n ChE<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does<\/jats:italic> hold when considering computational security<\/jats:italic>; that is, wiretap coding against a computationally bounded Eve is possible if and only if<\/jats:italic>$$\\textsf{ChB}$$<\/jats:tex-math>\n ChB<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is not a degraded version of $$\\textsf{ChE}$$<\/jats:tex-math>\n ChE<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our construction assumes the existence of virtual black-box obfuscation of specific classes of \u201cevasive\u201d functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal<\/jats:italic> in the sense that Alice\u2019s algorithm depends only on $$\\textsf{ChB}$$<\/jats:tex-math>\n ChB<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and not on $$\\textsf{ChE}$$<\/jats:tex-math>\n ChE<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00145-023-09482-2","type":"journal-article","created":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T20:36:43Z","timestamp":1697661403000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Beyond the Csisz\u00e1r\u2013K\u00f6rner Bound: Best-Possible Wiretap Coding via Obfuscation"],"prefix":"10.1007","volume":"37","author":[{"given":"Yuval","family":"Ishai","sequence":"first","affiliation":[]},{"given":"Alexis","family":"Korb","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Lou","sequence":"additional","affiliation":[]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,18]]},"reference":[{"key":"9482_CR1","doi-asserted-by":"crossref","unstructured":"S. Agrawal, Y. Ishai, E. Kushilevitz, V. Narayanan, M. Prabhakaran, V. Prabhakaran, A. Rosen, Secure computation from one-way noisy communication, or: anti-correlation via anti-concentration, in CRYPTO (2021).","DOI":"10.1007\/978-3-030-84245-1_5"},{"key":"9482_CR2","first-page":"764","volume-title":"Advances in Cryptology\u2013EUROCRYPT 2016, Part II volume 9666 of Lecture Notes in Computer Science, Vienna, Austria, May 8\u201312, 2016","author":"S Badrinarayanan","year":"2016","unstructured":"S. Badrinarayanan, E. Miles, A. Sahai, M. Zhandry, Post-zeroizing obfuscation: new mathematical tools, and the case of evasive circuits, in M. Fischlin, J.-S. Coron, editors, Advances in Cryptology\u2014EUROCRYPT\u00a02016, Part\u00a0II volume 9666 of Lecture Notes in Computer Science, Vienna, Austria, May\u00a08\u201312, 2016 (Springer, Heidelberg, 2016), pp. 764\u2013791"},{"key":"9482_CR3","doi-asserted-by":"crossref","unstructured":"B. Barak, N. Bitansky, R. Canetti, Y.T. Kalai, O. Paneth, A. Sahai, Obfuscation for evasive functions, in Theory of Cryptography Conference (Springer, 2014), pp. 26\u201351","DOI":"10.1007\/978-3-642-54242-8_2"},{"key":"9482_CR4","series-title":"Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 19\u201323, 2001","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44647-8_1","volume-title":"Advances in Cryptology\u2013CRYPTO 2001","author":"B Barak","year":"2001","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K.\u00a0Yang, On the (im)possibility of obfuscating programs, in J. Kilian, editor, Advances in Cryptology\u2014CRYPTO\u00a02001, volume 2139 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a019\u201323, 2001 (Springer, Heidelberg, 2001), pp. 1\u201318"},{"key":"9482_CR5","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Tessaro, A. Vardy, Semantic security for the wiretap channel, in R. Safavi-Naini, R. Canetti, editors, Advances in Cryptology\u2014CRYPTO 2012\u201432nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science (Springer, 2012), pp. 294\u2013311","DOI":"10.1007\/978-3-642-32009-5_18"},{"issue":"4","key":"9482_CR6","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M Blum","year":"1984","unstructured":"M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"9482_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti, B. Fuller, O. Paneth, L. Reyzin, A.D. Smith, Reusable fuzzy extractors for low-entropy distributions. J. Cryptol. 34(1), 2 (2021). Earlier version in Eurcrypt 2016","DOI":"10.1007\/s00145-020-09367-8"},{"key":"9482_CR8","series-title":"Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 18\u201322, 2013","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/978-3-642-40041-4_26","volume-title":"Advances in Cryptology\u2013CRYPTO 2013, Part I","author":"J-S Coron","year":"2013","unstructured":"J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers, in R. Canetti, J.A. Garay, editors, Advances in Cryptology\u2014CRYPTO\u00a02013, Part\u00a0I, volume 8042 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a018\u201322, 2013 (Springer, Heidelberg, 2013), pp. 476\u2013493"},{"issue":"1","key":"9482_CR9","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TIT.1972.1054727","volume":"18","author":"T Cover","year":"1972","unstructured":"T. Cover, Broadcast channels. IEEE Trans. Inf. Theory 18(1), 2\u201314 (1972)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9482_CR10","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1109\/TIT.1978.1055892","volume":"24","author":"I Csisz\u00e1r","year":"1978","unstructured":"I. Csisz\u00e1r, J. Korner, Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24(3), 339\u2013348 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9482_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Y. Dodis, R. Ostrovsky, L. Reyzin, A.D. Smith, Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008)","journal-title":"SIAM J. Comput."},{"key":"9482_CR12","doi-asserted-by":"crossref","unstructured":"B. Fuller, X. Meng, L. Reyzin, Computational fuzzy extractors. Inf. Comput. 275, 104602 (2020). Earlier version in Asiacrypt 2013","DOI":"10.1016\/j.ic.2020.104602"},{"key":"9482_CR13","series-title":"Lecture Notes in Computer Science, Athens, Greece, May 26\u201330, 2013","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-38348-9_1","volume-title":"Advances in Cryptology\u2013EUROCRYPT 2013","author":"S Garg","year":"2013","unstructured":"S. Garg, C. Gentry, S. Halevi, Candidate multilinear maps from ideal lattices, in T. Johansson, P.Q. Nguyen, editors, Advances in Cryptology\u2014EUROCRYPT\u00a02013, volume 7881 of Lecture Notes in Computer Science, Athens, Greece, May\u00a026\u201330, 2013 (Springer, Heidelberg, 2013), pp. 1\u201317"},{"key":"9482_CR14","first-page":"218","volume-title":"19th Annual ACM Symposium on Theory of Computing, New York City, NY, USA, May 25\u201327, 1987","author":"O Goldreich","year":"1987","unstructured":"O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in A. Aho, editor, 19th Annual ACM Symposium on Theory of Computing, New York City, NY, USA, May\u00a025\u201327, 1987 (ACM Press, New York, 1987), pp. 218\u2013229"},{"key":"9482_CR15","unstructured":"S. Goldwasser, Y.T. Kalai, On the impossibility of obfuscation with auxiliary input, in 46th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA, October\u00a023\u201325, 2005 (IEEE Computer Society Press, 2005), pp. 553\u2013562"},{"issue":"2","key":"9482_CR16","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9482_CR17","series-title":"Lecture Notes in Computer Science, Amsterdam, The Netherlands, February 21\u201324, 2007","first-page":"194","volume-title":"TCC 2007: 4th Theory of Cryptography Conference","author":"S Goldwasser","year":"2007","unstructured":"S. Goldwasser, G.N. Rothblum, On best-possible obfuscation, in S.P. Vadhan, editor, TCC\u00a02007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, Amsterdam, The Netherlands, February\u00a021\u201324, 2007 (Springer, Heidelberg, 2007), pp. 194\u2013213"},{"key":"9482_CR18","doi-asserted-by":"crossref","unstructured":"T. Holenstein, Key agreement from weak bit agreement, in H.N. Gabow, R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22\u201324, 2005 (ACM, 2005), pp. 664\u2013673","DOI":"10.1145\/1060590.1060689"},{"key":"9482_CR19","doi-asserted-by":"crossref","unstructured":"Y. Ishai, A. Korb, P. Lou, A. Sahai, Beyond the csisz\u00e1r\u2013k\u00f6rner bound: best-possible wiretap coding via obfuscation, in Crypto 2022 (2022)","DOI":"10.1007\/978-3-031-15979-4_20"},{"key":"9482_CR20","doi-asserted-by":"crossref","unstructured":"A. Jain, H. Lin, A. Sahai, Indistinguishability obfuscation from well-founded assumptions, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021), pp. 60\u201373","DOI":"10.1145\/3406325.3451093"},{"issue":"2","key":"9482_CR21","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10623-005-6343-z","volume":"38","author":"A Juels","year":"2006","unstructured":"A. Juels, M. Sudan, A fuzzy vault scheme. Des. Codes Cryptogr. 38(2), 237\u2013257 (2006)","journal-title":"Des. Codes Cryptogr."},{"key":"9482_CR22","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/319709.319714","volume-title":"ACM CCS 99: 6th Conference on Computer and Communications Security","author":"A Juels","year":"1999","unstructured":"A. Juels, M. Wattenberg, A fuzzy commitment scheme, in J. Motiwalla, G. Tsudik, editors, ACM CCS 99: 6th Conference on Computer and Communications Security, Singapore, November\u00a01\u20134, 1999 (ACM Press, 1999), pp. 28\u201336"},{"key":"9482_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2009\/142374","volume":"2009","author":"Y Liang","year":"2009","unstructured":"Y. Liang, G. Kramer, H.V. Poor, Compound wiretap channels. EURASIP J. Wirel. Commun. Netw. 2009, 1\u201312 (2009)","journal-title":"EURASIP J. Wirel. Commun. Netw."},{"key":"9482_CR24","doi-asserted-by":"crossref","unstructured":"U.M. Maurer, The strong secret key rate of discrete random triples, in Communications and Cryptography (Springer, 1994), pp. 271\u2013285","DOI":"10.1007\/978-1-4615-2694-0_27"},{"key":"9482_CR25","series-title":"Lecture Notes in Computer Science, Bruges, Belgium, May 14\u201318, 2000","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/3-540-45539-6_24","volume-title":"Advances in Cryptology\u2013EUROCRYPT 2000","author":"UM Maurer","year":"2000","unstructured":"U.M. Maurer, S. Wolf, Information-theoretic key agreement: from weak to strong secrecy for free, in B. Preneel, editor, Advances in Cryptology\u2014EUROCRYPT\u00a02000, volume 1807 of Lecture Notes in Computer Science, Bruges, Belgium, May\u00a014\u201318, 2000 (Springer, Heidelberg, 2000), pp. 351\u2013368"},{"issue":"3","key":"9482_CR26","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1109\/18.256484","volume":"39","author":"UM Maurer","year":"1993","unstructured":"U.M. Maurer, Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733\u2013742 (1993)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"9482_CR27","doi-asserted-by":"publisher","first-page":"4207","DOI":"10.1109\/TIT.2010.2054310","volume":"56","author":"C Nair","year":"2010","unstructured":"C. Nair, Capacity regions of two new classes of two-receiver broadcast channels. IEEE Trans. Inf. Theory 56(9), 4207\u20134214 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9482_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1073\/pnas.1618130114","volume":"114","author":"HV Poor","year":"2017","unstructured":"H.V. Poor, R.F. Schaefer, Wireless physical layer security. Proc. Natl. Acad. Sci. 114(1), 19\u201326 (2017)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"9482_CR29","unstructured":"M.T.C.A.J. Thomas, A.T. Joy, Elements of Information Theory (Wiley-Interscience, 2006)"},{"issue":"8","key":"9482_CR30","doi-asserted-by":"publisher","first-page":"1355","DOI":"10.1002\/j.1538-7305.1975.tb02040.x","volume":"54","author":"AD Wyner","year":"1975","unstructured":"A.D. Wyner, The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355\u20131387 (1975)","journal-title":"Bell Syst. Tech. J."},{"key":"9482_CR31","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Theory and application of trapdoor functions, in 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (IEEE, 1982), pp. 80\u201391","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09482-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09482-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09482-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T22:02:45Z","timestamp":1708984965000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09482-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,18]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["9482"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09482-2","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,18]]},"assertion":[{"value":"1 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}