You are looking at a specific version 20200221:121105 of this paper. See the latest version.

Paper 2020/229

Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications

Itai Dinur

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2020
Keywords
Collision search problemtime-space tradeoff$R$-way branching programprovable securitycryptanalysisparallel collision searchdouble encryption.
Contact author(s)
dinuri @ cs bgu ac il
History
2020-07-18: revised
2020-02-21: received
See all versions
Short URL
https://ia.cr/2020/229
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.