Paper 2021/1348

Beyond quadratic speedups in quantum attacks on symmetric schemes

Xavier Bonnetain, André Schrottenloher, and Ferdinand Sibleyras

Abstract

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{\v{z}}i and Tessaro (EUROCRYPT~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 Õ(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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
Post-quantum cryptographyquantum cryptanalysiskey-length extension2XOR-CascadeSimon's algorithmquantum searchoffline-Simon
Contact author(s)
xavier bonnetain @ inria fr
andre schrottenloher @ m4x org
ferdinand @ sibleyras fr
History
2022-05-16: revised
2021-10-07: received
See all versions
Short URL
https://ia.cr/2021/1348
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1348,
      author = {Xavier Bonnetain and André Schrottenloher and Ferdinand Sibleyras},
      title = {Beyond quadratic speedups in quantum attacks on symmetric schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1348},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1348}},
      url = {https://eprint.iacr.org/2021/1348}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.