4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Ella Rose
    Commented Apr 3, 2016 at 5:16

1 Answer 1

Reset to default
5
$\begingroup$

To understand the Even-Mansour security result, it helps to first understand the random oracle model. Roughly speaking, the random oracle model says that a hash function should behave like a randomly chosen function, and have no detectable patterns or structural properties that a random function wouldn't have. Of course, the hash function is publicly known, so anyone can compute it, but apart from that, it shouldn't have any other structural properties.

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.

This is like an unkeyed version of the ideal cipher model. See What is the ideal cipher model?.

Once you understand the ideal cipher model, you can then evaluate whether some specific construction would qualify. It basically comes down to whether your other construction qualifies as a reasonable instantiation of a random permutation oracle (i.e., as a reasonable instantiation of an unkeyed version of an ideal cipher).

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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).. $\endgroup$
    – Mikero
    Commented Aug 3, 2016 at 22:54
  • $\begingroup$ @Mikero, oops, right on! Thanks for the correct. I edited to fix that. Thanks again! $\endgroup$
    – D.W.
    Commented Aug 4, 2016 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.