{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T11:19:53Z","timestamp":1774523993101,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T00:00:00Z","timestamp":1545004800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["573\/16"],"award-info":[{"award-number":["573\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10623-018-00594-6","type":"journal-article","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T00:52:08Z","timestamp":1545007928000},"page":"1897-1926","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["An algorithmic framework for the generalized birthday problem"],"prefix":"10.1007","volume":"87","author":[{"given":"Itai","family":"Dinur","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,17]]},"reference":[{"key":"594_CR1","unstructured":"Becker A., Coron J., Joux A.: Improved generic algorithms for hard knapsacks. In: Paterson K.G. (ed) Advances in Cryptology\u2014EUROCRYPT 2011\u201430th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15\u201319, 2011. Lecture Notes in Computer Science, vol. 6632, pp. 364\u2013385. Springer, New York (2011)."},{"key":"594_CR2","unstructured":"Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in \n                    \n                      \n                    \n                    $$2^{n\/20}$$\n                    \n                      \n                        \n                          2\n                          \n                            n\n                            \/\n                            20\n                          \n                        \n                      \n                    \n                  : how \n                    \n                      \n                    \n                    $$1 + 1 = 0$$\n                    \n                      \n                        \n                          1\n                          +\n                          1\n                          =\n                          0\n                        \n                      \n                    \n                   improves information set decoding. In: Pointcheval D., Johansson T. (eds.) Advances in Cryptology\u2014EUROCRYPT 2012\u201431st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Lecture Notes in Computer Science, vol. 7237, pp. 520\u2013536. Springer, New York (2012)."},{"key":"594_CR3","unstructured":"Bernstein D.J.: Better price-performance ratios for generalized birthday attacks. In: SHARCS07: Special-Purpose Hardware for Attacking Cryptographic Systems (2007)."},{"key":"594_CR4","unstructured":"Bernstein D.J., Lange T., Niederhagen R., Peters C., Schwabe P.: FSBday. In: Roy B.K., Sendrier N. (eds.) Progress in Cryptology\u2014INDOCRYPT 2009, 10th International Conference on Cryptology in India, New Delhi, India, December 13\u201316, 2009. Lecture Notes in Computer Science, vol. 5922, pp. 18\u201338. Springer, New York (2009)."},{"key":"594_CR5","unstructured":"Biryukov A., Khovratovich D.: Equihash: asymmetric proof-of-work based on the generalized birthday problem. In: 23nd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21\u201324, 2016. The Internet Society (2016)."},{"key":"594_CR6","unstructured":"Canteaut A., Trabbia M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel B. (ed.) Advances in Cryptology\u2014EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14\u201318, 2000. Lecture Notes in Computer Science, vol. 1807, pp. 573\u2013588. Springer, New York (2000)."},{"key":"594_CR7","unstructured":"Dinur I., Dunkelman O., Keller N., Shamir A.: Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology\u2014CRYPTO 2012\u201432nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2012. Lecture Notes in Computer Science, vol. 7417, pp. 719\u2013740. Springer, New York (2012)."},{"key":"594_CR8","unstructured":"Finiasz M., Sendrier N.: Security bounds for the design of code-based cryptosystems. In: Matsui M. (ed.) Advances in Cryptology\u2014ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6\u201310, 2009. Lecture Notes in Computer Science, vol. 5912, pp. 88\u2013105. Springer, New York (2009)."},{"key":"594_CR9","unstructured":"Howgrave-Graham N., Joux A.: New generic algorithms for hard knapsacks. In: Gilbert H. (ed.) Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30\u2013June 3, 2010. Lecture Notes in Computer Science, vol. 6110, pp. 235\u2013256. Springer, New York(2010)."},{"issue":"3","key":"594_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF02252874","volume":"1","author":"W Meier","year":"1989","unstructured":"Meier W., Staffelbach O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159\u2013176 (1989).","journal-title":"J. Cryptol."},{"issue":"2","key":"594_CR11","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00145-011-9097-y","volume":"25","author":"L Minder","year":"2012","unstructured":"Minder L., Sinclair A.: The extended k-tree algorithm. J. Cryptol. 25(2), 349\u2013382 (2012).","journal-title":"J. Cryptol."},{"key":"594_CR12","unstructured":"Nikolic I., Sasaki Y.: Refinements of the k-tree algorithm for the generalized birthday problem. In: Iwata T., Cheon J.H. (eds.) Advances in Cryptology\u2014ASIACRYPT 2015\u201421st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29\u2013December 3, 2015. Lecture Notes in Computer Science, Part II, vol. 9453, pp. 683\u2013703. Springer, New York (2015)."},{"issue":"3","key":"594_CR13","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel R., Shamir A.: \n                    \n                      \n                    \n                    $$\\text{ A } \\text{ T }=\\text{ O }(2^{n\/2})$$\n                    \n                      \n                        \n                          \n                          A\n                          \n                          \n                          T\n                          \n                          =\n                          \n                          O\n                          \n                          (\n                          \n                            2\n                            \n                              n\n                              \/\n                              2\n                            \n                          \n                          )\n                        \n                      \n                    \n                  , \n                    \n                      \n                    \n                    $$\\text{ S }=\\text{ O }(2^{n\/4})$$\n                    \n                      \n                        \n                          \n                          S\n                          \n                          =\n                          \n                          O\n                          \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. 10(3), 456\u2013464 (1981).","journal-title":"SIAM J. Comput."},{"issue":"1","key":"594_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"PC Oorschot van","year":"1999","unstructured":"van Oorschot P.C., Wiener M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1\u201328 (1999).","journal-title":"J. Cryptol."},{"key":"594_CR15","unstructured":"Wagner D.A.: A generalized birthday problem. In: Yung M. (ed.) Advances in Cryptology\u2014CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18\u201322, 2002. Lecture Notes in Computer Science, vol. 2442, pp. 288\u2013303. Springer, New York(2002)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-018-00594-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-018-00594-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-018-00594-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T19:24:10Z","timestamp":1576524250000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-018-00594-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,17]]},"references-count":15,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["594"],"URL":"https:\/\/doi.org\/10.1007\/s10623-018-00594-6","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,17]]},"assertion":[{"value":"2 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}