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?
