{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:54:37Z","timestamp":1787500477475,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441472","type":"print"},{"value":"9783540457268","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45726-7_15","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T05:55:49Z","timestamp":1186811749000},"page":"179-193","source":"Crossref","is-referenced-by-count":11,"title":["Randomness-Optimal Characterization of Two NP Proof Systems"],"prefix":"10.1007","author":[{"given":"Alfredo","family":"De Santis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Di Crescenzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,8,23]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic Simulation in Logspace, Proc. of STOC 87.","DOI":"10.1145\/28395.28410"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, and S. Goldwasser, Randomness in Interactive Proof Systems, in Proc. of FOCS 90, pp. 563\u2013572.","DOI":"10.1109\/FSCS.1990.89577"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian and A. Wigderson, Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions, Proc. of STOC 88.","DOI":"10.1145\/62212.62223"},{"key":"15_CR4","unstructured":"M. Blum, Coin Flipping by Telephone, Proc. IEEE Spring COMPCOM (1982), 133\u2013137."},{"issue":"6","key":"15_CR5","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M. Blum","year":"1991","unstructured":"M. Blum, A. De Santis, S. Micali, and G. Persiano, Non-Interactive Zero-Knowledge, SIAM Jou. on Computing, vol. 20, no. 6, Dec 1991, pp. 1084\u20131118.","journal-title":"SIAM Jou. on Computing"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, and S. Micali, Non-Interactive Zero-Knowledge and Applications, Proc. of STOC 88.","DOI":"10.1145\/62212.62222"},{"issue":"4","key":"15_CR7","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali, How to Generate Cryptographically Strong Sequence of Pseudo-Random Bits, SIAM J. on Computing, vol. 13, no. 4, 1984, pp. 850\u2013864.","journal-title":"SIAM J. on Computing"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"J. Boyar and R. Peralta, Short Discreet Proofs, Proc. of EUROCRYPT 96.","DOI":"10.1007\/3-540-68339-9_12"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"B. Chor and O. Goldreich, On the Power of Two-Point Based Sampling, Journal of Complexity, vol. 5, pp. 96\u2013106, 1989.","journal-title":"Journal of Complexity"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"A. Cohen and A. Wigderson, Dispersers, Deterministic Amplification and Weak Random Sources, Proc. of FOCS 89.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano, and A. Sahai, Robust Non-Interactive Zero Knowledge, in Proc. of CRYPTO 2001.","DOI":"10.1007\/3-540-44647-8_33"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"A. De Santis, G. Di Crescenzo, and G. Persiano, Randomness-Efficient Non-Interactive Zero-Knowledge, Proc. of ICALP 97.","DOI":"10.1007\/3-540-63165-8_225"},{"key":"15_CR13","unstructured":"A. De Santis, G. Di Crescenzo, and G. Persiano, Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP, Proc. of ICALP 99."},{"key":"15_CR14","unstructured":"A. De Santis and M. Yung, Cryptographic applications of the meta-proof and the many-prover systems, Proc. of CRYPTO 90."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"C. Dwork and M. Naor, Zaps and Their Applications, Proc. of FOCS 2000.","DOI":"10.1109\/SFCS.2000.892117"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra and M. Szegedy, Approximating Clique is Almost NP-complete, Proc. of FOCS 91.","DOI":"10.1109\/SFCS.1991.185341"},{"issue":"1","key":"15_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U. Feige","year":"1999","unstructured":"U. Feige, D. Lapidot, and A. Shamir, Multiple Non-Interactive Zero-Know ledge Proofs Under General Assumptions, SIAM Jou. on Computing, 29(1), 1999, p. 1\u201328.","journal-title":"SIAM Jou. on Computing"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"U. Feige and A. Shamir, Witness-Indistinguishable and Witness-Hiding Protocols, Proc. of STOC 90.","DOI":"10.1145\/100216.100272"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber and Z. Galil, Explicit Constructions of Linear Sized Superconcentrators, Journal of Computer and System Sciences, vol. 22, pp. 407\u2013420, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR20","unstructured":"Gillman, A Chernoff Bound for Random Walks on Expanders, Proc. of STOC 93."},{"key":"15_CR21","unstructured":"M. Garey e D. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979."},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O. Goldreich","year":"1994","unstructured":"O. Goldreich and Y. Oren, Definitions and Properties of Zero-Knowledge Proof Systems, Journal of Cryptology, vol. 7, 1994, pp. 1\u201332.","journal-title":"Journal of Cryptology"},{"issue":"2","key":"15_CR23","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser, and S. Micali, Probabilistic Encryption, in Journal of Computer and System Sciences, vol. 28, n. 2, 1984, pp. 270\u2013299.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof-Systems, SIAM J. on Computing, vol. 18, n. 1, 1989.","DOI":"10.1137\/0218012"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"J. Hastad, R. Impagliazzo, L. Levin and M. Luby, Construction of A Pseudo-Random Generator from Any One-Way Function, SIAM Jou. on Computing, vol. 28, n. 4, pp. 1364\u20131396.","DOI":"10.1137\/S0097539793244708"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and D. Zuckerman, How to Recycle Random Bits, Proc. of FOCS 89.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"15_CR27","unstructured":"J. Kilian, On the complexity of bounded-interaction and non-interactive zero-knowledge proofs, Proc. of FOCS 94."},{"key":"15_CR28","unstructured":"R. Karp, N. Pippenger, and M. Sipser, Expanders, Randomness, or Time vs. Space, in Proc. of 1st Structures of Complexity Theory, 1986."},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"J. Kilian, and E. Petrank, An efficient zero-knowledge proof system for NP under general assumptions, Journal of Cryptology, vol. 11, n. 1, pp. 1\u201328.","DOI":"10.1007\/s001459900032"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak, Explicit Expanders and the Ramanujan Conjectures, Proc. of STOC 86.","DOI":"10.1145\/12130.12154"},{"key":"15_CR31","unstructured":"M. Naor, Bit Commitment from Pseudo-Randomness, Proc. of CRYPTO 89."},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and A. Wigderson, One-way Functions are Essential for Non-Trivial Zero-knowledge, in Proc. of the 2nd Israel Symposium on Theory of Computing and Systems (ISTCS-93).","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"15_CR33","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"N. Nisan","year":"1991","unstructured":"N. Nisan, Pseudorandom bits for constant depth circuits, Combinatorica, 11, pp. 63\u201370, 1991.","journal-title":"Combinatorica"},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"O. Reingold, S. Vadhan and A. Wigderson, Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors, in Proc. of FOCS 2000.","DOI":"10.1109\/SFCS.2000.892006"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"M. Sipser, A Complexity-Theoretic Aproach to Randomness, in Proc. of STOC 1983.","DOI":"10.1145\/800061.808762"},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"A. Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, in Proc. of FOCS 1999.","DOI":"10.1109\/SFFCS.1999.814628"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, Randomness-Optimal Oblivious Sampling, in Proc. of STOC 97.","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45726-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T03:03:49Z","timestamp":1737342229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45726-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441472","9783540457268"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-45726-7_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}