You are looking at a specific version 20200415:175911 of this paper. See the latest version.

Paper 2020/424

Low-gate Quantum Golden Collision Finding

Samuel Jaques and André Schrottenloher

Abstract

The golden collision problem asks us to find a single, special collision among the outputs of a pseudorandom function. This generalizes meet-in-the-middle problems, and is thus applicable in many contexts, such as cryptanalysis of the NIST post-quantum candidate SIKE. The main quantum algorithms for this problem are memory-intensive, and the costs of quantum memory may be very high. The quantum circuit model implies a linear cost for random access, which annihilates the exponential advantage of the previous quantum collision-finding algorithms over Grover's algorithm or classical van Oorschot-Wiener. Assuming that quantum memory is costly to access but free to maintain, we provide new quantum algorithms for the golden collision problem with high memory requirements but low gate costs. Under the assumption of a two-dimensional connectivity layout, we provide better quantum parallelization methods for generic and golden collision finding. This lowers the quantum security of the golden collision and meet-in-the-middle problems, including SIKE.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Quantum cryptanalysisgolden collision searchquantum walksSIKE
Contact author(s)
samuel jaques @ materials ox ac uk
andre schrottenloher @ inria fr
History
2020-10-18: revised
2020-04-15: received
See all versions
Short URL
https://ia.cr/2020/424
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.