I am learning zero knowledge protocols, and studied the GMW protocol for 3-Coloring (https://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf). A similar proof is also presented in Oded Goldreich's Foundations of Cryptography textbook. In this proof, the zero-knowledgeness property uses the hiding property of commitments. As described in the above resources, there are some subtleties in the proof.

However, most of the recent lecture notes and resources present a much simpler proof of zero-knowledgeness (e.g. Yehuda Lindell's tutorial: https://eprint.iacr.org/2016/046.pdf). In particular, these proofs use the following hybrid simulator: the hybrid simulator behaves like the simulator, except it also uses the 3-Coloring witness $(col_1, col_2, ..., col_n)$. This hybrid simulator picks a uniformly random edge $e'$ and a random permutation $\pi$ to randomise the coloring. It computes a commitment to $\pi(col_1), \pi(col_2), \ldots, \pi(col_n)$ and sends these commitments to the verifier. The verifier sends an edge $e$. If $e\neq e'$, the hybrid simulator restarts the simulation.

It is easy to show that the real world interaction is identical/statistically indistinguishable from the hybrid simulator's output. Second, it is not too difficult to use the commitment's hiding property to show that the hybrid simulator's output is comp. indistinguishable from the real simulator's output.

My question: am I missing some subtleties in this proof via hybrid simulator?



Your Answer

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

Browse other questions tagged or ask your own question.