Title | ||
---|---|---|
Quantum Demiric-Selçuk Meet-in-the-Middle Attacks: Applications to 6-Round Generic Feistel Constructions. |
Abstract | ||
---|---|---|
This paper shows that quantum computers can significantly speed-up a type of meet-in-the-middle attacks initiated by Demiric and Selcuk (DS-MITM attacks), which is currently one of the most powerful cryptanalytic approaches in the classical setting against symmetric-key schemes. The quantum DS-MITM attacks are demonstrated against 6 rounds of the generic Feistel construction supporting an n-bit key and an n-bit block, which was attacked by Guo et al. in the classical setting with data, time, and memory complexities of O(2(3n/4)). The complexities of our quantum attacks depend on the adversary's model. When the adversary has an access to quantum computers for offline computations but online queries are made in a classical manner, the attack complexities become (O) over tilde (2(n/2)), which significantly improves the classical attack. The attack is then extended to the case that the adversary can make superposition queries. The attack is based on 3-round distinguishers with Simon's algorithm and then appends 3 rounds for key recovery. This can be solved by applying the combination of Simon's and Grover's algorithms recently proposed by Leander and May. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-98113-0_21 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Post-quantum cryptography,Demiric-Selcuk meet-in-the-middle attack,Feistel construction,Grover's algorithm,Claw finding algorithm,Q1 model | Quantum,Superposition principle,Post-quantum cryptography,Computer science,Computer network,Quantum computer,Theoretical computer science,Tilde,Adversary,Grover's algorithm,Computation | Conference |
Volume | ISSN | Citations |
11035 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Akinori Hosoyamada | 1 | 1 | 1.36 |
Yu Sasaki | 2 | 247 | 15.33 |