**On generalized Feistel networks**

*Viet Tung Hoang and Phillip Rogaway*

**Abstract: **We prove beyond-birthday-bound security for the well-known types of
generalized Feistel networks, including: (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 size of the larger domain for alternating Feistel). This is asymptotically optimal. Prior analyses for generalized Feistel networks established security to only $q\sim N^{0.5}$ adversarial queries.

**Category / Keywords: **secret-key cryptography /

**Publication Info: **The conference version of this paper will appear in CRYPTO 2010.

**Date: **received 19 May 2010, last revised 7 Aug 2010

**Contact author: **tvhoang at ucdavis edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20100808:024351 (All versions of this report)

**Short URL: **ia.cr/2010/301

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]