Cryptology ePrint Archive: Report 2018/1067

On Quantum Slide Attacks

Xavier Bonnetain and María Naya-Plasencia and André Schrottenloher

Abstract: At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries.

In this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel networks. With modular additions inside branch or key-addition operations, these attacks reach up to two round self-similarity. With only XOR operations, they reach up to four rounds self-similarity, with a cost at most quadratic in the block size.

Moreover, some of these variants combined with whitening keys (FX construction) can be successfully attacked. We show how these results relate to general quantization principles of classical techniques including sliding with a twist, complementation slide and mirror slidex.

Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round founction is a strong function classically.

Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, that were thought to enjoy an exponential speed up in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.

Category / Keywords: secret-key cryptography / quantum cryptanalysis, slide attacks, Feistel networks, Simon's algorithm, Kuperberg's algortihm, slidex attacks, cycle finding

Date: received 2 Nov 2018

Contact author: xavier bonnetain at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20181109:162556 (All versions of this report)

Short URL: ia.cr/2018/1067


[ Cryptology ePrint archive ]