Cryptography Reference
In-Depth Information
4
Zero-Knowledge
Zero-knowledge proofs, introduced by Goldwasser, Micali and Rack-
off (81), provide a powerful tool for the design of cryptographic pro-
tocols. Loosely speaking, zero-knowledge proofs are proofs that yield
nothing beyond the validity of the assertion. That is, a verifier obtain-
ing such a proof only gains conviction in the validity of the assertion
(as if it was told by a trusted party that the assertion holds). This is
formulated by saying that anything that is feasibly computable from
a zero-knowledge proof is also feasibly computable from the (valid)
assertion itself. The latter formulation follows the simulation paradigm,
which is discussed next.
4.1
The simulation paradigm
A key question regarding the modeling of security concerns is how
to express the intuitive requirement that an adversary “gains nothing
substantial” by deviating from the prescribed behavior of an honest
user. Our approach is that the adversary
gains nothing
if whatever it
can obtain by unrestricted adversarial behavior can also be obtained
within essentially the same computational effort by a benign behav-
