Paper 2023/184

Quantum Linear Key-recovery Attacks Using the QFT

André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA

The Quantum Fourier Transform is a fundamental tool in quantum cryptanalysis. In symmetric cryptanalysis, hidden shift algorithms such as Simon's (FOCS 1994), which rely on the QFT, have been used to obtain structural attacks on some very specific block ciphers. The Fourier Transform is also used in classical cryptanalysis, for example in FFT-based linear key-recovery attacks introduced by Collard et al. (ICISC 2007). Whether such techniques can be adapted to the quantum setting has remained so far an open question. In this paper, we introduce a new framework for quantum linear key-recovery attacks using the QFT. These attacks loosely follow the classical method of Collard et al., in that they rely on the fast computation of a ``correlation state'' in which experimental correlations, rather than being directly accessible, are encoded in the amplitudes of a quantum state. The experimental correlation is a statistic that is expected to be higher for the good key, and on some conditions, the increased amplitude creates a speedup with respect to an exhaustive search of the key. The same method also yields a new family of structural attacks, and new examples of quantum speedups beyond quadratic using classical known-plaintext queries.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in CRYPTO 2023
Linear cryptanalysisQuantum cryptanalysisFast Walsh-Hadamard TransformQuantum Fourier Transform
Contact author(s)
andre schrottenloher @ inria fr
2023-06-06: revised
2023-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {André Schrottenloher},
      title = {Quantum Linear Key-recovery Attacks Using the QFT},
      howpublished = {Cryptology ePrint Archive, Paper 2023/184},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.