Paper 2025/1603

Post-quantum Security of Key-Alternating Feistel Ciphers

Ritam Bhaumik, Technology Innovation Institute

Amit Kumar Chauhan, QuNu Labs Pvt. Ltd.

Ravindra Jejurikar, Technology Innovation Institute

Ashwin Jha, Ruhr University Bochum

Anandarup Roy, Kyushu University

André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA

Suprita Talnikar, Indian Statistical Institute, Kyushu University

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.

@misc{cryptoeprint:2025/1603,
      author = {Jyotirmoy Basak and Ritam Bhaumik and Amit Kumar Chauhan and Ravindra Jejurikar and Ashwin Jha and Anandarup Roy and André Schrottenloher and Suprita Talnikar},
      title = {Post-quantum Security of Key-Alternating Feistel Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1603},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1603}
}