Paper 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in ASIACRYPT 2016
- Keywords
- meet-in-the-middletradeoffcollision search
- Contact author(s)
-
inikolic @ ntu edu sg
sasaki yu @ lab ntt co jp
cube444 @ gmail com - History
- 2016-09-07: received
- Short URL
- https://ia.cr/2016/851
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/851,
author = {Ivica Nikolic and Yu Sasaki},
title = {A New Algorithm for the Unbalanced Meet-in-the-Middle Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/851},
year = {2016},
url = {https://eprint.iacr.org/2016/851}
}
