Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On Quantum Slide Attacks

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, inspired by classical techniques including sliding with a twist, complementation slide and mirror slidex. These slide attacks on Feistel networks reach up to two round self-similarity with modular additions inside branch or key-addition operations. With only XOR operations, they reach up to four round self-similarity, with a cost at most quadratic in the block size. Some of these variants combined with whitening keys (FX construction) can also be successfully attacked. Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round function 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 superpositionmodel for some self-similar SPN and Feistel constructions.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01946399
Contributor : André Schrottenloher <>
Submitted on : Thursday, December 6, 2018 - 9:58:47 AM
Last modification on : Friday, April 19, 2019 - 4:55:25 PM
Long-term archiving on: : Thursday, March 7, 2019 - 1:02:28 PM

File

quantum-slide.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01946399, version 1

Collections

Citation

Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher. On Quantum Slide Attacks. 2018. ⟨hal-01946399⟩

Share

Metrics

Record views

112

Files downloads

135