### 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.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. The conference version of this paper will appear in CRYPTO 2010.
Contact author(s)
hviettung @ gmail com
History
2018-11-29: last of 12 revisions
See all versions
Short URL
https://ia.cr/2010/301

CC BY

BibTeX

@misc{cryptoeprint:2010/301,
author = {Viet Tung Hoang and Phillip Rogaway},
title = {On generalized Feistel networks},
howpublished = {Cryptology ePrint Archive, Paper 2010/301},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/301}},
url = {https://eprint.iacr.org/2010/301}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.