Cryptography Reference
In-Depth Information
The soundness requirement, in turn, must hold for every possible prover strategy.
Consequently, an interactive proof system should allow a prover to convince a
verifier of the validity of a true statement (completeness requirement), whereas
no prover strategy should be able to fool the verifier to accept a false statement
(soundness requirement).
It is obvious that interactive proofs are usually more powerful than conven-
tional ones (i.e., they sometimes allow the proof of statements that cannot be proven
conventionally). More specifically, it has been shown that when both randomization
and interaction are allowed, then the proofs that can be verified in polynomial time
are exactly those that can be generated with polynomial space [22].
Remember from Section 12.2 that two probability ensembles are poly-time
indistinguishable if no PPT algorithm (acting as a polynomial-time statistical test
or distinguisher) can tell them apart. Having this notion of computational indistin-
guishability in mind, one can say that an interactive proof between prover
P
and a
verifier
V
is
computationally zero knowledge
if for every PPT algorithm
V
,repre-
senting a dishonest verifier, there exists an efficient program
S
, called the
simulator
,
whose output
T
is computationally indistinguishable from the communication
T
taking place between
P
and
V
in a real protocol execution.
Zero knowledge implies the highest possible security for the prover
P
.Any-
thing a verifier can compute after performing the protocol with
P
, he or she can
also compute by himself or herself, in a way that is identical or at least statistically
indistinguishable from what would happen if the actual protocol has been performed.
More importantly, anybody can simulate transcripts of protocol executions that are
statistically indistinguishable from a real execution of the protocol. We overview and
discuss three exemplary zero-knowledge authentication protocols next.
17.3.2
Fiat-Shamir
Soon after Goldwasser, Micali, and Rackoff had introduced the notion of a zero-
knowledge proof, Amos Fiat and Adi Shamir
5
found a way to implement a zero-
knowledge protocol for authentication and/or digital signature generation and ver-
ification [23]. The Fiat-Shamir authentication protocol takes its security from the
fact that computing square roots and factoring a modulus are computationally
equivalent—that is, a square root modulo
n
can be efficiently computed if and only
if the factorization of
n
is known (see Section 3.3.7).
6
Similar to the RSA public key cryptosystem, let
p
and
q
be two primes and
n
be their product (i.e.,
n
=
pq
). Let the prover hold a private key
x
∈
Z
n
and
x
2
A
a corresponding public key
y
A
≡
(mod
n
). The Fiat-Shamir authentication
5
Adi Shamir is a co-inventor of the RSA public key cryptosystem.
6
The Rabin asymmetric encryption system is based on the same principle.
