Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles

The Feistel-2 (a.k.a, Feistel-KF) structure is a variant of the Feistel structure such that the i-th round function is given by $$\mathsf {F}_i(k_i \oplus x)$$ , where $$\mathsf {F}_i$$ is a public random function and its input/output length is n/2 bits. Isobe and Shibutani showed a meet-in-the-middle attack in the classical setting with $$(D,T)=(O(1),O(2^{n/2}))$$ on the 3-round Feistel-2 structure where D and T are the numbers of online/offline queries, respectively. In their attack, since two round keys are recovered simultaneously, a naive application of Grover’s algorithm for two keys needs $$T = O(2^{n/2})$$ in the quantum setting. In this paper, we introduce a new known plaintext attack and chosen plaintext attack on the 3-round Feistel-2 structure in the quantum setting using Grover’s algorithm by recovering the round key one by one in $$(D,T)=(O(1),O(2^{n/4}))$$ . Our attack does not need any quantum query to the encryption oracle (i.e., working in the Q1 model).