{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:18:45Z","timestamp":1781259525272,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642131899","type":"print"},{"value":"9783642131905","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13190-5_12","type":"book-chapter","created":{"date-parts":[[2010,5,19]],"date-time":"2010-05-19T13:16:46Z","timestamp":1274275006000},"page":"235-256","source":"Crossref","is-referenced-by-count":85,"title":["New Generic Algorithms for Hard Knapsacks"],"prefix":"10.1007","author":[{"given":"Nick","family":"Howgrave-Graham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"12_CR1","first-page":"10","volume-title":"30th ACM STOC","author":"M. Ajtai","year":"1998","unstructured":"Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: 30th ACM STOC, Dallas, Texas, USA, May\u00a023\u201326, pp. 10\u201319. ACM Press, New York (1998)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/3-540-46416-6_3","volume-title":"Advances in Cryptology - EUROCRYPT \u201991","author":"P. Camion","year":"1991","unstructured":"Camion, P., Patarin, J.: The Knapsack hash function proposed at Crypto\u201989 can be broken. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol.\u00a0547, pp. 39\u201353. Springer, Heidelberg (1991)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/3-540-46035-7_14","volume-title":"Advances in Cryptology - EUROCRYPT 2002","author":"P. Chose","year":"2002","unstructured":"Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol.\u00a02332, pp. 209\u2013221. Springer, Heidelberg (2002)"},{"key":"12_CR4","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":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"I. Damg\u00e5rd","year":"1990","unstructured":"Damg\u00e5rd, I.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 416\u2013427. Springer, Heidelberg (1990)"},{"key":"12_CR6","unstructured":"Open problem garden, http:\/\/garden.irmacs.sfu.ca"},{"key":"12_CR7","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. Freeman, San Francisco (1979)"},{"key":"12_CR8","first-page":"169","volume-title":"41st ACM STOC","author":"C. Gentry","year":"2009","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, Bethesda, MD, USA, May 2009, pp. 169\u2013178. ACM Press, New York (2009)"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-01957-9_27","volume-title":"Applied Cryptography and Network Security","author":"P.S. Hirschorn","year":"2009","unstructured":"Hirschorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol.\u00a05536, pp. 437\u2013455. Springer, Heidelberg (2009)"},{"issue":"2","key":"12_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. Assoc. Comp. Mach.\u00a021(2), 277\u2013292 (1974)","journal-title":"J. Assoc. Comp. Mach."},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-74143-5_9","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"N. Howgrave-Graham","year":"2007","unstructured":"Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 150\u2013169. Springer, Heidelberg (2007)"},{"key":"12_CR12","unstructured":"Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks, eprint.iacr.org or www.joux.biz\/publications\/Knapsacks.pdf"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology\u00a09(4), 199\u2013216 (1996)","journal-title":"Journal of Cryptology"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/BFb0053424","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"A. Joux","year":"1994","unstructured":"Joux, A., Granboulan, L.: A practical attack against knapsack based hash functions (extended abstract). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol.\u00a0950, pp. 58\u201366. Springer, Heidelberg (1994)"},{"issue":"1","key":"12_CR15","doi-asserted-by":"crossref","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. Assoc. Comp. Mach.\u00a032(1), 229\u2013246 (1985)","journal-title":"J. Assoc. Comp. Mach."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann.\u00a0261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-71039-4_4","volume-title":"Fast Software Encryption","author":"V. Lyubashevsky","year":"2008","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Swifft: A modest proposal for fft hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol.\u00a05086, pp. 54\u201372. Springer, Heidelberg (2008)"},{"issue":"5","key":"12_CR18","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"24","author":"R. Merkle","year":"1978","unstructured":"Merkle, R., Hellman, M.: Hiding information and signatures in trapdoor knapsacks. IEEE Trans. Information Theory\u00a024(5), 525\u2013530 (1978)","journal-title":"IEEE Trans. Information Theory"},{"key":"12_CR19","first-page":"331","volume":"20","author":"P.Q. Nguyen","year":"2001","unstructured":"Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. Progress in Computer Science and Applied Logic\u00a020, 331\u2013342 (2001); Final Proceedings of Cryptography and Computational Number Theory workshop, Singapore (1999)","journal-title":"Progress in Computer Science and Applied Logic"},{"key":"12_CR20","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. Theoretical Computer Science\u00a053, 201\u2013224 (1987)","journal-title":"Theoretical Computer Science"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Schroeppel, R., Shamir, A.: A T\u2009=\u2009O(2 n\/2), S\u2009=\u2009O(2 n\/4) algorithm for certain NP-complete problems. In: FOCS, pp. 328\u2013336 (1979)","DOI":"10.1109\/SFCS.1979.3"},{"issue":"3","key":"12_CR22","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\/2), S\u2009=\u2009O(2 n\/4) algorithm for certain NP-complete problems. SIAM Journal on Computing\u00a010(3), 456\u2013464 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR23","first-page":"279","volume-title":"Advances in Cryptology \u2013 CRYPTO 1982","author":"A. Shamir","year":"1983","unstructured":"Shamir, A.: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology \u2013 CRYPTO 1982, Santa Barbara, CA, USA, pp. 279\u2013288. Plenum Press, New York (1983)"},{"issue":"237","key":"12_CR24","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1090\/S0025-5718-01-01310-2","volume":"71","author":"D.R. Stinson","year":"2002","unstructured":"Stinson, D.R.: Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. Math. Comput.\u00a071(237), 379\u2013391 (2002)","journal-title":"Math. Comput."},{"key":"12_CR25","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 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13190-5_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T23:18:23Z","timestamp":1740093503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13190-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131899","9783642131905"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13190-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}