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?
2
$\begingroup$
$\endgroup$
4
$\begingroup$
$\endgroup$
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).
