{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:02Z","timestamp":1775282282862,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540100034","type":"print"},{"value":"9783540393467","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1980]]},"DOI":"10.1007\/3-540-10003-2_71","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:59:11Z","timestamp":1330189151000},"page":"195-207","source":"Crossref","is-referenced-by-count":31,"title":["Cryptocomplexity and NP-completeness"],"prefix":"10.1007","author":[{"given":"S.","family":"Even","sequence":"first","affiliation":[]},{"given":"Y.","family":"Yacobi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W. and Hellman, M.E., \"New Directions in Cryptography\", IEEE Transactions on Information Theory, Vol. 22, 1976, pp. 644\u2013654.","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR2","unstructured":"Brassard, G., Fortune, S., and Hopcroft, J., \"A Note on Cryptography and NP \u2229 CoNP-P\", TR78-338, Dept. of Comp. Sci., Cornell University."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Karp, R.M., \"Reducibility Among Combinatorial Problems\", in R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"18_CR4","unstructured":"Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979."},{"key":"18_CR5","unstructured":"Aho, A.V., Hopcroft, J.E. and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"18_CR6","unstructured":"Even, S., Graph Algorithms, Computer Science Press, 1979."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Lempel, A., \"Cryptology in Transition\", Computing Surveys, December 1979.","DOI":"10.1145\/356789.356792"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A., \"The Complexity of Theorem Proving Procedures\", Proceedings 3rd Am. ACM Symposium on Theory of Computing, ACM, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Rivest, R.L., Shamir, A., and Adleman, L., \"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems\", Comm. ACM 21, February 1978, pp. 120\u2013126.","DOI":"10.1145\/359340.359342"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"IT-24","author":"R. Merkle","year":"1978","unstructured":"Merkle, R., and Hellman, M., \"Hiding Information and Signatures in Trapdoor Knapsack\", IEEE Transactions on Information Theory. Vol. IT-24, September 1978, pp. 525\u2013530.","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/TIT.1979.1056010","volume":"IT-25","author":"G. Brassard","year":"1979","unstructured":"Brassard, G., \"A Note on the Complexity of Cryptography\", IEEE Transactions on Information Theory. Vol. IT-25, March 1979, pp. 232\u2013233.","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR12","unstructured":"Ginsburg, S., private communication."},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(67)90401-9","volume":"11","author":"J. S. Ullian","year":"1967","unstructured":"Ullian, J.S., \"Partial Algorithm Problems for Context Free Languages\". Information and Control, Vol. 11, 1967, pp. 80\u2013101.","journal-title":"Information and Control"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Brassard, G., \"Relativized Cryptography\". Proceedings of 20th FOCS, Puerto Rico 1979.","DOI":"10.1109\/SFCS.1979.36"}],"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-10003-2_71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:02:19Z","timestamp":1605643339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10003-2_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980]]},"ISBN":["9783540100034","9783540393467"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-10003-2_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1980]]}}}