Cryptography Reference
In-Depth Information
Figure 12.4: In a zero-knowledge proof, the colors of the nodes are
encrypted and sent to the skeptical inquirer who asks to have two
adjacent nodes revealed.
where + stands for concatenation. Ship the encrypted versions
to the skeptical inquirer.
4. The skeptical inquirer chooses an edge at random from the
graph, (
v a ,v b ) and presents it to you.
5. You ship
p b to the skeptical inquirer, who uses them to
decrypt the encrypted version of the colors,
p a and
v b ) .If
the two are different, the skeptical inquirer knows that you've
proven that you know how to color at least one part of the
graph. Figure 12.4 shows two adjacent nodes being revealed.
f (
v a ) and
f (
This process should be repeated until the skeptical inquirer is
satisfied. If the edges are truly chosen at random, any mistakes in
the coloring stand an equal chance of being revealed at each step.
The randomness prevents the prover from anticipating the choice
and selecting
f . Eventually, any weakness or miscoloring will show
through.
Zero knowledge proofs like this may be useful in the world of hid-
den information because they allow the information hider to control
how and when the information is revealed to another person. The
structure of the proof, however, guarantees that no information is re-
vealed. The proof can't be repeated by someone else or used as a
basis to remove the information. This solution may be useful for wa-
termarking applications where a copyright holder may want to prove
 
Search WWH ::




Custom Search