{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:36Z","timestamp":1787340756597,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>The simulation paradigm, introduced by Goldwasser, Micali, and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak [FOCS 2001, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 106--115] introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth [FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 223--232] instead requires the existence of an oblivious transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge arguments.<\/jats:p>","DOI":"10.1137\/130946083","type":"journal-article","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T10:39:53Z","timestamp":1461235193000},"page":"415-458","source":"Crossref","is-referenced-by-count":11,"title":["Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security"],"prefix":"10.1137","volume":"45","author":[{"given":"Kai-Min","family":"Chung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karn","family":"Seth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"B. Barak,\n                      How to go beyond the black-box simulation barrier\n                      , in FOCS 2001, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 106-115.","DOI":"10.1109\/SFCS.2001.959885"},{"key":"atypb2","unstructured":"B. Barak and O. Goldreich,\n                      Universal arguments and their applications\n                      , in Computational Complexity, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 162-171."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell,\n                      Resettably sound zero-knowledge and its applications\n                      , in FOCS 2002 IEEE Computer Society, Los Alamitos, CA, 2002, pp. 116-125.","DOI":"10.1109\/SFCS.2001.959886"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"atypb5","unstructured":"M. Blum,\n                      How to prove a theorem so no one else can claim it\n                      , in Proceedings of the International Congress of Mathematicians, International Congress of Mathematicians, Berkely, CA, 1986, pp. 1444-1451."},{"key":"atypb6","first-page":"223","author":"Bitansky N.","year":"2012","journal-title":"NJ"},{"key":"atypb7","first-page":"241","volume":"2013","author":"Bitansky N.","year":"2013","journal-title":"STOC"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335334"},{"key":"atypb9","first-page":"40","author":"Canetti R.","year":"2004","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/380752.380852","volume":"2001","author":"Canetti R.","year":"2001","journal-title":"STOC"},{"key":"atypb11","first-page":"60","author":"Chung K.-M.","year":"2013","journal-title":"NJ"},{"key":"atypb12","first-page":"231","author":"Chung K.-M.","year":"2013","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Y. Deng, V. Goyal, and A. Sahai,\n                      Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 251-260.","DOI":"10.1109\/FOCS.2009.59"},{"key":"atypb14","first-page":"416","volume":"1990","author":"Feige U.","year":"1990","journal-title":"STOC"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208001"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF00195207"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Foundations of Cryptography\n                      , Cambridge University Press, Cambridge, 2001.","DOI":"10.1017\/CBO9780511546891"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"atypb22","first-page":"723","author":"Kilian J.","year":"1992","journal-title":"New York"},{"key":"atypb23","first-page":"203","author":"Lindell Y.","year":"2004","journal-title":"New York"},{"key":"atypb24","first-page":"705","volume":"2011","author":"Lin H.","year":"2011","journal-title":"STOC"},{"key":"atypb25","unstructured":"R. C. Merkle,\n                      Digital Signature System and Method Based on a Conventional Encryption Function\n                      , November 14, 1989. U.S. Patent 4,881,264."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"atypb28","first-page":"33","volume":"1989","author":"Naor M.","year":"1989","journal-title":"STOC"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and A. Wigderson,\n                      One-way functions are essential for non-trivial zero-knowledge\n                      , in Theory and Computing Systems, 1993, IEEE Computer Society, Los Alamitos, CA, 2002, 1993, pp. 3-17.","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"atypb30","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1145\/1007352.1007393","volume":"2004","author":"Pass R.","year":"2004","journal-title":"STOC"},{"key":"atypb31","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/1060590.1060670","volume":"2005","author":"Pass R.","year":"2005","journal-title":"STOC"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Prabhakaran, A. Rosen, and A. Sahai,\n                      Concurrent zero knowledge with logarithmic round-complexity\n                      , in FOCS 2002, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 366-375.","DOI":"10.1109\/SFCS.2002.1181961"},{"key":"atypb33","first-page":"160","author":"Pass R.","year":"2009","journal-title":"Berlin"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/100811465"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"J. Rompel,\n                      One-way functions are necessary and sufficient for secure signatures\n                      , 1990 STOC 1990, ACM, New York, pp. 387-394.","DOI":"10.1145\/100216.100269"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130946083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:40Z","timestamp":1787338000000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130946083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/130946083"],"URL":"https:\/\/doi.org\/10.1137\/130946083","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}