Feistel Network, consisting of a repeated application of the Feistel Transform, gives a very convenient and popular method of designing "cryptographically strong" permutations from corresponding "cryptographically strong" functions. Up to now, all usages of the Feistel Network, including the celebrated Luby-Rackoff's result, critically rely on (a) the (pseudo)randomness of round functions; and (b) the secrecy of (at least some of) the intermediate round values appearing during the Feistel computation. Moreover, a small constant number of Feistel rounds was typically sufficient to guarantee security under assumptions (a) and (b). In this work we consider several natural scenarios where at least one of the above assumptions does not hold, and show that a constant, or even logarithmic number of rounds is provably insufficient to handle such applications, implying that a new method of analysis is needed. On a positive side, we develop a new combinatorial understanding of Feistel networks, which makes them applicable to situations when the round functions are merely unpredictable rather than (pseudo)random and/or when the intermediate round values may be leaked to the adversary (either through an attack or because the application requires it). In essence, our results show that in any such scenario a super-logarithmic number of Feistel rounds is necessary and sufficient to guarantee security. This partially explains why practical block ciphers use significantly more than 3-6 rounds predicted by the previous theoretical results, and also gives the first theoretical justification regarding the usage of Feistel Networks not satisfying assumptions (a) or (b) above. In particular, we show that super-logarithmic number of Feistel rounds is necessary and sufficient to yield • a strong unpredictable permutation (UP) from any unpredictable function (UF). • a strong pseudorandom permutation (PRP) from any pseudorandom function (PRF), which remains secure even if all the round values are made public. • a strong verifiable unpredictable permutation (VUP) -a new notion we introduce here -from any verifiable unpredictable function (VUF). • a strong verifiable random permutation (VRP) -a new notion we introduce here -from any verifiable random function (VRF, also known as unique signature scheme). Of independent interest, our technique yields a novel domain extension method for messages authentication codes and other related primitives, settling the question studied by An and Bellare in CRYPTO 1999.
Subsequent work by Dodis and Puniya REF studied other properties (such as unpredictability and verifiablity) of the Luby-Rackoff construction when the intermediate values are known to the attacker.
Feistel networks made public, and applications
Advances in Cryptology – EUROCRYPT ’07. LNCS
Computer Science