Beyond quadratic speedups in quantum attacks on symmetric schemes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Beyond quadratic speedups in quantum attacks on symmetric schemes

Ferdinand Sibleyras
  • Fonction : Auteur
  • PersonId : 1248777
  • IdRef : 269254331

Résumé

In this paper, we report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only, with a more than quadratic time speedup compared to the best classical attack. We study the 2XOR-Cascade construction of Gaži and Tessaro (EURO-CRYPT 2012). It is a key length extension technique which provides an n-bit block cipher with 5n 2 bits of security out of an n-bit block cipher with 2n bits of key, with a security proof in the ideal model. We show that the offline-Simon algorithm of Bonnetain et al. (ASIACRYPT 2019) can be extended to, in particular, attack this construction in quantum time O(2 n), providing a 2.5 quantum speedup over the best classical attack. Regarding post-quantum security of symmetric ciphers, it is commonly assumed that doubling the key sizes is a sufficient precaution. This is because Grover's quantum search algorithm, and its derivatives, can only reach a quadratic speedup at most. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit. In particular, the 2XOR-Cascade cannot be used to generically strengthen block ciphers against quantum adversaries, as it would offer only the same security as the block cipher itself.
Fichier principal
Vignette du fichier
2021-1348.pdf (510.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03926591 , version 1 (06-01-2023)

Licence

Paternité

Identifiants

Citer

Xavier Bonnetain, André Schrottenloher, Ferdinand Sibleyras. Beyond quadratic speedups in quantum attacks on symmetric schemes. EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Colin Boyd, May 2022, Trondheim, Norway. pp.315-344, ⟨10.1007/978-3-031-07082-2_12⟩. ⟨hal-03926591⟩
28 Consultations
34 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More