Cryptology ePrint Archive: Report 2016/851
A New Algorithm for the Unbalanced Meet-in-the-Middle Problem
Ivica Nikolic and Yu Sasaki
Abstract: A collision search for a pair of $n$-bit unbalanced functions (one is $R$ times more expensive than the other) is an instance of the meet-in-the-middle problem, solved with the familiar standard algorithm that follows the tradeoff $TM=N$, where $T$ and $M$ are time and memory complexities and $N=2^n$.
By combining two ideas, unbalanced interleaving and Oorschot-Wiener parallel collision search, we construct an alternative algorithm that follows $T^2 M = R^2 N$, where $M\le R$.
Among others, the algorithm solves the well-known open problem: how to reduce the memory of unbalanced collision search.
Category / Keywords: meet-in-the-middle, tradeoff, collision search
Original Publication (in the same form): IACR-ASIACRYPT-2016
Date: received 4 Sep 2016, last revised 7 Sep 2016
Contact author: inikolic at ntu edu sg, sasaki yu@lab ntt co jp, cube444@gmail com
Available format(s): PDF | BibTeX Citation
Version: 20160907:141912 (All versions of this report)
Short URL: ia.cr/2016/851
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]