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?

  • $\begingroup$ 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. $\endgroup$ Jan 8 at 13:25


Your Answer

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