Cryptography Reference
In-Depth Information
secrecy is established only a posteriori by the receiver disclosing the coin tosses it used
in the commit phase. In our case, the prover plays the role of the receiver, and the verifier
plays the role of the sender. It suffices to establish the secrecy property a posteriori,
because if secrecy is not established, then the verifier will reject. In such a case no harm
has been done, because the secrecy of the perfect commitment scheme is used only
to establish the soundness of the interactive proof. Thus, using Proposition 4.8.8, we
obtain the following:
Corollary 4.9.2:
If non-uniformly claw-free collections exist, then every language
in
NP
has a round-efficient zero-knowledge proof system.
4.9.2. Bounding the Power of Cheating Provers
Construction 4.9.1 yields round-efficient zero-knowledge proof systems for
, un-
der the assumption that claw-free collections exist. Using the seemingly more general
assumption that one-way functions exist, we can modify Construction 4.9.1 so as to
obtain zero-knowledge computationally sound proof systems. In the modified proto-
col, we let the verifier use a commitment scheme with computational secrecy, instead
of the commitment scheme with perfect secrecy used in Construction 4.9.1. (Hence,
both users commit to their messages using a perfectly binding commitment scheme,
which offers only computational secrecy.) Furthermore, the commitment scheme used
by the prover must have the extra property that it is infeasible to construct a com-
mitment without “knowing” to what value it commits. Such a commitment scheme is
called
non-oblivious
. We start by defining and constructing non-oblivious commitment
schemes.
NP
4.9.2.1. Non-Oblivious Commitment Schemes
The non-obliviousness of a commitment scheme is intimately related to the definition
of proof of knowledge (see Section 4.7).
Definition 4.9.3 (Non-Oblivious Commitment Schemes):
Let
(
S
R
)
be a (per-
fectly binding) commitment scheme as in Definition 4.4.1. We say that the commit-
ment scheme is
non-oblivious
if the prescribed receiver R constitutes a knowledge
verifier that is always convinced by S for the relation
((1
n
,
,
r
)
view
S
(
σ,
1
n
,
s
)
,
r
,
m
)
,
(
σ,
s
)) :
m
=
R
(1
n
where, as in Definition 4.4.1,
view
S
(
σ,
1
n
,
s
)
denotes the messages received by the
R
(1
n
,
r
)
interactive machine R, on input
1
n
and local coins r , when interacting with
machine S (which has input
(
σ,
1
n
)
and uses coins s).
It follows that the receiver's prescribed program,
R
, may accept or reject at the end
of the commit phase and that this decision is supposed to reflect the sender's ability
to later come up with a legal opening of the commitment (i.e., successfully complete
