Jan 21, 2018
Pseudorandom Permutation using a Feistel Network
What is a random permutation?
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomised algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.
But wait! Computers can’t generate truly random numbers. How can we generate random permutations then?
Bringing in pseudorandom permutations
In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function’s domain) with practical effort.
That’s cool! How do I build one?
Michael Luby and Charles Rackoff showed that a “strong” pseudorandom permutation can be built from a pseudorandom function using a Luby-Rackoff construction which is built using a Feistel network.
It can be shown that we can build a secure PRP using a secure PRF in just 3 rounds of a Feistel network.
Understood! Let’s build one!
We’ll use Python to build a quick working prototype. Note that the code is written to be more understandable rather than being more optimised. The code computes the mapping for each number in our input domain. It also ensures that no two numbers in the input domain map to the same number in the output range.
Production Ready Code
Originally published at https://blog.codezest.in on January 21, 2018.
