10
$\begingroup$

I have learned that a zero-knowledge (ZK) proof system can be constructed by making use of the three-color problem. In this particular case, the proof system also happens to be proof of knowledge (POK), i.e. any prover necessarily needs to know a witness in order to convince the verifier.

Are there ZK proof systems which are not POK?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of.

Improve this answer
$\endgroup$
3
  • $\begingroup$ From what I understand, in Goldreich-Kahan we have almost the same thing as the classical 3-color ZK proof system, but the prover is additionally required to commit itself beforehand to the challenge edges, which means the prover can then choose its color permutations based on these commits. So this means that a knowledge extractor cannot simply rewind the prover until it eventually spits out the whole coloring, right? $\endgroup$
    – dkaeae
    Jun 21, 2016 at 8:34
  • $\begingroup$ @dkaeae I guess you mean that the verifier commits beforehand; yes this is the case. Since the verifier is committed, it cannot rewind the prover and get answers to different queries. (Formally, to make the extractor fail, construct a prover who generates the random coloring and commitments by applying a PRF to the query commitment from the verifier.) $\endgroup$
    – Yehuda Lindell
    Jun 21, 2016 at 13:23
  • $\begingroup$ Oh yeah, that's a typo... I did mean the verifier must commit itself to the challenge edges (and not the prover). $\endgroup$
    – dkaeae
    Jun 21, 2016 at 13:39
3
$\begingroup$

Sure. ​ For any total relation,

Protocol: ​ verifier accepts
Simulator: ​ run the adversary

is a zero-knowledge proof system, but if it's of knowledge
then the search problem is efficiently solvable.
There trivially exist easily-checkable total relations whose search problems are hard:
For example, consider the relation given by xRy if and only if ​ length(y) = 2length(x) .


As far as NP relations go:

If ​ RP = NP ​ then the knowledge extractor can just find a witness on its own, so answers have to be conditional. ​ ​ ​ This answer's proof system is not affected by the relation being TFNP.
The best argument I'm aware of for why there are probably TFNP problems that aren't efficiently solvable is Polynomial Generalized Pigeonhole Principle, given by xRy if and only if
[[it's not the case that x encodes an ordered triple whose entries, in order, are
[a positive integer in unary, a positive integer in binary, a circuit computing a function
from {0,1,2,3,...,((left_entry)-1)*(middle_entry)} to {0,1,2,3,...,(middle_entry)-1}]]
or [with t,n,f being those integers and the function respectively, y is a set of t distinct
elements of {0,1,2,3,...,(t-1)*n} and f gives the same output for each elements of y]].
(Consider collision-resistance of hash functions.)


This sort of thing might be what "the Goldreich-Kahan 4-round ZK proof system" is for,
but looking at his link's pdf does not reveal that system, so I'm mentioning anyway that a way in which one might naturally end up with a ZK proof system that's not a proof of knowledge
is relations over cyclic groups, where the prover shows knowledge of gx but not of x.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If the prover can have success by using $g^x$, wouldn't that make $g^x$ itself the witness? $\endgroup$
    – dkaeae
    Jun 21, 2016 at 8:38
  • 1
    $\begingroup$ That would "make $g^x$ itself the witness" for a related relation, but not for the relation in which the witness is by definition x. ​ ​ $\endgroup$
    – user991
    Jun 21, 2016 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.