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". By combining two ideas, unbalanced interleaving and van Oorschot-Wiener parallel collision search, we construct an alternative algorithm that follows T~2M= R~2N, where M < R. Among others, the algorithm solves the well-known open problem: how to reduce the memory of unbalanced collision search.
展开▼
