International Association
for Cryptologic Research

This paper shows how to achieve quantum speed-up for multidimensional (zero correlation) linear and integral distinguishers. To understand post-quantum security of symmetric-key cryptosystems, it is important to study how much quantum speed-up we can obtain for classical cryptanalytic techniques such as differential, linear, and integral cryptanalysis. A previous work by Kaplan et al. already showed a quantum quadratic speed-up for one-dimensional linear distinguishers, but it is unclear how to extend their technique to multidimensional linear distinguishers. To remedy this, we investigate how to speed-up multidimensional linear distinguishers in the quantum setting. Firstly, we observe that there is a close relationship between the subroutine of Simon's algorithm and linear correlations via Fourier transform, and a slightly modified version of Simon's subroutine can be used to speed-up multidimensional linear distinguishers. The modified Simon's subroutine also leads to speed-ups for multidimensional zero correlation and some integral distinguishers. Surprisingly, our technique achieves more-than-quadratic speed-ups for some special types of integral distinguishers. This is because the modified Simon's subroutine can exploit the existence of multiple multidimensional zero correlation linear approximations. Our attacks are the first examples achieving such speed-up on classical cryptanalytic techniques without relying on any algebraic structures such as hidden periods or shifts. The speed-ups for multidimensional (zero correlation) linear distinguishers are at-most-quadratic, and all of our attacks require quantum superposition queries.