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 .