L13-PALLADIUM Datasheet, PDF (4/7 Pages) List of Unclassifed Manufacturers – Palladium, Zero Knowledge

4
3 ZERO-KNOWLEDGE PROOFS
Figure 2: 3-coloring of an undirected graph with 5 vertices
Verifier: points to 2 adjacent vertices Prover: removes stickies from the two selected vertices Verifier:
checks that two vertices have different colors (if not ⇒ not OK)
Output:OK
This algorithm is polynomial in the size of the graph (V + E, where V is the set of vertices and E
is the set of edges), assuming that t is bounded by a polynomial in |V | and |E|.
What are the properties of this protocol?
- Completeness: if Prover knows coloring, Verifier always accepts
- Soundness: if Prover doesn’t know coloring, he will be caught with significant probability.
o
Prob(Verifier
picks
“bad
edge”)
≥
1
|E|
o
Prob(Verifier
picks
“good
edge”)
≤
1
−
1
|E|
o
So
in
t
trials:
Prob
(bad
prover
escapes
detection)
≤
(1 −
1
|E|
)^t
≤
−t
e ^|E|
Since e^x ≥ 1 + x, this probability is bounded above by e^−t/|E|, which for t = |E|20 is less than e^−20.
Q: If t is |E| × 20 , aren’t you exposing more than the number of edges in the graph?
A: Yes, but each time you expose an edge it could be from any of the 6 piles (the Verifier doesn’t
know which pile the user picks)
We will try to show that the Verifier doesn’t learn anything if this scheme is followed. The idea is
that there is no correlation between pairs of colors revealed by each edge.
Q: Why can’t the Prover cheat by just showing different colors for each pair of vertices requested by
the Verifier (that is, choosing the vertex colors right before revealing them and that way guaranteeing