0
$\begingroup$

I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:

  • Currently, you can only select adjacent pairs of nodes to check. Would the proof still be zero knowledge if you could pick arbitrary pairs of nodes to check?

I think it would still be "zero knowledge" because it shouldn't leak information to verifier, but there won't be a proof if you select non-adjacent pairs since the reveal phase doesn't prove anything. Is this a trick question?

Improve this question
$\endgroup$
1
  • $\begingroup$ You are correct. $\endgroup$
    – vy32
    Sep 29, 2017 at 19:20

1 Answer 1

Reset to default
3
$\begingroup$

Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not. It's not a trick question -- just a bad one.

Improve this answer
$\endgroup$

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