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

6
3 ZERO-KNOWLEDGE PROOFS
Figure 4: Representation of the 6 permutations of a given graph 3-coloring
Private key of prover: x s.t. 0 ≤ x < q
Do t times:
- Prover: picks k ∈ Z_q, sends u = g^k mod p
- Verifier: computes b ∈_R {0, 1}, sends b to Prover
- Prover: sends l = k + bx mod q
- Verifier: computes u × y^b = g^l mod p
Note that the Prover can always succeed in each round with probability 1/2, by guessing b first,
then setting u = g^l/y^b.
This protocol is sound and complete. The Verifier will always accept an honest Prover’s proof, and
a cheating prover will be caught with significant probability in each round.
Now the claim is that the protocol is ZK. We can play this game all day long and there is no way
the Verifier will learn any information about x. The Verifier just gets a huge list of u, b, and l during
each iteration, but the claim again is that this tells us nothing about x.
To demonstrate our claim, we can generate transcripts (on our own) with the proper distribution:
- pick b ∈_R {0, 1}
- pick l ∈_R Z_q
- pick u = g^l/y^b mod p