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 <best@cs.bu.edu>.

Created on: April 13, 1995.
Updated on: April 12, 1995.