Boston University / CLA
Computer Science Dept
CLA CS-101: Introduction to Computers
----------------------------------------------------------------------------
Zero Knowledge Proofs
Imagine that you discovered a gold mine (or, to be more realistic, a program
that beats the odds of the stock market) and would like to convince a
wealthy corporation to give you some money to pursue your discovery.
Obviously, it is not a very smart idea for you to reveal your
secret---whether it is the location of the gold mine or your algorithm for
milking wall street---to prove to the other party that indeed you are
truthful. In brief, the problem that needs to be solved is: How could one
party convince the other that it knows a secret without revealing that
secret?!
In many computer applications, the above problem arises and there are
techniques that allow for one to reveal the fact that they "know" something
without revealing that thing. These techniques are called "zero-knowledge
proof techniques". They are called "zero-knowledge proofs" because they
"prove" something without revealing any knowledge (not even partial) about
that "thing".
Let's go through a simple example. Suppose that I claim that I have the
power to "count the number of leaves on any tree just by looking at the tree
for one second!" Obviously, I refuse to tell you "how", because then I would
reveal my secret. How could you establish the truthfulness of my claim? How
could my claim be "proven" without revealing any knowledge about it? Here is
one way of doing it! You take me to your backyard, show me a big tree and
ask me to tell you how many leaves it has. I look at it for a second and
tell you "4,677,451 leaves". Of course you can't check my answer and you are
not about to climb the tree and count its leaves! But, here is what you
could do. Ask me to go back into the house and make sure that I am not
looking at you. Then, you climb the tree and cut out some leaves, say "52
leaves". Now, you ask me to get out to the backyard and ask me to count the
leaves again. If I come up with anything other than "4,677,399 leaves", then
I am bluffing, and you have a proof! Otherwise, I may indeed have a magic
way of counting leaves. But then, you may think, it may be "just luck".
Well, to get the "luck" out of the way, you may want to repeat the process
several times. If (say) I keep coming up with the right answer for 20 times,
then it must be the case that "I know how to count leaves on trees", because
the likelihood that I am just lucky becomes incredibly small after repeating
the process for 20 times. [Note: In class we have gone through a simple
numerical computation to show "how improbable it is that I am just lucky"]
----------------------------------------------------------------------------
(C) Copyright 1995.
This document has been prepared by Professor Azer Bestavros
.
Created on: April 13, 1995.
Updated on: April 12, 1995.
----------------------------------------------------------------------------