How Does ZK Work?

EX: ZKIP for Graph 3 Coloring

On common input graph G and

private prover input coloring p:G {0,1,2}

P: choose random R,

send P(R,G,p) = E(t(v1)),Ö,E(t(vn)) where t = random permutation of p

V: send random edge (vi,vj)

P: decrypt colors t(vi)),t(vj))

If t(vi)) = t(vj)) in all iterations, then V accept

repeat

K times

Ability of P to give colors of all edges Soundness

Fact that P gives color of only one edge Zero Knowledge

Diapositive prÈcÈdente

Diapositive suivante

Revenir ý la premiËre diapositive

Afficher la version graphique