{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:17:47Z","timestamp":1725488267948},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9780387971964"},{"type":"electronic","value":"9780387347998"}],"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_23","type":"book-chapter","created":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T01:17:36Z","timestamp":1186363056000},"page":"297-310","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Generating Solved Instances of Computational Problems"],"prefix":"10.1007","author":[{"given":"Mart\u00edn","family":"Abadi","sequence":"first","affiliation":[]},{"given":"Eric","family":"Allendert","sequence":"additional","affiliation":[]},{"given":"Andrei","family":"Broder","sequence":"additional","affiliation":[]},{"given":"Joan","family":"Feigenbaum","sequence":"additional","affiliation":[]},{"given":"Lane A.","family":"Hemachandra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,12,1]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. \u201cHow to Generate Cryptographically Strong Sequences of Pseudo-random Bits,\u201d SIAM J. on Comput. (13), 1984, 850\u2013864.","journal-title":"SIAM J. on Comput."},{"key":"23_CR2","unstructured":"R. Boppana and R. Hirschfeld. \u201cPseudorandom Generators and Complexity Classes,\u201d to appear in Advances in Computer Research, Silvio Micali (ed.), JAI Press (pub.), 1987."},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"G. Brassard and C. Cr\u00e9peau. \u201cNon-transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond,\u201d Proceedings of the 27th FOCS, IEEE, 1986, 188\u2013195.","DOI":"10.1109\/SFCS.1986.33"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"G. Brassard and C. Cr\u00e9peau. \u201cZero-Knowledge Simulation of Boolean Circuits,\u201d Advances in Cryptology \u2014 CRYPTO86 Proceedings, Andrew Odlyzko (ed.), Springer-Verlag (pub.), 1987, 223\u2013233.","DOI":"10.1007\/3-540-47721-7_16"},{"key":"23_CR5","unstructured":"G. Brassard, D. Chaum, and C. Cr\u00e9peau. \u201cMinimum Disclosure Proofs of Knowledge,\u201d to appear."},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"U. Feige, A. Fiat, and A. Shamir. \u201cZero Knowledge Proofs of Identity,\u201d Proceedings of the 19th STOC, ACM, 1987, 210\u2013217.","DOI":"10.1145\/28395.28419"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Z. Galil, S. Haber, and M. Yung. \u201cCryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model,\u201d Advances in Crytology \u2014 CRYPTO87 Proceedings, Carl Pomerance (ed.), Springer-Verlag (pub.), 1988, 135\u2013155.","DOI":"10.1007\/3-540-48184-2_10"},{"key":"23_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"23_CR9","first-page":"270","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser and S. Micali. \u201cProbabilistic Encryption,\u201d JCSS (28), 1984, 270\u2013299.","journal-title":"JCSS"},{"key":"23_CR10","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff. \u201cThe Knowledge Complexity of Interactive Proof Systems,\u201d to appear in SIAM J. on Comput."},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. \u201cProofs that Yield Nothing but their Validity and a Method of Cryptographic Protocol Design,\u201d Proceedings of the 27 th FOCS, IEEE, 1986, 174\u2013187.","DOI":"10.1109\/SFCS.1986.47"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. \u201cComplete and Incomplete Randomized NP Problems,\u201d Proceedings of the 28th FOCS, IEEE, 1987, 111\u2013117.","DOI":"10.1109\/SFCS.1987.14"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. \u201cGeneralized Kolmogorov Complexity and the Structure of Feasible Computations,\u201d Proceedings of the 24th FOCS, IEEE, 1983, 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"M. Jerrum, L. Valiant, and V. Vazirani. \u201cRandom Generation of Combinatorial Structures from a Uniform Distribution,\u201d TCS (43), 1986, 169\u2013188.","journal-title":"TCS"},{"key":"23_CR15","first-page":"284","volume":"5","author":"D. Johnson","year":"1984","unstructured":"D. Johnson. \u201cThe NP-Completeness Column, An Ongoing Guide,\u201d JOA (5), 1984, 284\u2013299.","journal-title":"JOA"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"J. Lagarias","year":"1985","unstructured":"J. Lagarias and A. Oldlyzko. \u201cSolving Low-Density Subset Sum Problems,\u201d JACM (32), 1985, 229\u2013246.","journal-title":"JACM"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin. \u201cAverage Case Complete Problems,\u201d SIAM J. on Comput. (15), 1986, 285\u2013286.","journal-title":"SIAM J. on Comput."},{"key":"23_CR18","unstructured":"R. Rardin, C. Tovey, and M. Pilcher. \u201cPolynomial Constructability and Traveling Salesman Problems of Intermediate Complexity,\u201d ONR-URI Computational Combinatorics Report CC-88-2, Purdue University, November, 1988."},{"key":"23_CR19","unstructured":"S. Rudich, private communication."},{"key":"23_CR20","unstructured":"L. Sanchis and M. Fulk. \u201cEfficient Language Instance Generation\u201d, University of Rochester Computer Science Department TR 235, 1988."},{"key":"23_CR21","unstructured":"L. Sanchis. \u201cTest Instance Construction for NP-hard Problems,\u201d University of Rochester Computer Science Department TR 206, 1987."},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"R. Venkatesan and L. Levin. \u201cRandom Instances of a Graph Coloring Problem axe Hard,\u201d Proceedings of the 20th STOC, ACM, 1988, 217\u2013222.","DOI":"10.1145\/62212.62231"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"A. C. Yao. \u201cTheory and Applications of Trapdoor Functions,\u201d Proceedings of the 23rd FOCS, IEEE, 1982, 80\u201391.","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_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T15:27:29Z","timestamp":1576164449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/0-387-34799-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9780387971964","9780387347998"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/0-387-34799-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]},"assertion":[{"value":"1 December 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}