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=2n. By combining two ideas, unbalanced interleaving and Oorschot-Wiener parallel collision search, we construct an alternative algorithm that follows T2M=R2N, where MR. 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.