Cryptography Reference
In-Depth Information
of the
G
3
C
interactive proof, on common input
G
f
L
(
x
), and has auxiliary
input
x
. Using the hypothesis that the
G
3
C
interactive proof is auxiliary-input
zero-knowledge, it follows that there exists a simulator
M
∗∗
that on input (
G
=
x
)
simulates the interaction of
V
∗∗
with the
G
3
C
prover (on common input
G
and the
verifier's auxiliary input
x
). Hence the simulator for Construction 4.4.9, denoted
M
∗
, operates as follows: On input
x
, the simulator
M
∗
computes
G
,
def
=
f
L
(
x
) and
outputs
M
∗∗
(
G
,
x
). The proposition follows.
An alternative way of resolving the minor difficulty addressed earlier is to observe that
the function
f
L
(i.e., the one induced by the standard reductions) can be inverted in
polynomial time (see Exercise 17). In any case, we immediately get the following:
Theorem 4.4.11:
Suppose that there exists a commitment scheme satisfying the
(non-uniform) secrecy and unambiguity requirements. Then every language in
NP
has an auxiliary-input zero-knowledge proof system. Furthermore, the pre-
scribed prover in this system can be implemented in probabilistic polynomial time
provided it gets the corresponding
NP
-witness as auxiliary input.
We remind the reader that the condition of the theorem is satisfied if (and only if )
there exist (non-uniformly) one-way functions: See Theorem 3.5.12 (asserting that one-
way functions imply pseudorandom generators), Proposition 4.4.5 (asserting that pseu-
dorandom generators imply commitment schemes), and Exercise 13 (asserting that
commitment schemes imply one-way functions).
Applications: An Example
A typical application of Theorem 4.4.11 is to enable one party to prove some property
of its secret without revealing the secret. For concreteness, consider a party, denoted
S
, that makes a commitment to another party, denoted
R
. Suppose that at a later stage,
party
S
is willing to reveal partial information about the committed value but is not
willing to reveal all of it. For example, party
S
may want to reveal a single bit indicating
whether or not the committed value is larger than some value specified by
R
. If party
S
sends only this bit, party
R
cannot know if the bit sent is indeed the correct one. Using
a zero-knowledge proof allows
S
to convince
R
of the correctness of the revealed bit
without yielding any additional knowledge. The existence of such a zero-knowledge
proof follows from Theorem 4.4.11 and the fact that the statement to be proved is of
NP
type (and that
S
knows the corresponding
NP
-witness).
A reader who is not fully convinced of the validity of the foregoing claims (i.e., regarding
the applicability of Theorem 4.4.11) may want to formalize the story as follows: Let
v
denote the value to which
S
commits, let
s
denote the randomness it uses in the commitment
phase, and let
c
def
) be the resulting commitment (relative to the commitment scheme
C
). Suppose that
S
wants to prove to
R
that
c
is a commitment to a value greater than
u
.So
what
S
wants to prove (in zero-knowledge) is that
there exist
=
C
s
(
v
v
and s such that c
=
C
s
(
v
)
and
-type statement, and
S
knows the corresponding
NP
-witness (i.e., (
v,
s
)), since it has picked
v
and
s
by itself.
242
v>
u
, where
c
and
u
are known to
R
. Indeed, this is an
NP
