{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:26:18Z","timestamp":1769297178998,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540677154","type":"print"},{"value":"9783540450221","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_39","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"463-474","source":"Crossref","is-referenced-by-count":38,"title":["Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP"],"prefix":"10.1007","author":[{"given":"William","family":"Aiello","sequence":"first","affiliation":[]},{"given":"Sandeep","family":"Bhatt","sequence":"additional","affiliation":[]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[]},{"given":"S. Raj.","family":"Rajagopalan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"A. Ambainis. Upper bound on the communication complexity of private information retrieval. In Proc. of 24th ICALP, 1997.","DOI":"10.1007\/3-540-63165-8_196"},{"issue":"3","key":"39_CR2","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501\u2013555, May 1998.","journal-title":"Journal of the ACM"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin and M. Szegedy Checking computations in polylogarithmic time. In Proc. of the 23rd Annual ACM Symposium on the Theory of Computing, pp. 21\u201331, 1991.","DOI":"10.1145\/103418.103428"},{"key":"39_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BFb0057658","volume-title":"Mobile Agents\u2019 98","author":"I. Biehl","year":"1998","unstructured":"I. Biehl and B. Meyer and S. Wetzel. Ensuring the Integrity of Agent-Based Computation by Short Proofs. Mobile Agents\u2019 98, Kurt Rothermel and Fritz Hohl, editors, Lecture Notes in Computer Science, Vol. 1477, 1998, Springer-Verlag, pp. 183\u2013194."},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proc. of 36th FOCS, pages 41\u201350, 1995. Journal version to appear in JACM.","DOI":"10.1109\/SFCS.1995.492461"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology: Proceedings of EUROCRYPT99, 1999.","DOI":"10.1007\/3-540-48910-X_28"},{"key":"39_CR7","unstructured":"C. Dwork and M. Naor Zaps and Apps talk given at DIMACS Workshop on Cryptography and Intractability March 20\u201322, 2000 DIMACS Center, Rutgers University, Piscataway, NJ."},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for database private information retrieval. In Proc. of the 17th Annu. ACM Symp. on Principles of Distributed Computing, pages 91\u2013100, 1998.","DOI":"10.1145\/277697.277713"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo, T. Malkin, and R. Ostrovsky. Single-database private information retrieval implies oblivious transfer. In Advances in Cryptology-EUROCRYPT 2000, 2000.","DOI":"10.1007\/3-540-45539-6_10"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, Two Prover Protocols: low error at affordable rates. In Proc of Annual ACM Symposium on the Theory of Computing, 1994 pp. 172\u2013183.","DOI":"10.1145\/195058.195128"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"U. Feige and A. Shamir, Witness Indistinguishable and Witness Hiding Protocols. In Proc. of Annual ACM Symposium on the Theory of Computing 1990, pages 416\u2013426.","DOI":"10.1145\/100216.100272"},{"key":"39_CR12","unstructured":"F. Erg\u00fcn, S Kumar, and R. Rubinfeld. Fast pcps for approximations. FOCS 1999."},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin Protecting data privacy in private information retrieval schemes. In Proc. of the 30th Annual ACM Symposium on the Theory of Computing, pp. 151\u2013160, 1998.","DOI":"10.1145\/276698.276723"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 1\u201310, El Paso, Texas, 4\u20136 May 1997.","DOI":"10.1145\/258533.258536"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"J. Kilian Zero-Knowledge with Logspace Verifiers. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pages 25\u201335, El Paso, Texas, 4\u20136 May 1997.","DOI":"10.1109\/SFCS.1988.21918"},{"key":"39_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/3-540-44750-4_25","volume-title":"Proc. of CRYPTO","author":"J. Kilian","year":"1995","unstructured":"J. Kilian Improved Efficient Arguments In Proc. of CRYPTO Springer LNCS 963:311\u2013324, 1995"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"J. Kilian, E. Petrank, and G. Tardos. Probabilistic Checkable Proofs with Zero Knowledge. In 29th ACM Symp. on Theory of Computation, May 1997.","DOI":"10.1145\/258533.258643"},{"key":"39_CR18","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky Replication is not needed: Single Database, computationally-private information retrieval. In Proc. of Thirty-Eight Foundations of Computer Science pp. 364\u2013373, 1997.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. One-way Trapdoor Permutations are Sufficient for Non-Trivial Single-Database Computationally-Private Information Retrieval. In Proc. of EUROCRYPT\u2019 00, 2000.","DOI":"10.1007\/3-540-45539-6_9"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"S. Micali. CS proofs (extended abstracts). In 35th Annual Symposium on Foundations of Computer Science, pages 436\u2013453, Santa Fe, New Mexico, 20\u201322 1994. IEEE.","DOI":"10.1109\/SFCS.1994.365746"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation. In Proceedings of the 31st Annual Symposium on Theory of Computing. ACM, pp. 33\u201343, 1999.","DOI":"10.1145\/301250.301312"},{"key":"39_CR22","doi-asserted-by":"crossref","unstructured":"A. Polishchuk and D. Spielman Nearly-linear Size Holographic Proofs In Proceedings of the 25st Annual Symposium on Theory of Computing. ACM, pp. 194\u2013203, 1994.","DOI":"10.1145\/195058.195132"},{"key":"39_CR23","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"R. Raz A Parallel Repetition Theorem SIAM J. Computing Vol. 27, No. 3, pp. 763\u2013803, June 1998.","journal-title":"SIAM J. Computing"},{"key":"39_CR24","unstructured":"B.S. Yee. A Sanctuary For Mobile Agents. Proceedings of the DARPA Workshop on Foundations for Secure Mobile Code. March, 1997."},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"A.C. Yao. Theory and Applications of Trapdoor Functions In 23rd Annual Symposium on Foundations of Computer Science pages 80\u201391, Chicago, Illinois, 3\u20135 November 1982. IEEE.","DOI":"10.1109\/SFCS.1982.45"}],"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-45022-X_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T09:03:12Z","timestamp":1737536592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_39","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}