Paper 2021/1561
Quantum Time/Memory/Data Tradeoff Attacks
Abstract
One of the most celebrated and useful cryptanalytic algorithms is Hellman's time/memory tradeoff (and its Rainbow Table variant), which can be used to invert randomlooking functions on $N$ possible values with time and space complexities satisfying $TM^2=N^2$. As a search problem, one can always transform it into the quantum setting by using Grover's algorithm, but this algorithm does not benefit from the possible availability of auxiliary advice obtained during a free preprocessing stage. However, at FOCS'20 it was rigorously shown that a small amount of quantum auxiliary advice (which can be stored in a quantum memory of size $M \leq O(\sqrt{N})$) cannot possibly yield an attack which is better than Grover's algorithm. In this paper we develop new quantum versions of Hellman's cryptanalytic attack which use large memories in the standard QACM (Quantum Accessible Classical Memory) model of computation. In particular, we improve Hellman's tradeoff curve to $T^{4/3}M^2=N^2$. When we generalize the cryptanalytic problem to a time/memory/data tradeoff attack (in which one has to invert $f$ for at least one of $D$ given values), we get the generalized curve $T^{4/3}M^2D^2=N^2$. A typical point on this curve is $D=N^{0.2}$, $M=N^{0.6}$, and $T=N^{0.3}$, whose time is strictly lower than both Grover's algorithm and the classical Hellman algorithm (both of which require $T=N^{0.4}$ for these $D$ and $M$ parameters).
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint.
 Keywords
 Quantum Cryptanalysis TMD Attacks Hellman Tables Rainbow Tables
 Contact author(s)
 eyal ronen @ cs tau ac il
 History
 20220609: revised
 20211129: received
 See all versions
 Short URL
 https://ia.cr/2021/1561
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1561, author = {Orr Dunkelman and Nathan Keller and Eyal Ronen and Adi Shamir}, title = {Quantum Time/Memory/Data Tradeoff Attacks}, howpublished = {Cryptology ePrint Archive, Paper 2021/1561}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1561}}, url = {https://eprint.iacr.org/2021/1561} }