Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(1)$ is even and $0$ if $\sigma^{-1}(1)$ is odd. This is the famous permutation inversion problem and it can be proven that this problem requires an exponential number of queries to the permutation oracle. There are many ways to prove this lower bound, like using the hybrid argument, or the adversary method, or showing this problem is equivalent to Grover's search. I am specifically looking for a hybrid argument.

I found one here (Theorem $3.6$), but it deals with random permutation oracles instead of a fixed oracle. I don't think that condition should be necessary. Also, the proof seems very complicated. Can someone provide a simplified treatment?

  • 2
    $\begingroup$ Though the proof is done for a random permutation oracle, there is a standard method that applies the Borel-Cantelli lemma to extract a single "hard to invert" oracle from the distribution; see for example Impagliazzo-Rudich 1989 which introduced this technique in the context of providing an oracle separation between one way functions and public key encryption. $\endgroup$ Commented Sep 26, 2020 at 9:43


Your Answer

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

Browse other questions tagged or ask your own question.