Quantum distinguisher between the 3-round Feistel cipher and the random permutation

TLDR

No polynomial classical algorithms can distinguish between the 3‑round Feistel cipher with internal permutations and a random permutation. This paper shows that a polynomial quantum algorithm exists for distinguishing them. The distinguishing problem is efficiently solvable by exploiting quantum parallelism. The algorithm demonstrates that the cipher is secure against classical chosen‑plaintext attacks but becomes vulnerable to quantum chosen‑plaintext attacks, marking the first use of Simon’s algorithm in cryptanalysis.

Abstract

No polynomial classical algorithms can distinguish between the 3-round Feistel cipher with internal permutations and a random permutation. It means that the 3-round Feistel cipher with internal permutations is secure against any chosen plaintext attack on the classical computer. This paper shows that there exists a polynomial quantum algorithm for distinguishing them. Hence, the 3-round Feistel cipher with internal permutations may be insecure against a chosen plaintext attack on a quantum computer. This distinguishing problem is an instance that can be efficiently solved by exploiting the quantum parallelism. The proposed algorithm is the first application of Simon's algorithm to cryptographic analysis.