{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:51:15Z","timestamp":1742921475396,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662487990"},{"type":"electronic","value":"9783662488003"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48800-3_28","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T12:12:21Z","timestamp":1448539941000},"page":"683-703","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Refinements of the k-tree Algorithm for the Generalized Birthday Problem"],"prefix":"10.1007","author":[{"given":"Ivica","family":"Nikoli\u0107","sequence":"first","affiliation":[]},{"given":"Yu","family":"Sasaki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,30]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 6\u20138 July 2001, pp. 601\u2013610. ACM, Heraklion (2001)","DOI":"10.1145\/380752.380857"},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/3-540-69053-0_13","volume-title":"Advances in Cryptology - EUROCRYPT 1997","author":"M Bellare","year":"1997","unstructured":"Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: incrementality at reduced cost. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 163\u2013192. Springer, Heidelberg (1997)"},{"key":"28_CR3","unstructured":"Bernstein, D.: CAESAR Competition (2013). http:\/\/competitions.cr.yp.to\/caesar.html"},{"issue":"233","key":"28_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1090\/S0025-5718-00-01219-9","volume":"70","author":"DJ Bernstein","year":"2001","unstructured":"Bernstein, D.J.: Enumerating solutions to p(a) + q(b) = r(c) + s(d). Math. Comput. 70(233), 389\u2013394 (2001)","journal-title":"Math. Comput."},{"key":"28_CR5","unstructured":"Bernstein, D.J.: Better price-performance ratios for generalized birthday attacks. In: Workshop Record of SHARCS 2007: Special-purpose Hardware for Attacking Cryptographic Systems (2007). http:\/\/cr.yp.to\/rumba20\/genbday-20070719.pdf"},{"key":"28_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-10628-6_2","volume-title":"Progress in Cryptology - INDOCRYPT 2009","author":"DJ Bernstein","year":"2009","unstructured":"Bernstein, D.J., Lange, T., Niederhagen, R., Peters, C., Schwabe, P.: FSBday. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 18\u201338. Springer, Heidelberg (2009)"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Shamir, A.: Cryptanalytic time\/memory\/data tradeoffs for stream ciphers. In: Okamoto, T. (ed.) [26], vol. 1976, pp. 1\u201313. Springer, Heidelberg (2000)","DOI":"10.1007\/3-540-44448-3_1"},{"key":"28_CR8","unstructured":"Bleichenbacher, D.: On the generation of DSA one-time keys. In: The 6th Workshop on Elliptic Curve Cryptography (ECC 2002) (2002)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Yao, F.F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 21\u201323 May 2000, pp. 435\u2013440. ACM, Portland (2000)","DOI":"10.1145\/335305.335355"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Boneh, D., Joux, A., Nguyen, P.Q.: Why textbook ElGamal and RSA encryption are insecure. In: Okamoto, T. (ed.) [26], pp. 30\u201343 (2000)","DOI":"10.1007\/3-540-44448-3_3"},{"key":"28_CR11","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. 2332, p. 209. Springer, Heidelberg (2002)"},{"key":"28_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-42033-7_18","volume-title":"Advances in Cryptology - ASIACRYPT 2013","author":"I Dinur","year":"2013","unstructured":"Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and Full AES2. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 337\u2013356. Springer, Heidelberg (2013)"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Guo, J.: Marble v1. Submitted to CAESAR (2014)","DOI":"10.4324\/9781315746173-1"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-642-23951-9_22","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2011","author":"J Guo","year":"2011","unstructured":"Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326\u2013341. Springer, Heidelberg (2011)"},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"ME Hellman","year":"1980","unstructured":"Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401\u2013406 (1980)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"28_CR16","unstructured":"Jean, J., Nikoli\u0107, I., Peyrin, T.: Deoxys v1. Submitted to CAESAR (2014)"},{"key":"28_CR17","unstructured":"Jean, J., Nikoli\u0107, I., Peyrin, T.: Joltik v1. Submitted to CAESAR (2014)"},{"key":"28_CR18","unstructured":"Jean, J., Nikoli\u0107, I., Peyrin, T.: KIASU v1. Submitted to CAESAR (2014)"},{"issue":"234","key":"28_CR19","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1090\/S0025-5718-00-01200-X","volume":"70","author":"A Joux","year":"2001","unstructured":"Joux, A., Lercier, R.: \u201cChinese and Match\u201d, an alternative to Atkin \u201cMatch and Sort\u201d method used in the sea algorithm. Math. Comput. 70(234), 827\u2013836 (2001)","journal-title":"Math. Comput."},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-642-10366-7_21","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"A Joux","year":"2009","unstructured":"Joux, A., Lucks, S.: Improved generic algorithms for 3-collisions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 347\u2013363. Springer, Heidelberg (2009)"},{"issue":"2","key":"28_CR21","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":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1007\/978-3-662-45611-8_25","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"M Nandi","year":"2014","unstructured":"Nandi, M.: XLS is not a strong pseudorandom permutation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 478\u2013490. Springer, Heidelberg (2014)"},{"key":"28_CR23","unstructured":"Nandi, M.: Revisiting security claims of XLS and COPA. Cryptology ePrint Archive, Report 2015\/444 (2015). http:\/\/eprint.iacr.org\/"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-662-43933-3_7","volume-title":"Fast Software Encryption","author":"I Nikoli\u0107","year":"2014","unstructured":"Nikoli\u0107, I., Wang, L., Wu, S.: Cryptanalysis of round-reduced LED. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 112\u2013130. Springer, Heidelberg (2014)"},{"key":"28_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-540-45146-4_36","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"P Oechslin","year":"2003","unstructured":"Oechslin, P.: Making a faster cryptanalytic time-memory trade-off. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 617\u2013630. Springer, Heidelberg (2003)"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44448-3","volume-title":"Advances in Cryptology - ASIACRYPT 2000","author":"T Okamoto","year":"2000","unstructured":"Okamoto, T.: ASIACRYPT 2000. LNCS, vol. 1976. Springer, Heidelberg (2000)"},{"key":"28_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-540-74619-5_7","volume-title":"Fast Software Encryption","author":"T Ristenpart","year":"2007","unstructured":"Ristenpart, T., Rogaway, P.: How to enrich the message space of a cipher. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 101\u2013118. Springer, Heidelberg (2007)"},{"issue":"3","key":"28_CR28","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=O(2^{n\/2}), S=O(2^{n\/4})$$ algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"key":"28_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/11927587_5","volume-title":"Information Security and Cryptology \u2013 ICISC 2006","author":"K Suzuki","year":"2006","unstructured":"Suzuki, K., Tonien, D., Kurosawa, K., Toyota, K.: Birthday paradox for multi-collisions. In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 29\u201340. Springer, Heidelberg (2006)"},{"issue":"1","key":"28_CR30","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":"28_CR31","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. 2442, p. 288. Springer, Heidelberg (2002)"},{"key":"28_CR32","doi-asserted-by":"crossref","unstructured":"Wang, L.: SHELL v1. Submitted to CAESAR (2014)","DOI":"10.4324\/9781315746173-1"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48800-3_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T00:03:54Z","timestamp":1692144234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48800-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662487990","9783662488003"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48800-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}