Cryptology ePrint Archive: Report 2021/330

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

Pooya Farshim and Louiza Khati and 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.

Category / Keywords: secret-key cryptography / KDM Security, Key-Alternating Feistel Ciphers, H-Coefficient Technique

Original Publication (with minor differences): CT-RSA 2021

Date: received 12 Mar 2021

Contact author: damien vergnaud at lip6 fr

Available format(s): PDF | BibTeX Citation

Version: 20210314:150528 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]