{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:47:45Z","timestamp":1764132465025},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540694052"},{"type":"electronic","value":"9783540694076"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-69407-6_21","type":"book-chapter","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T13:39:35Z","timestamp":1213105175000},"page":"175-185","source":"Crossref","is-referenced-by-count":35,"title":["Succinct NP Proofs from an Extractability Assumption"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Di Crescenzo","sequence":"first","affiliation":[]},{"given":"Helger","family":"Lipmaa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_39","volume-title":"Automata, Languages and Programming","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Bhatt, S.N., Ostrovsky, R., Rajagopalan, S.R.: Fast Verification of Remote procedure Calls: Short Witness-Indistinguishable One-Round Proofs for . In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853. Springer, Heidelberg (2000)"},{"issue":"1","key":"21_CR2","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":"3","key":"21_CR3","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"},{"key":"21_CR4","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":"21_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O.: Universal Arguments and Their Applications. In: Proc. of IEEE Conference on Computational Complexity (2002)","DOI":"10.1109\/CCC.2002.1004355"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. of Mobile Agents 1998","author":"I. Biehl","year":"1998","unstructured":"Biehl, I., Meyer, B., Wetzel, S.: Ensuring the Integrity of Agent-Based Computation by Short Proofs. In: Proc. of Mobile Agents 1998. LNCS. Springer, Heidelberg (1998)"},{"issue":"2","key":"21_CR7","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"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"C. Cachin","year":"1999","unstructured":"Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592. Springer, Heidelberg (1999)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"I. Damg\u00e5rd","year":"1992","unstructured":"Damg\u00e5rd, I.: Towards Practical Public-key Systems Secure against Chosen Ciphertext Attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576. Springer, Heidelberg (1992)"},{"key":"21_CR10","unstructured":"Di Crescenzo, G.: Extractability Complexity Assumptions (August 2006) (unpublished manuscript)"},{"key":"21_CR11","unstructured":"Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct NP Proofs and Spooky Interactions (December 2004) (unpublished manuscript)"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof-Systems. SIAM Journal on Computing\u00a018(1) (1989)","DOI":"10.1137\/0218012"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"C. Gentry","year":"2005","unstructured":"Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580. Springer, Heidelberg (2005)"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","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. Springer, Heidelberg (1998)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on Efficient Zero-knowledge Priifs and Arguments. In: Proc. of ACM STOC 1991 (1991)","DOI":"10.1145\/129712.129782"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single Database, computationally-private information retrieval. In: Proc. of 38th IEEE FOCS 1997 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"21_CR17","unstructured":"Laur, S., Lipmaa, H.: Consistent Adaptive Two-Party Computations, Cryptology ePrint Archive, Report 2006\/088 (2006)"},{"key":"21_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Information Security","author":"H. Lipmaa","year":"2005","unstructured":"Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., L\u00f3pez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol.\u00a03650. Springer, Heidelberg (2005)"},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"R. Merkle","year":"1990","unstructured":"Merkle, R.: A Certified Digital Signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435. Springer, Heidelberg (1990)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS proofs. In: Proc. of 35th IEEE FOCS 1994 (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"2","key":"21_CR21","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00190757","volume":"8","author":"A. Russell","year":"1995","unstructured":"Russell, A.: Necessary and Sufficient Conditions for Collision-Free Hashing. J. Cryptology\u00a08(2), 87\u2013100 (1995)","journal-title":"J. Cryptology"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with Optimal Amortized Query Complexity. In: Proc. of the 32nd ACM STOC 2000 (2000)","DOI":"10.1145\/335305.335329"}],"container-title":["Lecture Notes in Computer Science","Logic and Theory of Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69407-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T08:16:29Z","timestamp":1588752989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69407-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540694052","9783540694076"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69407-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}