{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:27:01Z","timestamp":1725496021599},"publisher-location":"Berlin, Heidelberg","reference-count":77,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_5","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"52-70","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Zero Knowledge"],"prefix":"10.1007","author":[{"given":"Salil","family":"Vadhan","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1145\/509907.509999","volume-title":"Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing","author":"S. Aaronson","year":"2002","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 635\u2013642. ACM, New York (2002)"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/11753728_4","volume-title":"Computer Science \u2013 Theory and Applications","author":"V. Arvind","year":"2006","unstructured":"Arvind, V., Das, B.: Szk proofs for black-box group problems. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 6\u201317. Springer, Heidelberg (2006)"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0022-0000(91)90006-Q","volume":"42","author":"W. Aiello","year":"1991","unstructured":"Aiello, W., H\u00e5stad, J.: Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences\u00a042(3), 327\u2013345 (1991) (Preliminary version in FOCS 1987)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"5_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"5_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1137\/060648829","volume":"37","author":"D. Aharonov","year":"2007","unstructured":"Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation. SIAM Journal on Computing\u00a037(1), 47\u201382(electronic) (2007)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/SFCS.2001.959885","volume-title":"Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"B. Barak","year":"2001","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 106\u2013115. IEEE Computer Society, Los Alamitos (2001)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 345\u2013355 (2002)","DOI":"10.1109\/SFCS.2002.1181957"},{"issue":"2","key":"5_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"Brassard, G., Chaum, D., Cr\u00e9peau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences\u00a037(2), 156\u2013189 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01(1), 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"5_CR12","first-page":"21","volume-title":"STOC","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Levin, L., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21\u201331. ACM, New York (1991)"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. In: IEEE Conference on Computational Complexity, pp. 194\u2013203 (2002)","DOI":"10.1109\/CCC.2002.1004355"},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00145-002-0113-0","volume":"16","author":"M. Ben-Or","year":"2003","unstructured":"Ben-Or, M., Gutfreund, D.: Trading help for interaction in statistical zero-knowledge proofs. Journal of Cryptology\u00a016(2), 95\u2013116 (2003)","journal-title":"Journal of Cryptology"},{"key":"5_CR15","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 - CRYPTO \u201988","author":"M. Ben-Or","year":"1990","unstructured":"Ben-Or, M., Goldreich, O., Goldwasser, S., H\u00e5stad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol.\u00a0403, pp. 37\u201356. Springer, Heidelberg (1990)"},{"key":"5_CR16","first-page":"113","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Ben-Or","year":"1988","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 113\u2013131. ACM Press, New York (1988)"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025, 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences\u00a036, 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR20","first-page":"543","volume-title":"FOCS","author":"B. Barak","year":"2005","unstructured":"Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In: FOCS, pp. 543\u2013552. IEEE Computer Society, Los Alamitos (2005)"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM Journal on Computing\u00a036(4), 1119\u20131159(electronic) (2006)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (extended abstract). In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"key":"5_CR23","first-page":"261","volume-title":"FOCS","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player nash equilibrium. In: FOCS, pp. 261\u2013272. IEEE Computer Society, Los Alamitos (2006)"},{"issue":"4","key":"5_CR24","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R. Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM\u00a051(4), 557\u2013594(electronic) (2004)","journal-title":"Journal of the ACM"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: Image Density is complete for non-interactive-SZK. In: Automata, Languages and Programming, 25th International Colloquium, ICALP, pp. 784\u2013795 (1998) (See also preliminary draft of full version, May 1999)","DOI":"10.1007\/BFb0055102"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Goldreich, O., Okamoto, T., Wigderson, A.: Honest verifier vs. dishonest verifier in public coin zero-knowledge proofs. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 325\u2013338. Springer, Heidelberg (1995)","DOI":"10.1007\/3-540-44750-4_26"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/1132516.1132527","volume-title":"STOC 2006","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC 2006. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 71\u201378. ACM, New York (2006)"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Goldreich, O., Wigderson, A.: Hashing functions can simplify zero-knowledge protocol design (too). Technical Report RS-94\u201339, BRICS, November 1994. See Part\u00a01 of [DGOW]","DOI":"10.7146\/brics.v1i39.21604"},{"issue":"6","key":"5_CR29","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory\u00a022(6), 644\u2013654 (1976)","journal-title":"IEEE Transactions on Information Theory"},{"key":"5_CR30","first-page":"255","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC)","author":"G. Crescenzo Di","year":"2000","unstructured":"Di Crescenzo, G., Sakurai, K., Yung, M.: On zero-knowledge proofs: from membership to decision. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 255\u2013264. ACM Press, New York (2000)"},{"issue":"2","key":"5_CR31","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. Journal of the ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"Journal of the ACM"},{"key":"5_CR32","first-page":"429","volume":"5","author":"M. F\u00fcrer","year":"1989","unstructured":"F\u00fcrer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. Advances in Computing Research\u00a05, 429\u2013442 (1989) (Preliminary version in FOCS 1987)","journal-title":"Advances in Computing Research"},{"key":"5_CR33","doi-asserted-by":"crossref","first-page":"327","DOI":"10.2190\/4U1D-VQRM-J70D-JEQF","volume":"5","author":"L. Fortnow","year":"1989","unstructured":"Fortnow, L.: The complexity of perfect zero-knowledge. Advances in Computing Research: Randomness and Computation\u00a05, 327\u2013343 (1989)","journal-title":"Advances in Computing Research: Randomness and Computation"},{"issue":"2","key":"5_CR34","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L. Fortnow","year":"1994","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. Theoretical Computer Science\u00a0134(2), 545\u2013557 (1994)","journal-title":"Theoretical Computer Science"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 1\u20139 (1998)","DOI":"10.1145\/276698.276704"},{"issue":"1","key":"5_CR36","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 Journal on Computing\u00a025(1), 169\u2013192 (1996) (Preliminary version in ICALP 1990)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR37","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF02620137","volume":"6","author":"O. Goldreich","year":"1993","unstructured":"Goldreich, O., Kushilevitz, E.: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology\u00a06, 97\u2013116 (1993)","journal-title":"Journal of Cryptology"},{"issue":"1","key":"5_CR38","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 Journal on Computing\u00a018(1), 186\u2013208 (1989) (Preliminary version in STOC 1985)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"5_CR39","first-page":"691","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM\u00a038(1), 691\u2013729 (1991) (Preliminary version in FOCS 1986)","journal-title":"Journal of the ACM"},{"issue":"1","key":"5_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O. Goldreich","year":"1994","unstructured":"Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. Journal of Cryptology\u00a07(1), 1\u201332 (1994)","journal-title":"Journal of Cryptology"},{"key":"5_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001)"},{"key":"5_CR42","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":"5_CR43","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Honest verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 399\u2013408 (1998)","DOI":"10.1145\/276698.276852"},{"key":"5_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/3-540-48405-1_30","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"O.. Goldreich","year":"1999","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero-knowledge be made non-interactive? or On the relationship of SZK and NISZK. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 467\u2013484. Springer, Heidelberg (1999)"},{"key":"5_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/978-3-540-74208-1_41","volume-title":"APPROX-RANDOM","author":"D.. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Ta-Shma, A.: Worst-case to average-case reductions revisited. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX-RANDOM. LNCS, vol.\u00a04627, pp. 569\u2013583. Springer, Heidelberg (2007)"},{"key":"5_CR46","first-page":"54","volume-title":"IEEE Conference on Computational Complexity","author":"O.. Goldreich","year":"1999","unstructured":"Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In: IEEE Conference on Computational Complexity, pp. 54\u201373. IEEE Computer Society, Los Alamitos (1999)"},{"issue":"4","key":"5_CR47","doi-asserted-by":"crossref","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 Journal on Computing\u00a028(4), 1364\u20131396 (1999) Preliminary versions. In: STOC 1989 and STOC 1990","journal-title":"SIAM Journal on Computing"},{"key":"5_CR48","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC)","author":"I.. Haitner","year":"2007","unstructured":"Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 2007, New York (2007)"},{"key":"5_CR49","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 230\u2013235 (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"key":"5_CR50","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 - CRYPTO \u201987","author":"R.. Impagliazzo","year":"1988","unstructured":"Impagliazzo, R., Yung, M.: Direct minimum-knowledge computations (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol.\u00a0293, pp. 40\u201351. Springer, Heidelberg (1988)"},{"key":"5_CR51","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"issue":"4","key":"5_CR52","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C.. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"key":"5_CR53","unstructured":"Lindell, Y.: Protocols for bounded-concurrent secure two-party computation in the plain model. Chicago Journal of Theoretical Computer Science, pages Article 1, 50 (2006)"},{"key":"5_CR54","first-page":"11","volume-title":"FOCS","author":"M.. Luby","year":"1983","unstructured":"Luby, M., Micali, S., Rackoff, C.: How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In: FOCS, pp. 11\u201321. IEEE, New York (1983)"},{"issue":"4","key":"5_CR55","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S. Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM Journal on Computing\u00a030(4), 1253\u20131298 (2000), Preliminary version in FOCS 1994","journal-title":"SIAM Journal on Computing"},{"key":"5_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-45146-4_17","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"D.. Micciancio","year":"2003","unstructured":"Micciancio, D., Vadhan, S.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 282\u2013298. Springer, Heidelberg (2003)"},{"issue":"2","key":"5_CR57","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M. Naor","year":"1991","unstructured":"Naor, M.: Bit commitment using pseudorandomness. Journal of Cryptology 4(2), 151\u2013158 (1991); Preliminary version In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, Springer, Heidelberg (1990)","journal-title":"Journal of Cryptology"},{"key":"5_CR58","first-page":"3","volume-title":"Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS)","author":"M..-H.. Nguyen","year":"2006","unstructured":"Nguyen, M.-H., Ong, S.J., Vadhan, S.: Statistical zero-knowledge arguments for NP from any one-way function. In: Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), pp. 3\u201314. IEEE Computer Society, Los Alamitos, CA, USA (2006)"},{"key":"#cr-split#-5_CR59.1","doi-asserted-by":"crossref","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. Journal of Cryptology 11(2), 87\u2013108 (1998);","DOI":"10.1007\/s001459900037"},{"key":"#cr-split#-5_CR59.2","unstructured":"Preliminary version In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol.\u00a0740, Springer, Heidelberg (1993)"},{"key":"5_CR60","first-page":"287","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC)","author":"M..-H.. Nguyen","year":"2006","unstructured":"Nguyen, M.-H., Vadhan, S.: Zero knowledge with efficient provers. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 287\u2013295. ACM Press, New York (2006)"},{"issue":"1","key":"5_CR61","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T. Okamoto","year":"2000","unstructured":"Okamoto, T.: On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences, 60(1), 47\u2013108 (2000), Preliminary version in STOC 1996","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR62","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1109\/SCT.1991.160253","volume-title":"Proceedings of the 6th Annual Structure in Complexity Theory Conference","author":"R.. Ostrovsky","year":"1991","unstructured":"Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the 6th Annual Structure in Complexity Theory Conference, pp. 133\u2013138. IEEE Computer Society, Los Alamitos (1991)"},{"key":"5_CR63","series-title":"Lecture Notes in Computer Science","volume-title":"EUROCRYPT 2007","author":"S..J.. Ong","year":"2007","unstructured":"Ong, S.J., Vadhan, S.: Zero knowledge and soundness are symmetric. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol.\u00a04515, Springer, Heidelberg (2007)"},{"key":"5_CR64","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/ISTCS.1993.253489","volume-title":"Proceedings of the 2nd Israel Symposium on Theory of Computing Systems","author":"R.. Ostrovsky","year":"1993","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: Proceedings of the 2nd Israel Symposium on Theory of Computing Systems, pp. 3\u201317. IEEE Computer Society, Los Alamitos (1993)"},{"key":"5_CR65","first-page":"232","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"R.. Pass","year":"2004","unstructured":"Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 232\u2013241. ACM, New York (2004)"},{"key":"5_CR66","first-page":"404","volume-title":"FOCS","author":"R.. Pass","year":"2003","unstructured":"Pass, R., Rosen, A.: Bounded-concurrent secure two-party computation in a constant number of rounds. In: FOCS, p. 404. IEEE Computer Society, Los Alamitos (2003)"},{"key":"5_CR67","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/1060590.1060670","volume-title":"STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing","author":"R.. Pass","year":"2005","unstructured":"Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 533\u2013542. ACM, New York (2005)"},{"key":"5_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/11535218_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"R.. Pass","year":"2005","unstructured":"Pass, R., Shelat, A.: Unconditional characterizations of non-interactive zero-knowledge. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 118\u2013134. Springer, Heidelberg (2005)"},{"issue":"4","key":"5_CR69","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A.. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"5_CR70","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 2nd edn., Boston, MA, USA. Thomson Course Technology (2005)"},{"issue":"2","key":"5_CR71","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A. Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. Journal of the ACM, 50(2), 196\u2013249 (2003), Preliminary version in FOCS 1997","journal-title":"Journal of the ACM"},{"key":"5_CR72","doi-asserted-by":"crossref","unstructured":"Vadhan, S.: Probabilistic proof systems, part I \u2014 interactive & zero-knowledge proofs. In: Rudich, S., Wigderson, A. (eds.) Computational Complexity Theory. American Mathematical Society. IAS\/Park City Mathematics Series, vol.\u00a010 (2004)","DOI":"10.1090\/pcms\/010\/11"},{"issue":"4","key":"5_CR73","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.1137\/S0097539705447207","volume":"36","author":"S.P. Vadhan","year":"2006","unstructured":"Vadhan, S.P.: An unconditional study of computational zero knowledge. SIAM Journal on Computing, 36(4), 1160\u20131214 (2006). Preliminary version in FOCS 2004","journal-title":"SIAM Journal on Computing"},{"key":"5_CR74","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Limits on the power of quantum statistical zero-knowledge. In: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 459 (2002)","DOI":"10.1109\/SFCS.2002.1181970"},{"key":"5_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/11681878_22","volume-title":"Theory of Cryptography","author":"H.. Wee","year":"2006","unstructured":"Wee, H.: Finding Pessiland. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 429\u2013442. Springer, Heidelberg (2006)"},{"key":"5_CR76","first-page":"162","volume-title":"FOCS","author":"A..C..-C.. Yao","year":"1986","unstructured":"Yao, A.C.-C.: How to generate and exchange secrets. In: FOCS. Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 162\u2013167. IEEE Computer Society, Los Alamitos (1986)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:55:58Z","timestamp":1619520958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":77,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}