Cryptology ePrint Archive: Report 2017/1229

Quantum Meet-in-the-Middle Attacks: Applications to 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 then 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 to the adversary. When the adversary has an access to quantum computers for performing 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, and apply it to reduce the cost of finding a match in the MITM stage. The attack is then extended to the case that the adversary is further allowed to make superposition queries (so called Q2 model). The attack approach is drastically changed from 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.

Category / Keywords: post-quantum cryptography; Demiric-Sel\c{c}uk meet-in-the-middle attack; Feistel network; Grover's algorithm; claw finding algorithm; classical query model

Date: received 21 Dec 2017

Contact author: hosoyamada akinori at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20171222:201926 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]