International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Post-quantum Security of Key-Alternating Feistel Ciphers

Authors:
Jyotirmoy Basak , Okinawa Institute of Science and Technology
Ritam Bhaumik , Cryptography Research Centre, Technology Innovation Institute
Amit Kumar Chauhan , QNu Labs
Ravindra Jejurikar , Cryptography Research Centre, Technology Innovation Institute
Ashwin Jha , Ruhr-University Bochum
Anandarup Roy , Kyushu University
André Schrottenloher , Univ Rennes, Inria, CNRS, IRISA
Suprita Talnikar , Kyushu University & Indian Statistical Institute
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
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 \emph{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.
BibTeX
@inproceedings{asiacrypt-2025-36158,
  title={Post-quantum Security of Key-Alternating Feistel Ciphers},
  publisher={Springer-Verlag},
  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},
  year=2025
}