Paper 2021/330

The Key-Dependent Message Security of Key-Alternating Feistel Ciphers

Pooya Farshim, Louiza Khati, Yannick Seurin, and Damien Vergnaud


Key-Alternating Feistel (KAF) ciphers are a popular variant of Feistel ciphers whereby the round functions are defined as $x \mapsto F(k_i \oplus x)$, where k_i are the round keys and F is a public random function. Most Feistel ciphers, such as DES, indeed have such a structure. However, the security of this construction has only been studied in the classical CPA/CCA models. We provide the first security analysis of KAF ciphers in the key-dependent message (KDM) attack model, where plaintexts can be related to the private key. This model is motivated by cryptographic schemes used within application scenarios such as full-disk encryption or anonymous credential systems. We show that the four-round KAF cipher, with a single function $F$ reused across the rounds, provides KDM security for a non-trivial set of KDM functions. To do so, we develop a generic proof methodology, based on the H-coefficient technique, that can ease the analysis of other block ciphers in such strong models of security.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. CT-RSA 2021
KDM SecurityKey-Alternating Feistel CiphersH-Coefficient Technique
Contact author(s)
damien vergnaud @ lip6 fr
2021-03-14: received
Short URL
Creative Commons Attribution


      author = {Pooya Farshim and Louiza Khati and Yannick Seurin and Damien Vergnaud},
      title = {The Key-Dependent Message Security of Key-Alternating Feistel Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/330},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.