Paper 2025/1603

Post-quantum Security of Key-Alternating Feistel Ciphers

Abstract

Since Kuwakado and Morii's work (ISIT 2010 & ISITA 2012), it is known that the classically secure 3-round Luby-Rackoff PRP and Even-Mansour cipher become insecure against an adversary equipped with quantum query access. However, while this query model (the so-called Q2 model) has led to many more attacks, it seems that restricting the adversary to classical query access prevents such breaks (the so-called Q1 model). Indeed, at EUROCRYPT 2022, Alagic et al. proved the Q1-security of the Even-Mansour cipher. Notably, such a proof needs to take into account the dichotomy between construction queries, which are classical, and primitive queries, which are quantum (since the random oracle / permutation models a public function that the adversary can compute). In this paper, we focus on Feistel ciphers. More precisely, we consider Key-Alternating Feistels built from random functions or permutations. We borrow the tools used by Alagic et al. and adapt them to this setting, showing that in the Q1 setting: $\bullet$ the 3-round Key-Alternating Feistel, even when the round functions are the same random oracle, is a pseudo-random permutation; $\bullet$ similarly the 4-round KAF is a strong pseudo-random permutation.