Low-gate Quantum Golden Collision Finding - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Low-gate Quantum Golden Collision Finding

Résumé

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.
Fichier principal
Vignette du fichier
424.pdf (440.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03046039 , version 1 (08-12-2020)

Licence

Paternité

Identifiants

Citer

Samuel Jaques, André Schrottenloher. Low-gate Quantum Golden Collision Finding. SAC 2020 - Selected Areas in Cryptography, Oct 2020, Halifax / Virtual, Canada. pp.329-359, ⟨10.1007/978-3-030-81652-0_13⟩. ⟨hal-03046039⟩

Collections

INRIA INRIA2
79 Consultations
201 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More