26-05-2012, 11:55 AM
Alternative Variants of Zero-Knowledge Proofs
Alternative Variants of Zero-Knowledge Proofs.pdf (Size: 787.14 KB / Downloads: 24)
Introduction
Cryptography, Greek for hidden writing, is the science of how parties can communicate
without trusting each other and/or the environment they are communicating
in. Traditionally the science of cryptography was primarily used by the military
and the secret services in order to achieve secure message transmission, but with the
recent explosion of electronic communication, cryptography is today the concern of
almost anyone.
The past three decades have witnessed an unprecedented progress in the eld of
cryptography. In these years basic cryptographic notions such as encryption1 and
digital signatures2 have been put under rigorous treatment and numerous solutions
realizing these task have been proposed. Furthermore, during these years several
new and exciting cryptographic notions/applications have emerged.
Zero-Knowledge Proofs
One of the most basic and important examples of cryptographic notions is the one
of zero-knowledge interactive proof systems [38]. Loosely speaking, zero-knowledge
proofs are interactive protocols3 that enable one entity (called the prover) to convince
another entity (called the verier) of the validity of a mathematical statement,
without revealing anything beyond the assertion of the statement. For concreteness,
assume that a prover wants to convince a verier that a certain equation has
a solution. A naive way of doing this would be by simply giving the solution to
the verier. This approach, however, reveals information to the verier (namely
the solution to the equation). A zero-knowledge proof, on the other hand, would
convince the verier without revealing anything else.
Concurrent Composition of Cryptographic Protocols
The original setting in which cryptographic protocols were investigated consisted
of a single execution of the protocol at a time. That is, two parties execute a
single protocol once, without being able to communicate with the outside world. A
more realistic setting, especially in the time of the Internet, is one that allows the
concurrent execution of protocols [27, 25]. In the concurrent setting many protocols
are executed at the same time, involving multiple parties that may be talking with
the same (or many) other parties simultaneously.
LIMITATIONS OF ZERO-KNOWLEDGE PROOFS 3
executions. In particular, the adversary may use messages received in one of the
executions in order to cheat in a dierent execution.
It would be most desirable to have cryptographic protocols that retain their
security properties even when executed concurrently. Unfortunately, it has been
observed that the construction of such protocol seems more problematic than in the
stand-alone setting.
Limitations of zero-knowledge proofs
Although the notion of zero-knowledge proofs has proved very useful in the design of
cryptographic protocols, many limitations are also known, both in the stand-alone
setting and in the concurrent setting.