# Security of Even-Mansour scheme with keyed shuffle?

I was researching the Even-Mansour scheme and had a question that wasn't addressed in the paper that I saw, and google was minimally helpful.

What if a permutation that uses secret data like the Fisher-Yates shuffle was used as the F permutation instead of a publicly known one? Would the scheme still be equivalently secure?

I noticed the section in the paper that if F is an involution the security proof no longer holds. So there appear to be certain restrictions, and I'm not sure if this idea would violate them.

• I think I may have misinterpreted the meaning of "permutation" in this context (again...). I was thinking of permutation in the sense of a shuffling of bytes among the block, as opposed to a permutation among all possible blocks, like aes in this question – Ella Rose Apr 3 '16 at 5:16

Even-Mansour uses something similar, but now for permutations. The requirement in the Even-Mansour proof is that $F$ is a random permutation oracle: it has to behave just like a randomly chosen permutation (random bijective function), and have no detectable structural properties that a random permutation wouldn't have. Of course, $F$ can be publicly known (so given $x$ anyone can compute $F(x)$ and $F^{-1}(x)$), but apart from that, it shouldn't have any other structural properties.
Fisher-Yates is not suitable except for constructing block cipher, as the running time of Fisher-Yates is super exponential: if you want a random permutation on $b$ bits, the running time of Fisher-Yates is at least $(2^b)!$, which grows asymptotically as something like $2^{(b-1.44) \cdot 2^b}$... i.e., huge.
• Minor correction: $F$ is an ideal permutation not ideal cipher, with the distinction being that an ideal permutation is keyless (it takes a single argument) while an ideal cipher takes two arguments, one of them interpreted as a key. The goal of Even-Mansour is to make a keyed primitive (cipher) from a keyless one (ideal permutation).. – Mikero Aug 3 '16 at 22:54