I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], which says you need at least 3 rounds of a $2$-branch Feistel network to get a PRP if the underlying $f$ function is a PRF. I also came to know about the Generalized Feistel Network which has more than two branches.

What will be the minimum number of rounds to get a PRP from a generalized $n~(>2)$ branch Feistel network, given the underlying function $f$ is a PRF?

  • $\begingroup$ Ah, OK, I think I'm starting to see the idea of the question now. It asks for the number of rounds as a function of $n$, given that the PRF is theoretically secure. Thanks, I'll remove the other comments. $\endgroup$ – Maarten Bodewes Dec 18 '19 at 17:25

As you probably saw in the reference linked, there are multiple types of "basic" generalized Feistel networks: Type-1, Type-2 and Type-3. As far as I can tell all of these were introduced at CRYPTO'89 by Zheng, Matsumoto, and Imai in "On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses".

Suppose that your state is split into $k$ blocks, then the above paper does in fact prove / claim security for these generalized Feistel constructions (with each and every PRF used in all rounds and all state parts of each round being independent):

  • For Type-1, security is proven for $2k-1$ rounds
  • For Type-2, security is proven for $k+1$ rounds
  • For Type-3, security is proven for $k+1$ rounds

The paper also proves / claims that these numbers of rounds are actually minimal.

For everbody's reference, here are the three basic types as a fancy graphic: Feistel variants
image source

As one can somewhat clearly see, the first two types are "special cases" of the third where a certain selections of PRF invocations and XORings is dropped. The paper does provide further analysis on the number of rounds to keep security when dropping these with certain patterns

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.