{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:39:07Z","timestamp":1725561547532},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642147111"},{"type":"electronic","value":"9783642147128"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14712-8_12","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T09:17:50Z","timestamp":1280395070000},"page":"189-204","source":"Crossref","is-referenced-by-count":4,"title":["On the Round Complexity of Zero-Knowledge Proofs Based on One-Way Permutations"],"prefix":"10.1007","author":[{"given":"S. Dov","family":"Gordon","sequence":"first","affiliation":[]},{"given":"Hoeteck","family":"Wee","sequence":"additional","affiliation":[]},{"given":"David","family":"Xiao","sequence":"additional","affiliation":[]},{"given":"Arkady","family":"Yerukhimovich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","first-page":"327","volume":"42","author":"W. Aiello","year":"1991","unstructured":"Aiello, W., Hastad, J.: Statistical zero-knowledge languages can be recognized in two rounds. JCSS\u00a042, 327\u2013345 (1991)","journal-title":"JCSS"},{"key":"12_CR2","first-page":"106","volume-title":"Proc. 42nd FOCS","author":"B. Barak","year":"2001","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: Proc. 42nd FOCS, pp. 106\u2013115. IEEE, Los Alamitos (2001)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Lindell, Y.: Strict polynomial-time in simulation and extraction. In: STOC, pp. 484\u2013493 (2002)","DOI":"10.1145\/509907.509979"},{"issue":"2","key":"12_CR4","first-page":"321","volume":"72","author":"B. Barak","year":"2006","unstructured":"Barak, B., Lindell, Y., Vadhan, S.: Lower bounds for non-black-box zero knowledge. JCSS\u00a072(2), 321\u2013391 (2006)","journal-title":"JCSS"},{"key":"12_CR5","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 - EUROCRYPT \u201997","author":"M. Bellare","year":"1997","unstructured":"Bellare, M., Jakobsson, M., Yung, M.: Round-optimal zero-knowledge arguments based on any one-way function. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol.\u00a01233, pp. 280\u2013305. Springer, Heidelberg (1997)"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Bellare, M., Micali, S., Ostrovsky, R.: Perfect zero-knowledge in constant rounds. In: STOC, pp. 482\u2013493 (1990)","DOI":"10.1145\/100216.100283"},{"key":"12_CR7","unstructured":"Blum, M.: How to prove a theorem so no one else can claim it. In: Proc. ICM (1986)"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/3-540-46885-4_21","volume-title":"Advances in Cryptology - EUROCRYPT \u201989","author":"G. Brassard","year":"1990","unstructured":"Brassard, G., Cr\u00e9peau, C., Yung, M.: Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol.\u00a0434, pp. 192\u2013195. Springer, Heidelberg (1990)"},{"key":"12_CR9","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 - CRYPTO \u201989","author":"U. Feige","year":"1990","unstructured":"Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 526\u2013545. Springer, Heidelberg (1990)"},{"key":"12_CR10","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 - CRYPTO \u201989","author":"U. Feige","year":"1990","unstructured":"Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 526\u2013544. Springer, Heidelberg (1990)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: The complexity of perfect zero-knowledge. In: STOC \u201987, pp. 204\u2013209 (1987)","DOI":"10.1145\/28395.28418"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput.\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM J. Comput."},{"key":"12_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Applications, vol.\u00a02. Cambridge University Press, New York (2004)"},{"issue":"3","key":"12_CR14","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s001459900010","volume":"9","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology\u00a09(3), 167\u2013190 (1996)","journal-title":"J. Cryptology"},{"issue":"1","key":"12_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/S0097539791220688","volume":"25","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM J. Comput.\u00a025(1), 169\u2013192 (1996)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM\u00a038(3), 691\u2013729 (1991) (prelim. version in FOCS \u201986)","journal-title":"J. ACM"},{"issue":"1","key":"12_CR17","first-page":"1","volume":"7","author":"O. Goldreich","year":"1994","unstructured":"Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems\u00a07(1), 1\u201332 (Winter 1994) (preliminary version in FOCS\u2019 87)","journal-title":"Winter 1994"},{"issue":"1","key":"12_CR18","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput.\u00a018(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"12_CR19","first-page":"73","volume":"5","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. Advances in Computing Research: Randomness and Computation\u00a05, 73\u201390 (1989)","journal-title":"Advances in Computing Research: Randomness and Computation"},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/BFb0055744","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"S. Hada","year":"1998","unstructured":"Hada, S., Tanaka, T.: On the existence of 3-round zero-knowledge protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 408\u2013423. Springer, Heidelberg (1998)"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: Proc. FOCS \u201907, pp. 669\u2013679 (2007)","DOI":"10.1109\/FOCS.2007.7"},{"key":"12_CR22","unstructured":"Haitner, I., Mahmoody-Ghidary, M., Xiao, D.: A new sampling protocol and applications to basing cryptography on NP-hardnss. In: Proc. CCC 2010 (to appear, 2010), Full version available as ECCC TR-867-09"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Haitner, I., Reingold, O., Vadhan, S., Wee, H.: Inaccessible entropy. In: STOC, pp. 611\u2013620 (2009)","DOI":"10.1145\/1536414.1536497"},{"issue":"4","key":"12_CR24","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. of Com.\u00a028(4), 1364\u20131396 (1999) (preliminary versions appeared in STOC\u2019 89 and STOC\u2019 90)","journal-title":"SIAM J. of Com."},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: STOC, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-540-78524-8_5","volume-title":"Theory of Cryptography","author":"J. Katz","year":"2008","unstructured":"Katz, J.: Which languages have 4-round zero-knowledge proofs? In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 73\u201388. Springer, Heidelberg (2008)"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. In: FOCS, pp. 2\u201310 (1990)","DOI":"10.1109\/FSCS.1990.89518"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Naor, M.: Bit commitment using pseudorandomness 4(2), 151\u2013158 (1991) (preliminary version in CRYPTO\u2019 89)","DOI":"10.1007\/BF00196774"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: ISTCS \u201993, pp. 3\u201317 (1993)","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on np-hardness. In: IEEE Conference on Computational Complexity, pp. 96\u2013110 (2006)","DOI":"10.1109\/CCC.2006.33"},{"key":"12_CR31","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":"TCC 2010","author":"R. Pass","year":"2010","unstructured":"Pass, R., Venkitasubramaniam, M.: Private coins versus public coins in zero-knowledge proof systems. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 588\u2013605. Springer, Heidelberg (2010)"},{"key":"12_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-00457-5_24","volume-title":"Theory of Cryptography","author":"R. Pass","year":"2009","unstructured":"Pass, R., Wee, H.: Black-box constructions of two-party protocols from one-way functions. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 403\u2013418. Springer, Heidelberg (2009)"},{"issue":"1-3","key":"12_CR33","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.tcs.2007.06.013","volume":"385","author":"A. Pavan","year":"2007","unstructured":"Pavan, A., Selman, A.L., Sengupta, S., Vinodchandran, N.V.: Polylogarithmic-round interactive proofs for conp collapse the exponential hierarchy. Theor. Comput. Sci.\u00a0385(1-3), 167\u2013178 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR34","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"key":"12_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-540-24638-1_11","volume-title":"Theory of Cryptography","author":"A. Rosen","year":"2004","unstructured":"Rosen, A.: A note on constant-round zero-knowledge proofs for np. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 191\u2013202. Springer, Heidelberg (2004)"},{"key":"12_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"D.R. Simon","year":"1998","unstructured":"Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"key":"12_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-70936-7_23","volume-title":"Theory of Cryptography","author":"H. Wee","year":"2007","unstructured":"Wee, H.: One-way permutations, interactive hashing and statistically hiding commitments. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 419\u2013433. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology \u2013 LATINCRYPT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14712-8_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:56:39Z","timestamp":1606186599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14712-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642147111","9783642147128"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14712-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}