2
$\begingroup$

Below is a suggestion for a zero knowledge proof for the existence of both a $k$-independent set (IS) AND a $k$-vertex cover (VC). It was given as an example of an interactive proof that is not computational zero-knowledge due to leakage of information, and I'm having trouble understanding why.

  • Peggy selects a random permutation of the graph, generates a commitment per (permuted) edge and sends them to Victor.

  • Victor selects a random $b \in \{0,1\}$ and sends to Peggy.

  • If $b=0$, Peggy sends the permutation and and reveals the commitments. Victor verifies the two.

  • If $b=1$, Peggy sends:

    1. The (permuted) vertices in the VC and reveals the commitments for all edges involving only vertices outside of VC.

    2. The (permuted) vertices in the IS and reveals the commitments for all edges involving only vertices inside of IS.

    Victor verifies the edges revealed in both are $0$ (no edge).

After a long time of trying to see what the leakage of information is on some random graphs, I'm just not seeing it. I understand that the combination of the two sets is somehow supposed to be informative, but how does one go about constructing a counter example that demonstrates this?

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.