{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:33:50Z","timestamp":1787510030193,"version":"build-2736575974"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,10,8]],"date-time":"2010-10-08T00:00:00Z","timestamp":1286496000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00145-010-9081-y","type":"journal-article","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T04:08:17Z","timestamp":1286424497000},"page":"41-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Which Languages Have 4-Round Zero-Knowledge Proofs?"],"prefix":"10.1007","volume":"25","author":[{"given":"Jonathan","family":"Katz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,10,8]]},"reference":[{"issue":"3","key":"9081_CR1","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0022-0000(91)90006-Q","volume":"42","author":"W. Aiello","year":"1991","unstructured":"W. Aiello, J. H\u00e5stad, Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci.\n                           42(3), 327\u2013345 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9081_CR2","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai, S. Moran, Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci.\n                           36(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9081_CR3","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/SFCS.2001.959885","volume-title":"Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"B. Barak","year":"2001","unstructured":"B. Barak, How to go beyond the black-box simulation barrier, in Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, New York, 2001), pp. 106\u2013115"},{"issue":"4","key":"9081_CR4","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539703427975","volume":"33","author":"B. Barak","year":"2004","unstructured":"B. Barak, Y. Lindell, Strict polynomial-time in simulation and extraction. SIAM J. Comput.\n                           33(4), 738\u2013818 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9081_CR5","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, S. Vadhan, Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci.\n                           72(2), 321\u2013391 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9081_CR6","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1137\/050641958","volume":"37","author":"B. Barak","year":"2007","unstructured":"B. Barak, S.J. Ong, S.P. Vadhan, Derandomization in cryptography. SIAM J. Comput.\n                           37(2), 380\u2013400 (2007)","journal-title":"SIAM J. Comput."},{"key":"9081_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/3-540-69053-0_20","volume-title":"Advances in Cryptology\u2014Eurocrypt \u201997","author":"M. Bellare","year":"1997","unstructured":"M. Bellare, M. Jakobsson, M. Yung, Round-optimal zero-knowledge arguments based on any one-way function, in Advances in Cryptology\u2014Eurocrypt \u201997. Lecture Notes in Computer Science, vol. 1233 (Springer, Berlin, 1997), pp. 280\u2013305"},{"key":"9081_CR8","first-page":"482","volume-title":"Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Bellare","year":"1990","unstructured":"M. Bellare, S. Micali, R. Ostrovsky, Perfect zero knowledge in constant rounds, in Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC) (ACM, New York, 1990), pp. 482\u2013493"},{"key":"9081_CR9","first-page":"494","volume-title":"Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Bellare","year":"1990","unstructured":"M. Bellare, S. Micali, R. Ostrovsky, The (true) complexity of statistical zero knowledge, in Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC) (ACM, New York, 1990), pp. 494\u2013502"},{"key":"9081_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-28628-8_17","volume-title":"Advances in Cryptology\u2014Crypto 2004","author":"M. Bellare","year":"2004","unstructured":"M. Bellare, A. Palacio, The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols, in Advances in Cryptology\u2014Crypto 2004. Lecture Notes in Computer Science, vol. 3152 (Springer, Berlin, 2004), pp. 273\u2013289"},{"key":"9081_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Advances in Cryptology\u2014Crypto \u201988","author":"M. Ben-Or","year":"1990","unstructured":"M. Ben-Or, O. Goldreich, S. Goldwasser, J. H\u00e5stad, J. Kilian, S. Micali, P. Rogaway, Everything provable is provable in zero knowledge, in Advances in Cryptology\u2014Crypto \u201988. Lecture Notes in Computer Science, vol. 403 (Springer, Berlin, 1990), pp. 37\u201356"},{"issue":"2","key":"9081_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"R. Boppana, J. H\u00e5stad, S. Zachos, Does coNP have short interactive proofs? Inf. Process. Lett.\n                           25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9081_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF00204448","volume":"2","author":"J. Boyar","year":"1990","unstructured":"J. Boyar, S. Kurtz, M. Krentel, Discrete logarithm implementation of perfect zero-knowledge blobs. J.\u00a0Cryptol.\n                           2(2), 63\u201376 (1990)","journal-title":"J.\u00a0Cryptol."},{"issue":"2","key":"9081_CR14","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"G. Brassard, D. Chaum, C. Cr\u00e9peau, Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci.\n                           37(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9081_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-540-46588-1_24","volume-title":"Public-Key Cryptography (PKC) 2000","author":"R. Cramer","year":"2000","unstructured":"R. Cramer, I. Damg\u00e5rd, P. MacKenzie, Efficient zero-knowledge proofs of knowledge without intractability assumptions, in Public-Key Cryptography (PKC) 2000. Lecture Notes in Computer Science, vol. 1751 (Springer, Berlin, 2000), pp. 354\u2013372"},{"issue":"2","key":"9081_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(94)90015-9","volume":"50","author":"G. Crescenzo Di","year":"1994","unstructured":"G. Di Crescenzo, G. Persiano, Round-optimal perfect zero-knowledge proofs. Inf. Process. Lett.\n                           50(2), 93\u201399 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9081_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s001459900026","volume":"10","author":"I. Damg\u00e5rd","year":"1997","unstructured":"I. Damg\u00e5rd, M. Pedersen, B. Pfitzmann, On the existence of statistically-hiding bit commitment schemes and fail-stop signatures. J. Cryptol.\n                           10(3), 163\u2013194 (1997)","journal-title":"J. Cryptol."},{"key":"9081_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1007\/0-387-34805-0_46","volume-title":"Advances in Cryptology\u2014Crypto \u201989","author":"U. Feige","year":"1990","unstructured":"U. Feige, A. Shamir, Zero knowledge proofs of knowledge in two rounds, in Advances in Cryptology\u2014Crypto \u201989. Lecture Notes in Computer Science, vol. 435 (Springer, Berlin, 1990), pp. 526\u2013544"},{"key":"9081_CR19","first-page":"327","volume-title":"Advances in Computing Research","author":"L. Fortnow","year":"1989","unstructured":"L. Fortnow, The complexity of perfect zero knowledge, in Advances in Computing Research, ed. by S.\u00a0Micali, vol. 5 (JAC Press, Inc., Stanford, 1989), pp. 327\u2013343"},{"issue":"3","key":"9081_CR20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s001459900010","volume":"9","author":"O. Goldreich","year":"1996","unstructured":"O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP. J.\u00a0Cryptol.\n                           9(3), 167\u2013190 (1996)","journal-title":"J.\u00a0Cryptol."},{"issue":"1","key":"9081_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/S0097539791220688","volume":"25","author":"O. Goldreich","year":"1996","unstructured":"O. Goldreich, H. Krawczyk, On the composition of zero-knowledge proof systems. SIAM J. Comput.\n                           25(1), 169\u2013192 (1996)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9081_CR22","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems. J. ACM\n                           38(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"9081_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O. Goldreich","year":"1994","unstructured":"O. Goldreich, Y. Oren, Definitions and properties of zero-knowledge proof systems. J. Cryptol.\n                           7(1), 1\u201332 (1994)","journal-title":"J. Cryptol."},{"issue":"1","key":"9081_CR24","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput.\n                           18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9081_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S. Goldwasser","year":"1988","unstructured":"S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput.\n                           17(2), 281\u2013308 (1988)","journal-title":"SIAM J. Comput."},{"key":"9081_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-14712-8_12","volume-title":"Progress in Cryptology\u2014Latincrypt 2010","author":"S.D. Gordon","year":"2010","unstructured":"S.D. Gordon, H. Wee, D. Xiao, A. Yerukhimovich, On the round complexity of zero-knowledge proofs based on one-way permutations, in Progress in Cryptology\u2014Latincrypt 2010. Lecture Notes in Computer Science, vol. 6212 (Springer, Berlin, 2010), pp. 189\u2013204"},{"key":"9081_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/BFb0055744","volume-title":"Advances in Cryptology\u2014Crypto \u201998","author":"S. Hada","year":"1998","unstructured":"S. Hada, T. Tanaka, On the existence of 3-round zero-knowledge protocols, in Advances in Cryptology\u2014Crypto \u201998. Lecture Notes in Computer Science, vol. 1462 (Springer, Berlin, 1998), pp. 408\u2013423. Available at \n                    http:\/\/eprint.iacr.org\/1999\/009"},{"key":"9081_CR28","first-page":"669","volume-title":"Proc. 48th Annual Symposium on Foundations of Computer Science (FOCS)","author":"I. Haitner","year":"2007","unstructured":"I. Haitner, J.J. Hoch, O. Reingold, G. Segev, Finding collisions in interactive protocols\u2014a tight bound on the round complexity of statistically-hiding commitments, in Proc. 48th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, New York, 2007), pp. 669\u2013679. Available at \n                    http:\/\/eprint.iacr.org\/2007\/145"},{"issue":"3","key":"9081_CR29","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1137\/080725404","volume":"39","author":"I. Haitner","year":"2009","unstructured":"I. Haitner, M.-H. Nguyen, S.J. Ong, O. Reingold, S.P. Vadhan, Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput.\n                           39(3), 1153\u20131218 (2009)","journal-title":"SIAM J. Comput."},{"key":"9081_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/3-540-68697-5_16","volume-title":"Advances in Cryptology\u2014Crypto \u201996","author":"S. Halevi","year":"1996","unstructured":"S. Halevi, S. Micali, Practical and provably-secure commitment schemes from collision-free hashing, in Advances in Cryptology\u2014Crypto \u201996. Lecture Notes in Computer Science, vol. 1109 (Springer, Berlin, 1996), pp. 201\u2013215"},{"key":"9081_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-48184-2_4","volume-title":"Advances in Cryptology\u2014Crypto \u201987","author":"R. Impagliazzo","year":"1988","unstructured":"R. Impagliazzo, M. Yung, Direct minimum-knowledge computations, in Advances in Cryptology\u2014Crypto \u201987. Lecture Notes in Computer Science, vol. 293 (Springer, Berlin, 1988), pp. 40\u201351"},{"key":"9081_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/3-540-57332-1_28","volume-title":"Advances in Cryptology\u2014Asiacrypt \u201991","author":"T. Itoh","year":"1993","unstructured":"T. Itoh, K. Sakurai, On the complexity of constant-round ZKIP of possession of knowledge, in Advances in Cryptology\u2014Asiacrypt \u201991. Lecture Notes in Computer Science, vol. 739 (Springer, Berlin, 1993), pp. 331\u2013345"},{"key":"9081_CR33","first-page":"34","volume":"E78-A(1)","author":"K. Kurosawa","year":"1995","unstructured":"K. Kurosawa, W. Ogata, S. Tsujii, 4-move perfect ZKIP for some promise problems. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.\n                           E78-A(1), 34\u201341 (1995)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"9081_CR34","unstructured":"M. Lepinski, On the existence of 3-round zero-knowledge proofs. Master\u2019s thesis, MIT, Cambridge, MA (2002). Available at \n                    http:\/\/theory.lcs.mit.edu\/~cis\/cis-theses.html"},{"key":"9081_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1007\/978-3-540-78524-8_27","volume-title":"3rd Theory of Cryptography Conference (TCC)","author":"S.J. Ong","year":"2008","unstructured":"S.J. Ong, S. Vadhan, An equivalence between zero knowledge and commitments, in 3rd Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, vol. 4948 (Springer, Berlin, 2008), pp. 482\u2013500"},{"key":"9081_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1007\/978-3-642-11799-2_35","volume-title":"5th Theory of Cryptography Conference (TCC)","author":"R. Pass","year":"2010","unstructured":"R. Pass, M. Venkitasubramaniam, Private coins versus public coins in zero-knowledge proof systems, in 5th Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, vol. 5978 (Springer, Berlin, 2010), pp. 588\u2013605"},{"key":"9081_CR37","series-title":"Lecture Notes in Computer Science","first-page":"320","volume-title":"Advances in Cryptology\u2014Asiacrypt \u201991","author":"T. Saito","year":"1993","unstructured":"T. Saito, K. Kurosawa, K. Sakurai, 4-move perfect SKIP of knowledge with no assumption, in Advances in Cryptology\u2014Asiacrypt \u201991. Lecture Notes in Computer Science, vol. 739 (Springer, Berlin, 1993), pp. 320\u2013331"},{"key":"9081_CR38","unstructured":"S. Vadhan, A study of statistical zero-knowledge proofs. Ph.D. thesis, MIT, Cambridge, MA (1999)"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9081-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-010-9081-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9081-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9081-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T04:48:50Z","timestamp":1586321330000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-010-9081-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,8]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["9081"],"URL":"https:\/\/doi.org\/10.1007\/s00145-010-9081-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,8]]},"assertion":[{"value":"2 May 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2010","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}