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 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.
展开▼
