Skip to main content

Feistel Shuffle

2023-05-13 • @kevincharm

The Feistel Shuffle is a generalised Feistel cipher (GFC) that implements format-preserving encryption (FPE), bijectively mapping XXX \rightarrow X with pseudorandom permutation πS\pi^S determined by a random seed SS. This algorithm was originally proposed by Black & Rogaway [1].

Using the Feistel Shuffle, we can efficiently perform on-chain shuffles in the EVM by eliminating writes to storage due to its stateless nature.

Iteration Bounds

In our implementation of the generalised Feistel cipher, the selection of parameters aa and bb for a cipher on domain kk are automatically chosen as a=b=h=ka = b = h = \lceil \sqrt{k} \rceil (the next perfect square). This gives (from [1]):

δk=2k+1\delta_{k} = 2 \cdot \sqrt{k} + 1

where δk\delta_{k} denotes the number of elements that lie outside of the domain kk for which we need to perform an additional cycle-walk iteration.

It follows that the upper bound of cycle-walking iterations CC (from [2]) is denoted by:

C=nhC = \lceil \frac{n}{h} \rceil

Pseudorandom Round Functions

With an input domain DD, the round function fif_i should output unique keys K0,...,Kr1K_0, ..., K_{r-1}, where DKD \subset K, that will be used as the round keys for rr rounds of Feistel.

Feistel Rounds

According to [3], performing r=4r = 4 rounds of Feistel is sufficient for CCA security. This practically means that r=4r = 4 rounds are enough to create pseudorandom permutations that are indistinguishable from truly random permutations.

Randomness of Permutations

We do a little empirical testing to show the randomness of permutations generated by GFC-FPE.

The following figure shows the permuted indices (y-axis) for each input (x-axis) in a domain of size 1000010000 with r=4r = 4 Feistel rounds, using keccak256 and some 256-bit random seed as the pseudorandom function.


The following figure plots 10 instances of GFC-FPE outputs with the same configuration as above, but using a different 256-bit random seed for each instance.




[1] John Black and Phillip Rogaway. 2002. Ciphers with arbitrary finite domains. In Topics in Cryptology—CT-RSA 2002: The Cryptographers’ Track at the RSA Conference 2002 San Jose, CA, USA, February 18–22, 2002 Proceedings, Springer, 114–130.

[2] Bruce Schneier and John Kelsey. 2005. Unbalanced Feistel networks and block cipher design. In Fast Software Encryption: Third International Workshop Cambridge, UK, February 21–23 1996 Proceedings, Springer, 121–144.

[3] Michael Luby and Charles Rackoff. 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing 17, 2 (1988), 373–386.

[4] Viet Tung Hoang and Phillip Rogaway. 2010. On Generalized Feistel Networks. In CRYPTO, Springer, 613–630.

[5] Vitalik Buterin. 2018. In ethereum/research.