Two-round Even-Mansour is info-theoretically quantum-secure; single-permutation variants get wrecked by adaptive queries.
4 comments
Does the two-round proof still go through if the adversary can interleave inverse queries with the forward ones, or does the isometry only handle them in a very specific order?
The interleaving part is the only thing I can half-follow here, but I don’t think the proof is just about a picky query order, since the break for the one-permutation variant is coming from the adaptive access itself, not from whether the inverse call happens before or after a forward one.
Simon’s attack on one-round Even-Mansour needs adaptivity; two rounds dodge it.
> two rounds dodge it.
that sounds too tidy. the issue is the adversary model, not just “more rounds”, and i’d want to see the proof survive fully interleaved inverse queries before believing that.