CryptoDB
The Exact Multi-User Security of Key-Alternating Feistel Ciphers with a Single Permutation
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Provable security bounds of Feistel ciphers have been a significant research topic since the seminal work by Luby and Rackoff in 1986. While the field of research started by abstracting round functions with ideal random functions, the research community has extended provable security to encompass more realistic models. These models include key-alternating Feistel (KAF) ciphers that separate random functions into round keys and public primitives, which is further extended to utilizing a single primitive across all rounds, correlated subkeys, and in the multi-user (mu) setting. This paper advances this field by presenting new mu security bounds for a notable variant, a KAF with a single public permutation based on the Even-Mansour (EM) construction. With an $n$-bit public permutation and $(r-2)$-wise independent subkeys, with respect to the round number $r$, our new proof establishes a general bound of $n(r-2)/(r-1)$ bits, offering improvements over the current state-of-the-art. We also provide a new information-theoretic matching attack, confirming its tightness. Technical innovation include extending the resampling method to Feistel ciphers and devising an information-theoretic variant of the meet-in-the-middle attack applicable to large $r$. |
BibTeX
@inproceedings{crypto-2025-35766,
title={The Exact Multi-User Security of Key-Alternating Feistel Ciphers with a Single Permutation},
publisher={Springer-Verlag},
author={Yusuke Naito and Yu Sasaki and Takeshi Sugawara},
year=2025
}