Paper 2016/312

Refinements of the k-tree Algorithm for the Generalized Birthday Problem

Ivica Nikolic and Yu Sasaki

Abstract

We study two open problems proposed by Wagner in his seminal work on the generalized birthday problem. First, with the use of multicollisions, we improve Wagner's $3$-tree algorithm. The new 3-tree only slightly outperforms Wagner's 3-tree, however, in some applications this suffices, and as a proof of concept, we apply the new algorithm to slightly reduce the security of two CAESAR proposals. Next, with the use of multiple collisions based on Hellman's table, we give improvements to the best known time-memory tradeoffs for the k-tree. As a result, we obtain the a new tradeoff curve T^2 \cdot M^{\lg k -1} = k \cdot N. For instance, when k=4, the tradeoff has the form T^2 M = 4 \cdot N.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2015
Keywords
Generalized birthday problemk-list problemk-tree algorithmtime-memory tradeoff
Contact author(s)
inikolic @ ntu ed sg
sasaki yu @ lab ntt co jp
History
2016-03-21: received
Short URL
https://ia.cr/2016/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/312,
      author = {Ivica Nikolic and Yu Sasaki},
      title = {Refinements of the k-tree Algorithm for the Generalized Birthday Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2016/312},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/312}},
      url = {https://eprint.iacr.org/2016/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.