Here's an example of a zero knowledge proof.  Abstractly, a zero knowledge
proof is an interactive proof with a prover and a verifier, where the prover
convinces the verifier of a statement (with high probability) without
revealing any information about how to go about proving that statement.
Hopefully the example will make it all clear.

First, our assumptions.  We're going to arithmetic mod n, where n = pq, p
and q primes.  Factoring n is assumed to be intractible.

Rabin showed in [RabinFunc] that finding square roots mod n is equivalent to
factoring n.  That is, if you have an algorithm that can find a square root
of a number mod n, then you can use that algorithm to factor n.  Our zero
knowledge proof will consist of rounds of interaction which shows that the
prover knows a square root of a published number, where we do not reveal any
new information about the square root.  It is known that there exists a
square root to this number (public knowledge), i.e., it is a quadratic
residue.  The factors of the modulus n may be entirely secret.  (U. Feige
shows a refinement in [FFS] which allows the published number to be a
non-quadratic residue of a particular form as well, thus revealing less
information; in either case, runs of the protocol itself reveals no new
information.)

The prover, P, publishes the quadratic residue $v$ for which P claims to
know a root $s$.

When P wishes to prove its knowledge of $s$ to the verifier, V, P runs
several rounds of interaction.  In each round, P choses a new random number
$r$ and sends $x = r^2 \bmod n$ to V.  Now, V choses a random bit $b$, and
sends it to P.  P replies with $y = r s^b$.  To verify P's claim, V computes
$y^2$ and compares it with $x v^b$.

Now, let's do the analysis.  The first claim is that only P can successfully
complete the protocol for both possible values of $b$.  This is clear since
knowing $y_1 = r s$ when $b = 1$ and $y_2 = r$ when $b = 0$ means you also
know $s$, since $y_1/y_2 = s$.  The second claim is that an imposter P' who
does not actually know $s$ can succeed with a probability of exactly 1/2
each round:  to see this, notice that if P' guesses correctly that $b = 0$,
then it can just follow the protocol and succeed; on the other hand, if P'
guesses that $b = 1$, P' can generate $x$ by chosing a random number $t$ and
setting $x = t^2 / v$.  The response is $y = t$.  The third claim is that no
new information is released.  To see this, consider what an eavesdropper E
hears.  In the case of the random bit $b = 0$, E sees a random numer $r$ and
its square $x$; in the case of $b = 1$, E sees the numbers $rs$ and $x =
(rs)^s/v$.  These are numbers that the eavesdropper could have generated in
a closet.  More precisely, a simulator S can run both sides of the protocol,
and by using advanced information as to the value of the random bit (model
is a TM with an auxiliary input tape of random bits), S can simulate the
protocol without knowledge of $s$.

Each round of the proof shows that there is a 1/2 chance that a prover P''
might not actually know $s$.  Iterating 20 times gives a probability of less
than 2^-20 or .0000009536 that P'' does not actually know $s$.

Such zero knowledge proofs can be used for authentication -- the value of
$v$ can be generated from a randomly chose $s$, and $v$ is widely published.
A successful zero knowledge proof showing knowledge of $s$ authenticates
identity.  In [StrongboxIn25th], Doug Tygar (my advisor) and I show how to
obtain superexponential scaling in security modulo the factorization
assumption, run the protocol in constant rounds while retaining the zero
knowledge property, and simultaneously perform key exchange.

-bsy

==========

@TechReport(RabinFunc,
Author="Michael Rabin",
        Institution="Laboratory for Computer Science,
                 Massachusetts Institute of Technology",
        Title="Digitalized Signatures and Public-Key
                Functions as Intractable as Factorization",
        Key="Rabin",
        Year=1979,
        Month="January",
        Number="MIT/LCS/TR-212")

@InProceedings(FeigeFiatShamir,
        Key="Feige",
        Author="Uriel Feige and Amos Fiat and Adi Shamir",
        Title="Zero Knowledge Proofs of Identity",
        Year=1987,
        Pages="210-217",
        Booktitle="Proceedings of the 19th ACM Symp. on Theory of Computing",
        Month="May")

@Inproceedings(StrongboxIn25th,
        Key="Tygar and Yee",
        Author="J. D. Tygar and Bennet S. Yee",
        Title="Strongbox:  A System for Self Securing Programs",
        Organization = "ACM",
        Booktitle="CMU Computer Science:
                25th Anniversary Commemorative",
        Year = 1991)

-- 
Bennet S. Yee           Phone: +1 412 268-7571          Email: bsy+@cs.cmu.edu
CS Dept, SCS, Carnegie Mellon Univ, 5000 Forbes Ave, Pittsburgh, PA 15213-3891

------------------------------