{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:49:56Z","timestamp":1772725796662,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T00:00:00Z","timestamp":1539561600000},"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":["J Cryptol"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00145-018-9304-1","type":"journal-article","created":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T16:20:20Z","timestamp":1539620420000},"page":"35-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem"],"prefix":"10.1007","volume":"32","author":[{"given":"Shi","family":"Bai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7114-8377","authenticated-orcid":false,"given":"Steven D.","family":"Galbraith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liangze","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Sheffield","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,10,15]]},"reference":[{"key":"9304_CR1","unstructured":"Y. Arbitman, G. Dogon, V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen, SWIFFTX: A proposal for the SHA-3 standard. Submitted to NIST SHA-3 competition"},{"key":"9304_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, Generating hard instances of lattice problems, electronic colloquium on computational complexity (ECCC), TR96-007 (1996)","DOI":"10.1145\/237814.237838"},{"key":"9304_CR3","unstructured":"N. Bansal, S. Garg, J. Nederlof, N. Vyas, Faster space-efficient algorithms for subset sum and k-sum, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 (2017), pp. 198\u2013209"},{"key":"9304_CR4","doi-asserted-by":"crossref","unstructured":"A. Becker, J.-S. Coron, A. Joux, Improved generic algorithms for hard knapsacks, in K. G. Paterson (ed.), EUROCRYPT 2011. LNCS, 6632 (Springer, 2011), pp. 364\u2013385","DOI":"10.1007\/978-3-642-20465-4_21"},{"key":"9304_CR5","unstructured":"D.J. Bernstein, Better price-performance ratios for generalized birthday attacks, in Workshop Record of SHARCS07, (2007). \n                    http:\/\/cr.yp.to\/papers.html#genbday"},{"key":"9304_CR6","doi-asserted-by":"crossref","unstructured":"D.J. Bernstein, T. Lange, R. Niederhagen, C. Peters, P. Schwabe, FSBday: Implementing Wagner\u2019s generalized birthday attack against the SHA-3 round-1 candidate FSB, in B.K. Roy and N. Sendrier (eds.), INDOCRYPT 2009. LNCS, 5922 (Springer, 2009), pp. 18\u201338","DOI":"10.1007\/978-3-642-10628-6_2"},{"key":"9304_CR7","unstructured":"J. Buchmann, R. Lindner, Secure parameters for SWIFFT, in B. Roy and N. Sendrier (eds.), INDOCRYPT 2009. LNCS, 5922 (2009), pp. 1\u201317"},{"key":"9304_CR8","doi-asserted-by":"crossref","unstructured":"P. Camion, J. Patarin, The knapsack hash function proposed at Crypto\u201989 can be broken, in D.W. Davies (ed.), EUROCRYPT 1991. LNCS, 547 (Springer, 1991), pp. 39\u201353","DOI":"10.1007\/3-540-46416-6_3"},{"key":"9304_CR9","unstructured":"T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to algorithms, 2nd ed., (MIT press, 2001)"},{"key":"9304_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"Matthijs J Coster","year":"1992","unstructured":"M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.-P. Schnorr, J. Stern, Improved low-density subset sum algorithms. Comput. Complex., 2, 111\u2013128, (1992)","journal-title":"Computational Complexity"},{"key":"9304_CR11","doi-asserted-by":"crossref","unstructured":"I. Dinur, O. Dunkelman, N. Keller, A. Shamir, Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems, in R. Safavi-Naini and R. Canetti, CRYPTO 2012. LNCS, 7417 (Springer, 2012), pp. 719\u2013740.","DOI":"10.1007\/978-3-642-32009-5_42"},{"key":"9304_CR12","doi-asserted-by":"crossref","unstructured":"M. Finiasz, N. Sendrier, Security bounds for the design of code-based cryptosystems, In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Heidelberg, 2009), pp. 88105","DOI":"10.1007\/978-3-642-10366-7_6"},{"key":"9304_CR13","doi-asserted-by":"crossref","unstructured":"N. Gama, M. Izabach\u00e8ne, P.Q. Nguyen, X. Xie, Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic cryptosystems. EUROCRYPT (2), 528\u2013558 (2016)","DOI":"10.1007\/978-3-662-49896-5_19"},{"key":"9304_CR14","unstructured":"N. Howgrave-Graham, J.H. Silverman, W. Whyte, A meet-in-the-middle attack on an NTRU private key, Technical Report 004, NTRU Cryptosystems, June 2003"},{"key":"9304_CR15","doi-asserted-by":"crossref","unstructured":"N. Howgrave-Graham, A. Joux, New generic algorithms for hard knapsacks, in H. Gilbert (ed.), EUROCRYPT 2010. LNCS, 6110 (Springer, 2010), pp. 235\u2013256","DOI":"10.1007\/978-3-642-13190-5_12"},{"key":"9304_CR16","unstructured":"N. Howgrave-Graham, A. Joux, New Generic Algorithms for Hard Knapsacks (preprint), 17 pages (undated). Available from \n                    www.joux.biz\/publications\/Knapsacks.pdf"},{"key":"9304_CR17","doi-asserted-by":"crossref","unstructured":"N. Howgrave-Graham, A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU, in A. Menezes (ed.), CRYPTO 2007. LNCS, 4622 (Springer, 2007), pp. 150\u2013169.","DOI":"10.1007\/978-3-540-74143-5_9"},{"issue":"1","key":"9304_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"Jeffrey C Lagarias","year":"1985","unstructured":"J.C. Lagarias, A.M. Odlyzko, Solving low-density subset sum problems. J. ACM\n                           32(1), 229\u2013246 (1985)","journal-title":"J. ACM"},{"key":"9304_CR19","unstructured":"P. Kirchner, Improved generalized birthday attack, cryptology ePrint Archive: Report 2011\/377 (2011)"},{"key":"9304_CR20","unstructured":"V. Lyubashevsky, On random high density subset sums, electronic colloquium on computational complexity (ECCC) 007 (2005)"},{"key":"9304_CR21","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen, SWIFFT: A modest proposal for FFT hashing, in K. Nyberg (ed.), FSE 2008. LNCS, 5086 (Springer, 2008), pp. 54\u201372","DOI":"10.1007\/978-3-540-71039-4_4"},{"key":"9304_CR22","unstructured":"D. Micciancio, Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions, electronic colloquium on computational complexity (ECCC), No. 095 (2004)"},{"key":"9304_CR23","doi-asserted-by":"crossref","unstructured":"D. Micciancio, C. Peikert, Hardness of SIS and LWE with Small Parameters, in R. Canetti and J. A. Garay (eds.), CRYPTO 2013. LNCS, 8042 (Springer , 2013), pp. 21\u201339","DOI":"10.1007\/978-3-642-40041-4_2"},{"key":"9304_CR24","doi-asserted-by":"crossref","unstructured":"D. Micciancio, O. Regev, Lattice-based cryptography, in D.\u00a0J. Bernstein, J.\u00a0Buchmann and E.\u00a0Dahmen (eds.), Post quantum cryptography, (Springer, 2009), pp. 147\u2013191","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"9304_CR25","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00145-011-9097-y","volume":"25","author":"Lorenz Minder","year":"2012","unstructured":"L. Minder, A. Sinclair, The extended k-tree algorithm. J. Cryptol.\n                           25, 349\u2013382 (2012)","journal-title":"J. Cryptol."},{"key":"9304_CR26","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"3","author":"Richard Schroeppel","year":"1981","unstructured":"R. Schroeppel, A. Shamir, A \n                    \n                      \n                    \n                    $$T=O(2^{n\/2})$$\n                    \n                      \n                        \n                          T\n                          =\n                          O\n                          (\n                          \n                            2\n                            \n                              n\n                              \/\n                              2\n                            \n                          \n                          )\n                        \n                      \n                    \n                  , \n                    \n                      \n                    \n                    $$S=O(2^{n\/4})$$\n                    \n                      \n                        \n                          S\n                          =\n                          O\n                          (\n                          \n                            2\n                            \n                              n\n                              \/\n                              4\n                            \n                          \n                          )\n                        \n                      \n                    \n                   algorithm for certain NP-complete problems. SIAM J. Comput.\n                           3, 456\u2013464 (1981)","journal-title":"SIAM J. Comput. No."},{"key":"9304_CR27","doi-asserted-by":"crossref","unstructured":"A. Shallue, An Improved Multi-set Algorithm for the Dense Subset Sum Problem, in A.J. van der Poorten and A. Stein (eds.), ANTS 2008. LNCS, 5011 (Springer, 2008), pp. 416\u2013429","DOI":"10.1007\/978-3-540-79456-1_28"},{"key":"9304_CR28","doi-asserted-by":"crossref","unstructured":"D. Wagner, A Generalized Birthday Problem, in M.\u00a0Yung (ed.), CRYPTO 2002, LNCS. 2442 (Springer, 2002), pp. 288\u2013303","DOI":"10.1007\/3-540-45708-9_19"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-018-9304-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9304-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9304-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:09:35Z","timestamp":1586333375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-018-9304-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,15]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["9304"],"URL":"https:\/\/doi.org\/10.1007\/s00145-018-9304-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,15]]},"assertion":[{"value":"27 November 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}