Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Generalized birthday problem, k-list problem, k-tree algorithm, time-memory tradeoff

Original Publication (with minor differences): IACR-ASIACRYPT-2015

Date: received 18 Mar 2016

Contact author: inikolic at ntu ed sg, sasaki yu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20160321:101043 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]