On Quantum Slide Attacks - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

On Quantum Slide Attacks

(1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
quantum-slide.pdf (517.36 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01946399 , version 1 (06-12-2018)

Identifiers

  • HAL Id : hal-01946399 , version 1

Cite

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

Collections

INRIA INRIA2
131 View
163 Download

Share

Gmail Facebook Twitter LinkedIn More