0
$\begingroup$

So I think I understand how zero knowledge protocol with 3-coloring is supposed to work. But in an attempt to increase soundness of the protocol, we allow the verifier V to challenge two edges per repetition instead of one. I'm told that this breaks the zero knowledge property, but I'm not exactly sure how to prove it.

How would a malicious verifier V that repeats this modified zero knowledge protocol a polynomial number of times be able to construct an honest P's entire witness? In other words, how could V learn to color the entire graph when it can open two edges at a time when one edge at a time doesn't work? And why does it have to br a malicious verifier that breaks the property and not an honest verifier?

Improve this question
$\endgroup$
3
  • $\begingroup$ Note that breaking ZK does not require the malicious verifier to learn the witness. It merely needs to learn anything it didn't already know. $\endgroup$
    – Maeher
    Nov 14 at 5:34
  • $\begingroup$ @Maeher By learning "anything it didn't already know", would that be something like learning the colors of any of the edges that are still locked after revealing two edges? I suppose it could be possible, but I'm not sure if that's the case. $\endgroup$
    – HughJass24
    Nov 14 at 5:48
  • 1
    $\begingroup$ Learning exact colors would be tough indeed, but think about learning information of the forme "these two vertices have the same color in the 3-coloring" or "these two vertices have different colors in the 3-coloring". (1) do you see how to learn that with two edge queries? (2) bonus (not needed as Maeher pointed out) can you see how, after enough repetition, this actually allows the verifier to extract the full witness (up to permutation of the colors)? $\endgroup$
    – Geoffroy Couteau
    Nov 14 at 7:50

0

Reset to default

Your Answer

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