Paper 2022/1558

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

Akinori Hosoyamada, NTT Social Informatics Laboratories
Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
Keywords
quantum cryptanalysislinear cryptanalysisintegral cryptanalysismore-than-quadratic speed-up
Contact author(s)
akinori hosoyamada @ ntt com
History
2023-09-15: last of 2 revisions
2022-11-09: received
See all versions
Short URL
https://ia.cr/2022/1558
License
Creative Commons Attribution
CC BY

BibTeX

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