{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:54:09Z","timestamp":1781078049366,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006919","name":"Massachusetts Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006919","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show a general compiler that transforms a large class of erroneous cryptographic schemes (such as public-key encryption, indistinguishability obfuscation, and secure multiparty computation schemes) into perfectly correct ones. The transformation works for schemes that are<jats:italic>correct on all inputs with probability noticeably larger than half<\/jats:italic>, and are secure under parallel repetition. We assume the existence of one-way functions and of functions with deterministic (uniform) time complexity<jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{O(n)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>2<\/mml:mn><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and non-deterministic circuit complexity<jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{\\Omega (n)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>2<\/mml:mn><mml:mrow><mml:mi>\u03a9<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our transformation complements previous results that showed how public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that<jats:italic>for all inputs<\/jats:italic>are often correct, showing that they can be made perfectly correct. The technique relies on the idea of \u201creverse randomization\u201d [Naor, Crypto 1989] and on Nisan\u2013Wigderson style derandomization, previously used in cryptography to remove interaction from witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].<\/jats:p>","DOI":"10.1007\/s00145-022-09428-0","type":"journal-article","created":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T21:02:37Z","timestamp":1652475757000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Note on Perfect Correctness by Derandomization"],"prefix":"10.1007","volume":"35","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,5,13]]},"reference":[{"key":"9428_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, C. Dwork. A public-key cryptosystem with worst-case\/average-case equivalence. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pp. 284\u2013293. ACM, (1997).","DOI":"10.1145\/258533.258604"},{"key":"9428_CR2","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Jain, A. Sahai. Robust transforming combiners from indistinguishability obfuscation to functional encryption. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part I, pp. 91\u2013121, (2017)","DOI":"10.1007\/978-3-319-56620-7_4"},{"key":"9428_CR3","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, O. Paneth, and Alon Rosen. On the existence of extractable one-way functions. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 505\u2013514. ACM, (2014)","DOI":"10.1145\/2591796.2591859"},{"issue":"2","key":"9428_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s001450010016","volume":"14","author":"D Boneh","year":"2001","unstructured":"D. Boneh, R.A. DeMillo, R.J. Lipton. On the importance of eliminating errors in cryptographic computations. J. Cryptology, 14(2):101\u2013119, (2001)","journal-title":"J. Cryptology"},{"issue":"2","key":"9428_CR5","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2160158.2160159","volume":"59","author":"B Barak","year":"2012","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, (2012)","journal-title":"J. ACM"},{"issue":"2","key":"9428_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.jcss.2005.06.010","volume":"72","author":"B Barak","year":"2006","unstructured":"B. Barak, Y. Lindell, SP. Vadhan. Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci., 72(2):321\u2013391, (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9428_CR7","doi-asserted-by":"crossref","unstructured":"M. Blum, S. Micali. How to generate cryptographically strong sequences of pseudo random bits. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pp. 112\u2013117, (1982)","DOI":"10.1109\/SFCS.1982.72"},{"issue":"4","key":"9428_CR8","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 pseudo-random bits. SIAM J. Comput., 13(4):850\u2013864, (1984)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9428_CR9","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1137\/050641958","volume":"37","author":"B Barak","year":"2007","unstructured":"B. Barak, S. Jin Ong, S.P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380\u2013400, (2007)","journal-title":"SIAM J. Comput."},{"key":"9428_CR10","doi-asserted-by":"crossref","unstructured":"N. Bitansky , O.P. Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II, vol. 9015 of Lecture Notes in Computer Science, pp. 401\u2013427. Springer, 2015.","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"9428_CR11","unstructured":"N. Bitansky, V. Vaikuntanthan. Indistinguishability obfuscation: from approximate to exact. In Theory of Cryptography - 13th Theory of Cryptography Conference, TCC 2016, Tel Aviv, Israel, January 10-13, 2016, 2016"},{"key":"9428_CR12","doi-asserted-by":"crossref","unstructured":"R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pp. 136\u2013145. IEEE Computer Society, 2001","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9428_CR13","doi-asserted-by":"crossref","unstructured":"C. Cachin, J. Camenisch, editors. Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, vol. 3027 of Lecture Notes in Computer Science. Springer, 2004","DOI":"10.1007\/b97182"},{"issue":"6","key":"9428_CR14","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"C Dwork","year":"2007","unstructured":"C. Dwork, M. Naor. Zaps and their applications. SIAM J. Comput., 36(6):1513\u20131543, (2007)","journal-title":"SIAM J. Comput."},{"key":"9428_CR15","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, O. Reingold. Immunizing encryption schemes from decryption errors. In Cachin and Camenisch [13], pp. 342\u2013360","DOI":"10.1007\/978-3-540-24676-3_21"},{"key":"9428_CR16","first-page":"429","volume":"5","author":"M Furer","year":"1989","unstructured":"M. Furer, O. Goldreich, Y. Mansour, M. Sipser, S. Zachos. On completeness and soundness in interactive proof systems. Adv. Comput. Res.: Res. Ann. (Randomness and Computation, S. Micali, ed.), 5:429\u2013442, (1989)","journal-title":"Advances in Computing Research: A Research Annual (Randomness and Computation, S. Micali, ed.)"},{"key":"9428_CR17","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, S. Halevi. Eliminating decryption errors in the ajtai-dwork cryptosystem. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO \u201997, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, vol. 1294 of Lecture Notes in Computer Science, pages 105\u2013111. Springer, (1997)","DOI":"10.1007\/BFb0052230"},{"issue":"2","key":"9428_CR18","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":"9428_CR19","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Y. Mansour, M. Sipser. Interactive proof systems: Provers that never fail and random selection (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pp. 449\u2013461. IEEE Computer Society, (1987)","DOI":"10.1109\/SFCS.1987.35"},{"key":"9428_CR20","volume-title":"The Foundations of Cryptography - Volume 2, Basic Applications","author":"O Goldreich","year":"2004","unstructured":"O. Goldreich. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004."},{"key":"9428_CR21","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S.P. Vadhan, A. Wigderson. Simplified derandomization of BPP using a hitting set generator. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pp. 59\u201367. (2011)","DOI":"10.1007\/978-3-642-22670-0_8"},{"issue":"4","key":"9428_CR22","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, LA. Levin, M. Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"9428_CR23","doi-asserted-by":"crossref","unstructured":"T. Holenstein, R. Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, vol. 3621 of Lecture Notes in Computer Science, pp. 478\u2013493. (Springer, 2005)","DOI":"10.1007\/11535218_29"},{"key":"9428_CR24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, A. Wigderson. $$P = BPP$$ if $$E$$ requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pp. 220\u2013229, (1997)","DOI":"10.1145\/258533.258590"},{"issue":"4","key":"9428_CR25","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C Lautemann","year":"1983","unstructured":"C. Lautemann. BPP and the polynomial hierarchy. Inf. Process. Lett., 17(4):215\u2013217, (1983)","journal-title":"Inf. Process. Lett."},{"key":"9428_CR26","unstructured":"H. Lin, S. Tessaro. Amplification of chosen-ciphertext security. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pp. 503\u2013519. (Springer, 2013)"},{"issue":"2","key":"9428_CR27","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M Naor","year":"1991","unstructured":"M. Naor. Bit commitment using pseudorandomness. J. Cryptology, 4(2):151\u2013158, (1991)","journal-title":"J. Cryptology"},{"issue":"2","key":"9428_CR28","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N Nisan","year":"1994","unstructured":"N. Nisan, A. Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149\u2013167, (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9428_CR29","doi-asserted-by":"crossref","unstructured":"O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 84\u201393. ACM, (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"9428_CR30","doi-asserted-by":"crossref","unstructured":"R. Shaltiel, C. Umans. Simple extractors for all min-entropies and a new pseudo-random generator. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pp. 648\u2013657, (2001)","DOI":"10.1109\/SFCS.2001.959941"},{"key":"9428_CR31","doi-asserted-by":"crossref","unstructured":"ACC. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pp. 80\u201391. IEEE Computer Society, (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"9428_CR32","doi-asserted-by":"crossref","unstructured":"ACC. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pp. 80\u201391, (1982)","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-022-09428-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09428-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09428-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,5]],"date-time":"2023-02-05T05:48:36Z","timestamp":1675576116000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09428-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,13]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9428"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09428-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,13]]},"assertion":[{"value":"30 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}