The Elegance of the Feistel Cipher
Pseudorandom Functions & Block Ciphers
Read this section to see how the Feistel cipher works with pseudorandom functions. One important thing to note is that no matter what trick we use inside a round, we can always undo it. And when you are trying to decode a message, the steps taken are like flipping a mirror image of what was done to encode it. This makes it easy to build simple hardware systems to do this coding and decoding.
Pseudorandom Functions & Block Ciphers Imagine if Alice & Bob had an infinite amount of shared randomness - not just a short key. They could split it up into λ-bit chunks and use each one as a one-time pad whenever they want to send an encrypted message of length λ.
Alice could encrypt by saying, "hey Bob, this message is encrypted with one-time pad using chunk #674696273 as key". Bob could decrypt by looking up location #674696273 in his copy of the shared randomness. As long as Alice doesn't repeat a key/chunk, an eavesdropper (who doesn't have the shared randomness) would learn nothing about the encrypted messages. Although Alice announces (publicly) which location/chunk was used as each one-time pad key, that information doesn't help the attacker know the value at that location.
It is silly to imagine an infinite amount of shared randomness. However, an expo- nential amount of something is often just as good as an infinite amount. A shared table containing "only" 2λ one-time pad keys would be quite useful for encrypting as many messages as you could ever need.
A pseudorandom function (PRF) is a tool that allows Alice & Bob to achieve the effect of such an exponentially large table of shared randomness in practice. In this chapter we will explore PRFs and their properties. In a later chapter, after introducing new security definitions for encryption, we will see that PRFs can be used to securely encrypt many messages under the same key, following the main idea illustrated above.
Source: Mike Rosulek, https://joyofcryptography.com/pdf/chap6.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.