Welcome to the resource topic for 2020/229
Title:
Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications
Authors: Itai Dinur
Abstract:We consider a 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 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) for S = \tilde{O}(C). In this paper, we prove that any algorithm for CSP satisfies T^2 \cdot S = \tilde{\Omega}(C^2 \cdot N) for S = \tilde{O}(C), 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.
ePrint: https://eprint.iacr.org/2020/229
Talk: https://www.youtube.com/watch?v=ljVAm1ZNN_4
Slides: https://iacr.org/submit/files/slides/2020/eurocrypt/ec2020/165/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .