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

3.3 Proof using discrete logs
5
Figure 3: High-level overview of exchange between Prover and Verifier
that the coloring works)?
A: The Prover actually commits to a coloring before hand, so all he can do is remove the stickies
and expose the vertex colors.
Q: Does the Prover need to know all possible colorings in this scheme?
A: No (look above). The Prover picks one coloring and just permutes the color assignments (so the
coloring scheme actually remains the same).
Our informal proof of “zero-knowledge”:
The Verifier gets a transcript of his conversation with the Prover and nothing more (transcript
embodies all information obtained by the Verifier). We are assuming that the Prover takes the same
amount of time to respond to each challenge (so, for instance, the Verifier can’t learn anything extra
based on the time taken for the Prover to respond).
The information we get from this protocol is:
This distribution of transcripts can be simulated by verifier, without Prover’s help.
3.3 Proof using discrete logs
We now give another illustration of a zero-knowledge protocol. The goal of this protocol is for the
Prover to convince the Verifier that he knows the discrete logarithm x of a public value (his public
key) y.
Global public parameters: prime p, prime q dividing p − 1, g of order q.
Public key of prover: y = g^x mod p