CryptoDB
Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications
| Authors: |
- Itai Dinur , Ben-Gurion University, Israel
|
| Download: |
- DOI: 10.1007/978-3-030-45721-1_15
(login may be required)
- Search ePrint
- Search Google
|
| Presentation: |
Slides
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
We consider a \emph{collision search problem} (CSP), where given a parameter $C$, the goal is to find $C$ collision pairs in a random function $f:[N] \rightarrow [N]$ (where $[N] = \{0,1,\ldots,N-1\})$ using $S$ bits of memory. Algorithms for CSP have numerous cryptanalytic applications such as space-efficient attacks on double and triple encryption. The best known algorithm for CSP is \emph{parallel collision search} (PCS) published by van Oorschot and Wiener, which achieves the time-space tradeoff $T^2 \cdot S = \tilde{O}(C^2 \cdot N)$.
In this paper, we prove that any algorithm for CSP satisfies $T^2 \cdot S = \tilde{\Omega}(C^2 \cdot N)$, hence the best known time-space tradeoff is optimal (up to poly-logarithmic factors in $N$). On the other hand, we give strong evidence that proving similar unconditional time-space tradeoff lower bounds on CSP applications (such as breaking double and triple encryption) may be very difficult, and would imply a breakthrough in complexity theory. Hence, we propose a new restricted model of computation and prove that under this model, the best known time-space tradeoff attack on double encryption is optimal. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30185,
title={Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Time-space tradeoff;$R$-way branching program;provable security;cryptanalysis;parallel collision search;double encryption.},
volume={12105},
doi={10.1007/978-3-030-45721-1_15},
author={Itai Dinur},
year=2020
}
