Cryptography: An Introduction to Zero Knowledge Proof Systems -- Yogishwar Maharaj, June 28, 2004

<p>

An archetypical cryptographic problem consists of providing mutually 
distrustful parties with a means of disclosing "pieces of information."
It refers to settings in which parties posses secrets and they wish to 
reveal parts of these secrets.  The secrets are partially or fully 
determined by some publicly known  information.  The question is how to 
allow verification of newly revealed parts of the secret without 
disclosing other parts of the secrets. 

As an example, suppose that all users in a system keep backups of their 
entire file systems encrypted using their secret keys, in publicly 
accessible storage media.  Suppose that at some point, user Alice wishes 
to reveal to user Bob the plain text of some record in one of her files.  
A "trivial" solution is for Alice simply to send the text record to Bob.  
The "problem" with this solution is that Bob has no way of verifying 
that Alice has sent him the true record, rather than some arbitrarily 
chosen one.  Alice must "convince" or prove to Bob that the record is 
correct without revealing "any" information.  Such proofs, whenever they 
exist are called zero-knowledge proofs. 

It turns out that zero-knowledge proof systems have further reaching 
applications than solving engineering problems.  The main result I want 
to present is a method for constructing zero-knowledge proof systems for 
every language in the complexity class NP.