Paper 2021/330

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. CT-RSA 2021
Keywords
KDM SecurityKey-Alternating Feistel CiphersH-Coefficient Technique
Contact author(s)
damien vergnaud @ lip6 fr
History
2021-03-14: received
Short URL
https://ia.cr/2021/330
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/330,
      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},
      url = {https://eprint.iacr.org/2021/330}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.