Luby and Rackoff showed that 3 rounds are sufficient to make the Feistel networks a pseudorandom permutation.

Question: why are 3 round Feistel Ciphers not common?

My thoughts about the round functions of Luby and Rackoff construction are

  1. They are hard to find one
  2. They are hard to analyze
  3. They are complex to fit small devices.
  4. 3 rounds of Luby and Rackofd constructions are slower than 16 rounds non-Luby and Rackoff constructions. Assuming that they have the same security.
  • $\begingroup$ how do they not fit on small devices ? the same circuitry can be used on encryption and decryption $\endgroup$
    – hardyrama
    Oct 13 '18 at 13:03
  • $\begingroup$ @hardyrama Well, this is maybe a bit older issue where we have very limited devices. If the $F$ function in Feistel is complex i.e. requires more space to satisfy Luby and Rackoff requirements, then a simple $F'$ that requires small space can fit the device. Of course, will have a bigger key scheduling algorithm. $\endgroup$
    – kelalaka
    Oct 13 '18 at 15:00
  • $\begingroup$ @PaulUszak These are my thoughts, I will try to find reasons or counter examples. If the speed of the a Luby and Rackoff round function is $>16/3$ where a unit 1 is non-LR's speed then this is the case. $\endgroup$
    – kelalaka
    Oct 13 '18 at 15:11

The main issue is that this only holds if you start with a PRF. Constructing a secure PRF is just as hard as constructing a secure strong PRP, so haven't gained much. In practice we typically start with constructing a PRP and then turn it in into a PRF, not the other way round.

Feistel based blockciphers use many rounds, because their round functions are individually weak but also faster than a PRF.

In addition we typically want a strong PRP, so you need at least four rounds, not three. Another limitation is that the block size must be big enough for the target security level (IIRC you need 2n-bit blocks for n-bit security while we often target a security level equal or higher than the block size (e.g. AES has 128-bit blocks and 128/192/256-bit keys with the security level matching the key size).

There is one area where Feistel constructions using a small number (two to four) strong round functions are popular: Large and variable width permutations. OAEP is based on a two round feistel structure. There is the EME mode for wide block encryption.

  • $\begingroup$ do you know some reason that why the popularity is gone away? $\endgroup$
    – kelalaka
    Oct 15 '18 at 8:42

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.