Beyond Quadratic Speedups in Quantum Attacks on Symmetric Schemes
| Autor: | Xavier Bonnetain, André Schrottenloher, Ferdinand Sibleyras |
|---|---|
| Přispěvatelé: | Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, NTT Corporation |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Quantum Physics Computer Science - Cryptography and Security Post-quantum cryptography offline-Simon key-length extension quantum cryptanalysis quantum search FOS: Physical sciences Simon's algorithm 2XOR-Cascade [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Quantum Physics (quant-ph) Cryptography and Security (cs.CR) Computer Science::Cryptography and Security |
| Zdroj: | EUROCRYPT 2022 Lecture Notes in Computer Science EUROCRYPT 2022-41st Annual International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT 2022-41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2022, Trondheim, Norway. pp.315-344, ⟨10.1007/978-3-031-07082-2_12⟩ Advances in Cryptology – EUROCRYPT 2022 ISBN: 9783031070815 |
| DOI: | 10.1007/978-3-031-07082-2_12 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|