{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T17:45:26Z","timestamp":1775756726327,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642204647","type":"print"},{"value":"9783642204654","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20465-4_21","type":"book-chapter","created":{"date-parts":[[2011,5,2]],"date-time":"2011-05-02T14:42:47Z","timestamp":1304347367000},"page":"364-385","source":"Crossref","is-referenced-by-count":58,"title":["Improved Generic Algorithms for Hard Knapsacks"],"prefix":"10.1007","author":[{"given":"Anja","family":"Becker","sequence":"first","affiliation":[]},{"given":"Jean-S\u00e9bastien","family":"Coron","sequence":"additional","affiliation":[]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in \n                    \n                      \n                    \n                    $\\mbox{L}_2$\n                   is NP-hard for randomized reductions (extended abstract). In: STOC 1998, pp. 10\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. Eprint archive (2011)","DOI":"10.1007\/978-3-642-20465-4_21"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"M.J. Coster","year":"1992","unstructured":"Coster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.-P., Stern, J.: Improved low-density subset sum algorithms. Computational Complexity\u00a02, 111\u2013128 (1992)","journal-title":"Computational Complexity"},{"key":"21_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-13190-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"N. Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 235\u2013256. Springer, Heidelberg (2010)"},{"key":"21_CR6","series-title":"Seminumerical Algorithms","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1981","unstructured":"Knuth, D.E.: The Art of Computer Programming, 2nd edn. Seminumerical Algorithms, vol.\u00a0II. Addison-Wesley, Reading (1981)","edition":"2"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"J.C. Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM\u00a032(1), 229\u2013246 (1985)","journal-title":"J. ACM"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261, 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"21_CR9","unstructured":"May, A., Meurer, A.: Personal communication"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"24","author":"R.C. Merkle","year":"1978","unstructured":"Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory\u00a024, 525\u2013530 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Progress in Computer Science and Applied Logic, Final Proceedings of Cryptography and Computational Number Theory Workshop, Singapore, vol. 20, pp. 331\u2013224 (2001)","DOI":"10.1007\/978-3-0348-8295-8_24"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci.\u00a053, 201\u2013224 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR13","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T\u2009=\u2009O(2\n                    n\/2), S\u2009=\u2009O(2\n                    n\/4) algorithm for certain NP-complete problems. SIAM J. Comput.\u00a010(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Shamir, A.: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In: CRYPTO 1982, pp. 279\u2013288 (1982)","DOI":"10.1007\/978-1-4757-0602-4_27"},{"key":"21_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-68697-5_18","volume-title":"Advances in Cryptology - CRYPTO \u201996","author":"P.C. Oorschot van","year":"1996","unstructured":"van Oorschot, P.C., Wiener, M.J.: Improving implementable meet-in-the-middle attacks by orders of magnitude. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol.\u00a01109, pp. 229\u2013236. Springer, Heidelberg (1996)"},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology - CRYPTO 2002","author":"D. Wagner","year":"2002","unstructured":"Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.\u00a02442, pp. 288\u2013303. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20465-4_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:58:18Z","timestamp":1606186698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20465-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642204647","9783642204654"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20465-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}