Paper 2017/1229

Quantum Demiric-Selçuk Meet-in-the-Middle Attacks: Applications to 6-Round Generic Feistel Constructions

Akinori Hosoyamada and Yu Sasaki

Abstract

This paper shows that quantum computers can significantly speed-up a type of meet-in-the-middle attacks initiated by Demiric and Selçuk (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 and the number of qubits available. When the adversary has an access to quantum computers for offline computations but online queries are made in a classical manner (so called Q1 model), the attack complexities are $O(2^{n/2})$ classical queries, $O(2^n/q)$ quantum computations by using about $q$ qubits. Those are balanced at $\tilde{O}(2^{n/2})$, which significantly improves the classical attack. Technically, we convert the quantum claw finding algorithm to be suitable in the Q1 model. The attack is then extended to the case that the adversary can make superposition queries (so called Q2 model). The attack approach is drastically changed from the one in the Q1 model; 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.