Paper 2022/1558

Quantum Speed-Up for Multidimensional (Zero Correlation) Linear Distinguishers

Akinori Hosoyamada, NTT Social Informatics Laboratories

This paper shows how to achieve a quantum speed-up for multidimensional (zero correlation) linear distinguishers. A previous work by Kaplan et al. has already shown a quantum quadratic speed-up for one-dimensional linear distinguishers. However, classical linear cryptanalysis often exploits multidimensional approximations to achieve more efficient attacks, and in fact it is highly non-trivial whether Kaplan et al.'s technique can be extended into the multidimensional case. To remedy this, we investigate a new quantum technique to speed-up multidimensional linear distinguishers. Firstly, we observe that there is a close relationship between the subroutine of Simon's algorithm and linear correlations via Fourier transform. Specifically, a slightly modified version of Simon's subroutine, which we call Correlation Extraction Algorithm (CEA), can be used to speed-up multidimensional linear distinguishers. CEA also leads to a speed-up for multidimensional zero correlation distinguishers, as well as some integral distinguishers through the correspondence of zero correlation and integral properties shown by Bogdanov et al.~and Sun et al. Furthermore, we observe possibility of a more than quadratic speed-ups for some special types of integral distinguishers when multiple integral properties exist. Especially, we show a single-query distinguisher on a 4-bit cell SPN cipher with the same integral property as 2.5-round AES. Our attacks are the first to observe such a speed-up for classical cryptanalytic techniques without relying on hidden periods or shifts. By replacing the Hadamard transform in CEA with the general quantum Fourier transform, our technique also speeds-up generalized linear distinguishers on an arbitrary finite abelian group.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
quantum cryptanalysislinear cryptanalysisintegral cryptanalysismore-than-quadratic speed-up
Contact author(s)
akinori hosoyamada @ ntt com
2023-09-15: last of 2 revisions
2022-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akinori Hosoyamada},
      title = {Quantum Speed-Up for Multidimensional (Zero Correlation) Linear Distinguishers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1558},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.