2
$\begingroup$

I have this set: {0,1,2,3,...,15}.

I would like to create a pseudo-random permutation from elements of this set, for example {10,2,15,0,7,5,9,4,3,13,11,1,6,12,8,14}.

Which method could I use to obtain the permutation?

$\endgroup$
4
$\begingroup$

The problem is small enough that the desired PRP can be implemented as a small array of 16 values initialized using the Fisher-Yates shuffle, with a pseudo-random generator deciding the indexes of the shuffles. That's probably the simplest, thus the best except perhaps when side channels (such as cache-induced timing variations) are a consideration.

Something NOT suitable is using a Feistel cipher with many rounds and a large random key defining the round functions: this is bound to generate an even permutation, thus only half of the $16!$ permutations would be obtainable. However this defect can be fixed by using 2-bit modular addition instead of 2-bit XOR to mix the output of the round functions: $R_{i+1}=((L_i+F(R_i,K_i))\bmod 4)$. This can be made constant-time, and also works nicely for permutations of $2^k$ elements with $k$ large enough to preclude the Fisher-Yates approach, which requires about $k\,2^k$ bits of memory.

The problem is well studied in Format Preserving Encryption, which offers a number of other techniques that remain suitable for much larger sets (contrary to Fisher-Yates), including some that exactly balance the odds of the resulting permutations (contrary to Feistel cipher with mixing by modular addition).

$\endgroup$

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.