{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:26:16Z","timestamp":1737523576044,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_28","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"334-345","source":"Crossref","is-referenced-by-count":7,"title":["On Interactive Proofs with a Laconic Prover"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"issue":"3","key":"28_CR1","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0022-0000(91)90006-Q","volume":"42","author":"W. Aiello","year":"1991","unstructured":"William Aiello and Johan H\u00e5stad. Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences, 42(3):327\u2013345, June 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BFb0058034","volume-title":"Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"V. Arvind","year":"1997","unstructured":"V. Arvind and J. K\u00f6bler. On resource-bounded measure and pseudorandomness. In Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 235\u2013249. LNCS 1346, Springer-Verlag, 1997."},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 421\u2013429, Providence, Rhode Island, 6-8 May 1985.","DOI":"10.1145\/22145.22192"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L\u00e1szl\u00f3 Babai and Shlomo Moran. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"28_CR5","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and Nonapproximability\u2014towards tight results. SIAM Journal on Computing, 27(3):804\u2013915 (electronic), 1998.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. B. Boppana","year":"1987","unstructured":"Ravi B. Boppana, Johan H\u00e5stad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"issue":"2","key":"28_CR7","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"Gilles Brassard, David Chaum, and Claude Cr\u00e9peau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156\u2013189, October 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR8","unstructured":"Lance Fortnow. The complexity of perfect zero-knowledge. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 327\u2013343. JAC Press, Inc., 1989."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. Modern Cryptography, Probabilistic Proofs, and Pseudorandomness. Number 17 in Algorithms and Combinatorics. Springer-Verlag, 1999.","DOI":"10.1007\/978-3-662-12521-2"},{"issue":"3","key":"28_CR10","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1006\/jcss.1999.1686","volume":"60","author":"O. Goldreich","year":"2000","unstructured":"Oded Goldreich and Shafi Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540\u2013563, 2000.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"28_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"O. Goldreich","year":"1998","unstructured":"Oded Goldreich and Johan H\u00e5stad. On the complexity of interactive proofs with bounded communication. Information Processing Letters, 67(4):205\u2013214, 1998.","journal-title":"Information Processing Letters"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF02620137","volume":"6","author":"O. Goldreich","year":"1993","unstructured":"Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6:97\u2013116, 1993.","journal-title":"Journal of Cryptology"},{"issue":"1","key":"28_CR13","first-page":"691","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(1):691\u2013729, 1991.","journal-title":"Journal of the ACM"},{"issue":"4","key":"28_CR14","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1137\/S0097539795280524","volume":"27","author":"O. Goldreich","year":"1998","unstructured":"Oded Goldreich, Rafail Ostrovsky, and Erez Petrank. Computational complexity and knowledge complexity. SIAM Journal on Computing, 27(4):1116\u20131141, August 1998.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"28_CR15","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/s000370050019","volume":"8","author":"O. Goldreich","year":"1999","unstructured":"Oded Goldreich and Erez Petrank. Quantifying knowledge complexity. Computational Complexity, 8(1):50\u201398, 1999.","journal-title":"Computational Complexity"},{"issue":"1","key":"28_CR16","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186\u2013208, February 1989.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR17","unstructured":"Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 73\u201390. JAC Press, Inc., 1989."},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 723\u2013732, Victoria, British Columbia, Canada, 4-6 May 1992.","DOI":"10.1145\/129712.129782"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pages 659\u2013667, Atlanta, 1-4 May 1999.","DOI":"10.1145\/301250.301428"},{"issue":"4","key":"28_CR20","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859\u2013868, October 1992.","journal-title":"Journal of the ACM"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen and N.V. Vinodchandran. Derandomizing Arthur-Merlin games using hitting sets. In 40th Annual Symposium on Foundations of Computer Science, New York, NY, 17-19 October 1999. IEEE.","DOI":"10.1109\/SFFCS.1999.814579"},{"issue":"1","key":"28_CR22","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T. Okamoto","year":"2000","unstructured":"Tatsuaki Okamoto. On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences, 60(1):47\u2013108, February 2000.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Erez Petrank and G\u00e1bor Tardos. On the knowledge complexity of NP. In 37th Annual Symposium on Foundations of Computer Science, pages 494\u2013503, Burlington, Vermont, 14-16 October 1996. IEEE.","DOI":"10.1109\/SFCS.1996.548508"},{"key":"28_CR24","doi-asserted-by":"crossref","unstructured":"Amit Sahai and Salil P. Vadhan. A complete promise problem for statistical zero-knowledge. In 38th Annual Symposium on Foundations of Computer Science, pages 448\u2013457, Miami Beach, Florida, 20-22 October 1997. IEEE.","DOI":"10.1109\/SFCS.1997.646133"},{"issue":"4","key":"28_CR25","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869\u2013877, October 1992.","journal-title":"Journal of the ACM"},{"key":"28_CR26","unstructured":"Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997."},{"key":"28_CR27","volume-title":"Applied combinatorics","author":"A. Tucker","year":"1995","unstructured":"Alan Tucker. Applied combinatorics. John Wiley & Sons Inc., New York, third edition, 1995.","edition":"third edition"},{"key":"28_CR28","unstructured":"Salil Vadhan. Probabilistic proof systems I: Interactive and zero-knowledge proofs. Lecture Notes from the IAS\/PCMI Graduate Summer School on Computational Complexity, August 2000. Available from http:\/\/eecs.harvard.edu\/~salil\/ ."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:04Z","timestamp":1737503404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}