Welcome to the resource topic for 2016/312
Title:
Refinements of the k-tree Algorithm for the Generalized Birthday Problem
Authors: Ivica Nikolic, 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.
ePrint: https://eprint.iacr.org/2016/312
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .