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 van Oorschot-Wiener parallel collision search, we construct an alternative algorithm that follows (TM)-M-2 = (RN)-N-2, where M <= R. Among others, the algorithm solves the well-known open problem: how to reduce the memory of unbalanced collision search. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/978-3-662-53887-6_23 | ADVANCES IN CRYPTOLOGY - ASIACRYPT 2016, PT I |
Keywords | DocType | Volume |
Meet-in-the-middle,Tradeoff,Collision search | Conference | 10031 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
17 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ivica Nikolic | 1 | 170 | 18.14 |
Yu Sasaki | 2 | 247 | 15.33 |