On Quantum Slide Attacks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

On Quantum Slide Attacks

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-01946399 , version 1

Citer

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

Collections

INRIA INRIA2
141 Consultations
255 Téléchargements

Partager

Gmail Facebook X LinkedIn More