On Generalized Feistel Networks
Authors:
Viet Tung Hoang and
Phillip Rogaway
Abstract:
We prove beyond-birthday-bound security for
most of the well-known types of generalized Feistel networks:
(1) unbalanced Feistel networks,
where the $n$-bit to $m$-bit round functions may have $n\ne m$;
(2) alternating Feistel networks,
where the round functions alternate between contracting and expanding;
(3) type-1, type-2, and type-3 Feistel networks,
where $n$-bit to $n$-bit round functions are used to encipher $kn$-bit strings for some $k\ge2$;
and
(4) numeric variants of any of the above,
where one enciphers numbers in some given range rather than strings of some given size.
Using a unified analytic framework, we show that, in any of these settings,
for any $\varepsilon>0$, with enough rounds,
the subject scheme can tolerate CCA attacks of up to
$q\sim N^{1-\varepsilon}$ adversarial queries, where $N$ is the size of the round functions' domain
(the larger domain for alternating Feistel).
Prior analyses for most generalized Feistel networks established security to only
$q\sim N^{0.5}$ queries.
References:
Proceedings of CRYPTO 2011
Full Version:
Full version is available in pdf