You are looking at a specific version 20211007:112920 of this paper. See the latest version.

Paper 2021/1348

Beyond quadratic speedups in quantum attacks on symmetric schemes

Xavier Bonnetain and 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
Preprint. MINOR revision.
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.