{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T23:56:55Z","timestamp":1768435015291,"version":"3.49.0"},"publisher-location":"New York, NY","reference-count":26,"publisher":"Springer New York","isbn-type":[{"value":"9780387971964","type":"print"},{"value":"9780387347998","type":"electronic"}],"license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/0-387-34799-2_2","type":"book-chapter","created":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T01:17:36Z","timestamp":1186363056000},"page":"8-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":67,"title":["Limits on the Provable Consequences of One-way Permutations"],"prefix":"10.1007","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[]},{"given":"Steven","family":"Rudich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,12,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P=NP question. SIAM J. Comp., 4 (1975) pp. 431\u2013442.","journal-title":"SIAM J. Comp."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"C. H. Bennett and J. Gill. Relative to a random oracle A, P AneNP AneCo \u2014 NP A with probability 1. SIAM J. Comp. 10 (1981)","DOI":"10.1137\/0210008"},{"key":"2_CR3","series-title":"Technical Report","volume-title":"Minimum disclosure proofs of knowledge","author":"G. Brassard","year":"1987","unstructured":"G. Brassard, D. Chaum, and C. Cr\u00e9peau. Minimum disclosure proofs of knowledge. Technical Report PM-RS710, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands, 1987."},{"key":"2_CR4","unstructured":"J. Cohen Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, Sept 1987. YALEU\/DCS\/TR-561."},{"key":"2_CR5","volume-title":"Three applications of the oblivious transfer: Part i: Coin flipping by telephone; part ii: How to exchange secrets; part iii: How to send certified electronic mail","author":"M. Blum","year":"1981","unstructured":"M. Blum. Three applications of the oblivious transfer: Part i: Coin flipping by telephone; part ii: How to exchange secrets; part iii: How to send certified electronic mail. Department of EECS, University of California, Berkeley, CA, 1981."},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"M. Blum. Coin flipping by telephone: A protocol for solving impossible problems. In Proceedings of the 24th IEEE Computer Conference (Com-pCon), pages 133\u2013137, 1982. reprinted in SIGACT News, vol. 15, no. 1, 1983, pp. 23\u201327.","DOI":"10.1145\/1008908.1008911"},{"key":"2_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 sequences of pseudo-random bits. SIAM J. Comp. 13 (1984) pp. 850\u2013864","journal-title":"SIAM J. Comp."},{"key":"2_CR8","series-title":"Technical Report","first-page":"54","volume-title":"Advances in Cryptography, a Report on CRYPTO 81","author":"G. Brassard","year":"1982","unstructured":"G. Brassard. An optimally secure relativized cryptosystem. Advances in Cryptography, a Report on CRYPTO 81, Technical Report no. 82-04, Department of ECE, University of California, Santa Barbara, CA, 1982, pp. 54\u201358; reprinted in SIGACT News vol. 15, no. 1, 1983, pp. 28\u201333."},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","volume":"IT-19","author":"G. Brassard","year":"1983","unstructured":"G. Brassard. Relativized cryptography. IEEE Transactions on Information Theory, IT-19:877\u2013894, 1983.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"A.K. Chandra, D. Kozen, and L. Stockmeyer. Alternation. JACM, 28:114\u2013133, 1981.","journal-title":"JACM"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"IT-22","author":"W. Diffie","year":"1976","unstructured":"W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22:644\u2013654, 1976.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"U. Feige, A. Fiat and A. Shamir. Zero-knowledge proofs of identity. STOC, 1987.","DOI":"10.1145\/28395.28419"},{"key":"2_CR13","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. In Proceedings of the 25th Annual Foundations of Computer Science. ACM, 1984."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for proto cols with honest majority. In Proceedings of the 19th Annual Symposium on Theory of Computing. ACM, 1987.","DOI":"10.1145\/28395.28420"},{"key":"2_CR15","first-page":"270","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser and S. Micali. Probabalistic Encryption. JCSS, 28:270\u2013299, 1984.","journal-title":"JCSS"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali, and R. Rivest. A \u201cparadoxical\u201d solution to the signature problem. In Proceedings of the 25th Annual Foundations of Computer Science. ACM, 1984.","DOI":"10.1109\/SFCS.1984.715946"},{"key":"2_CR17","unstructured":"R. Impagliazzo Proofs that relativize, and proofs that do not. Unpublished manuscript, 1988."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Yung. Direct minimum-knowledge computations. In Proceedings of Advances in Cryptography. CRYPTO, 1987.","DOI":"10.1007\/3-540-48184-2_4"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"Mark Jerrum, Leslie Valiant, and Vijay Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169\u2013188, 1986.","journal-title":"Theoretical Computer Science"},{"key":"2_CR20","unstructured":"M. Luby and C. Rackoff. How to construct pseudo-random permutations from pseudo-random functions. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986."},{"issue":"4","key":"2_CR21","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/359460.359473","volume":"21","author":"R. C. Merkle","year":"1978","unstructured":"R. C. Merkle. Secure communications over insecure channels. CACM, 21(4):294\u2013299, April 1978.","journal-title":"CACM"},{"key":"2_CR22","unstructured":"M. Naor and M. Yung. Universal One-Way Hash Functions and Their Applications. These precedings."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1145\/361082.361089","volume":"17","author":"G. P. Purdy","year":"1974","unstructured":"G. P. Purdy A high security log-in procedure. CACM, 17:442\u2013445, 1974.","journal-title":"CACM"},{"key":"2_CR24","unstructured":"M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard University, 1981."},{"key":"2_CR25","unstructured":"C. Rackoff. A basic theory of public and private cryptosystems. Crypto"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"A.C. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 80\u201391. IEEE, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO\u2019 88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/0-387-34799-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T16:53:13Z","timestamp":1587833593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/0-387-34799-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9780387971964","9780387347998"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/0-387-34799-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990]]},"assertion":[{"value":"1 December 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}