Even-Mansour Cipher: Efficient algorithms for sampling a random permutation

Question

My understanding of the Even-Mansour cipher is the following:

• We draw a random permutation $P$ from the set of all permutation $P: \{0,1\}^n \rightarrow \{0,1\}^n$. This permutation is public.
• We generate two random keys $k_1, k_2 \in \{0,1\}^n$.
• To encrypt a message $m \in \{0,1\}^n$, we compute $E_{k_1, k_2} = P(m \oplus k_1) \oplus k_2$.

What kind of algorithms exists that allow us to efficiently sample (and represent) a permutation $P$ from the set of all permutations from $n$ bit strings to $n$ bit strings?

Answer 1

Even-Mansour is a theoretical model to prove security results. One would need to sample permutations of $n$ bits, say for $n=128,$ since the resulting space of $N=2^n$ objects would be too large to store or manipulate. This is similar to the fact that no one uses a purely random equidistributed and i.i.d. sequence of bits as a keystream in OTP mode in modern cryptography. It is too slow.

However, the following algorithm gives a random permutation on $\{1,2,\ldots, N\}.$ No claim of optimal efficiency is made here.

CODE FOR RANDOM PERMUTATION OF SMALL LIST

Input: The list $A=[1,2,\ldots, N]$ of $N=2^n$ items.

Task: permute the values in $A$ at random.

Let $S:=\{u: u \in A\}.$ Let $B:=A$

for each $i=1,\ldots,N$ do

$\quad$ Choose a random integer $j \in S$

$\quad$ Change array $B$ via $B[j]:=A[i]$

$\quad$ Remove $j$ from set $S$

end for This algorithm chooses $N,$ then $N-1$, then $N-2$ etc. objects uniformly and can generate each permutation with equal likelihood, since it makes $N\!$ choices. Output: The list $A$ is now random.

There are more efficient ways to sample random permutations, see for example Jens Gustedt, "Efficient sampling of random permutations", Journal of Discrete Algorithms, Vol. 6, Issue 1, 2006. Also take a look at Fisher-Yates shuffle and Knuth Shuffle, google is your friend.

The algorithm below doesn't quite get there, thanks to @kelalaka for the correction

Input: The list $A=\{1,2,\ldots, N\}$ of $N=2^n$ items.

Task: permute the values in $A$ at random.

for each $i=0,\ldots,N-1$ do

$\quad$ Choose a random integer $j$ with $i<j<N.$

$\quad$ Swap the entries $A[i]$ and $A[j].$

end for

Output: The list $A$ is now random.