# Impossibility of uniform generation in random world

I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers.

I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich when I got stuck on a sentence.

First of all, they define a polynomial relation that is any relation $$R$$ verifiable in polynomial time in $$||x|| + ||y||$$, i.e., $$xRy$$ iff we can decide in poly time if $$y$$ is a valid assignment of values for boolean formula $$x$$.
After this, they define Uniform Generation, that is a problem in which given $$x$$, one have to pick a $$y$$ uniformly at random such that $$xRy$$.
A PPT algorithm $$\mathcal{A}$$ is said to be a generator for $$R$$ if given $$x$$ it will output a uniformly chosen $$y$$ with at least $$1/2$$ of chances.
Then they cite a theorem (3.1) that states "For any polynomial-time relation, there exists a PPT algorithm $$\mathcal{A}$$ equipped with a $$\Sigma_2^P$$ oracle that uniformly generates it."

In page 6, at the start of section 4.2 they say that Uniform Generation is impossible in a random world, i.e. a world with a Random Oracle, and they specify that it is impossible to uniform generate an inverse of a random function.
More in detail, they first state the theorem 4.1 which states that a random function is "strongly one-way", which means that it is information-theoretically one-way, i.e., every PPT algorithm has expectation of inverting that is no more than $$poly(n)/2^n$$ for an input of length $$n$$.
Immediately after they say "Theorem 4.1 implies that uniform generation is impossible in a random world; it is impossible to uniformly generate an inverse to the function associated with the oracle."

My question is why it is impossible?
I mean, checking if a given $$y$$ is an image of a one way function $$f$$ evaluated on $$x$$ is clearly a polynomial time relation. Since the algorithm to evaluate $$f$$ is a polynomial algorithm, given $$x$$ and $$y$$ it is simple to check if $$xRy$$ (in this case maybe is better to write $$yRx$$) by computing $$f(x)$$ and check if it is equal to $$y$$.
Why I can't use the theorem 3.1 and say that there exists the algorithm that uniformly generate an inverse?

• I haven’t seen the paper, but just looking at your quotes: first, $f$ is not polynomial-time, only polynomial-time with the random oracle (let’s call it $A$). More importantly, Theorem 3.1 requires a $\Sigma^P_2$ oracle (which, presumably, should be a $(\Sigma^P_2)^A$ oracle if you intend to apply the result to a $P^A$ relation, if it relativizes at all), and you don’t have that here. Jan 8 at 13:25