What is the simplest known scheme that allows one to, given an input x : {0,1}* for which F(x) == y where F : {0,1}* -> {0,1}*, elaborate a proof p : {0,1}* such that V(p, y, F) iff F(x) == y?
$\begingroup$
$\endgroup$
11
-
$\begingroup$ Your question seems to ask for an interactive ZK proof based on one-way function, but if so, why do you mention the random oracle model in your question? The random oracle model is not an assumption, it's an idealized model to give arguments of security, and it is often use to make standard public-coin ZK proofs non-interactive. $\endgroup$– Geoffroy CouteauMay 10, 2017 at 21:10
-
1$\begingroup$ @Geoffroy Couteau then I probably don't understand wrong what the Random Oracle Model stands for, I thought it meant "an idealized model where you can assume the existence of non-invertible, collision-resistant, random-looking functions", which would be a synonym to what I asked on the question body. I don't understand how both statements are different. $\endgroup$– MaiaVictorMay 10, 2017 at 21:33
-
$\begingroup$ You do not need the ROM to assume non-invertible random-looking collision-resistant hash functions - you just have to use a concrete hash function in the standard model for which we conjecture these properties. The ROM is a model in which you replace the hash function by an oracle, i.e., you have some black-box access to a true random function (which cannot exist in the real world, unlike, for example, collision-resistant hash functions). But there are simple interactive ZK proofs in the standard model assuming collision-resistant hash functions, or even OW functions; the ROM is not necessary. $\endgroup$– Geoffroy CouteauMay 10, 2017 at 21:40
-
1$\begingroup$ You can't do this for arbitrary existential statements - for example, the statement "For the program P, does there exist an input x for which P(x) does not terminate?" can't be proven by any interactive proof system. $\endgroup$– pg1989May 11, 2017 at 1:03
-
1$\begingroup$ Does the verifier know F^-1? What is trivial is that you could commit to an x by sending p as the hash of x, then verification would require to publish x or to reverse F. $\endgroup$– eckesMay 11, 2017 at 2:06
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
2
What is the simplest known scheme that allows one to, given an input x : {0,1}* for which F(x) == y where F : {0,1}* -> {0,1}, elaborate a proof p : {0,1} such that V(p, y, F) iff F(x) == y?
First, in your definition the verifier needs to know $F,y$ and $p$, as he uses those in the verification process.
As @RickyDemer pointed out, if $F$ is some invertible function, the zero knowledge property trivially holds - but that might not be what you wanted:
- If $F$ is invertible, the verifier can calculate $F^{-1}(y) = x$
- Knowing $x$ and the distribution of the random coins used in the proof, the verifier can just act like the prover.
However, this is probably not what you had in mind with zero knowledge in the title. It does not mean, the verifier can't learn $x$. In order to achieve that, we need that $F$ is some kind of a one-way function. If we model the prover as computationally unbound, we could also assume that the evaluation of $F$ is super-polynomial, and in that case the polynomially bound verifier could not act like the unbounded prover - but then any verification would most likely also be super-polynomial.
If we require $F$ to be a one-way function of some kind, a proof of knowing a preimage can take different forms, depending on the function $F$. The most common and simple ones utilize algebraic structures and known hard problems like the discrete logarithm. More generally, for any NP-complete problem you can create a zero knowledge proof (assuming one-way functions exist), and graph coloring is a classic example. For non-algebraic statements, there is also some research, but it's much more complicated. Here are two related questions, which have some relevant references:
-
$\begingroup$ "... he immediately knows $x$", so in that case, the zero-knowledge property trivially does hold, since he can use $x$ to act exactly as the prover. $\endgroup$– user991May 16, 2017 at 9:34
-
$\begingroup$ @RickyDemer I edited the answer, you're absolutely right. $\endgroup$– tyloMay 16, 2017 at 11:04