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?

  • 1
    $\begingroup$ I don't remember that part of the paper and don't have the time to reread it right now, so this is a guess: The machine that can evaluate $f$ in polynomial time that you want to use to verify the relation is an oracle machine. It is likely that Theorem 3.1 does not actually apply to oracle machines. $\endgroup$
    – Maeher
    Commented Dec 5, 2023 at 20:13
  • 1
    $\begingroup$ @Maeher I thought the same but it's not clear why. The theorem 4.2 suggest this but I don't know the exact reason. It seems possible to uniformly generate even if there is this oracle to me, but maybe the problem is that oracle can be an arbitrary random oracle, in an infinite space. In any case, I don't have a confident answer. $\endgroup$
    – Pur2all
    Commented Dec 6, 2023 at 9:14


Your Answer

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