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?

  • $\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
    Commented Nov 14, 2023 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
    Commented Nov 14, 2023 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$ Commented Nov 14, 2023 at 7:50


Your Answer

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