Cryptography Reference
In-Depth Information
Karp-reducible) to
G
3
C
. Namely, there exists a polynomial-time-computable function
f
∈
G
3
C
. Last, we observe that the standard
reduction of
L
to
G
3
C
, denoted
f
L
, has the following additional property:
such that
x
∈
L
if and only if
f
(
x
)
•
There exists a polynomial-time-computable function, denoted g
L
, such that for every
(
x
,w
)
∈
R
L
, it holds that g
L
(
x
,w
)
is a 3-coloring of f
L
(
x
)
.
We stress that this additional property is not required by the standard definition of a
Karp reduction. Yet it can be easily verified (see Exercise 16) that the standard reduction
f
L
(i.e., the composition of the generic reduction of
L
to
SAT
, the standard reductions
of
SAT
to 3
SAT
, and the standard reduction of 3
SAT
to
G
3
C
) does have such a
corresponding
g
L
. Using these conventions, we are ready to “reduce” the construction
of zero-knowledge proofs for
NP
to a zero-knowledge proof system for
G
3
C
.
Construction 4.4.9 (A Zero-Knowledge Proof for a Language
L
∈
NNP
):
Common input:
A string x (supposedly in L).
Auxiliary input to the prover:
A
witness
,
w
, for the membership of x
∈
L (i.e., a
w
,w
∈
string
such that
(
x
)
R
L
).
def
=
Local pre-computation:
Each party computes G
f
L
(
x
)
. The prover computes
def
=
ψ
g
L
(
x
,w
)
.
Invoking a zero-knowledge proof for
G
3
C
:
The parties invoke a zero-knowledge
proof on common input G. The prover enters this proof with auxiliary input
ψ
.
Clearly, if the prescribed prover in the
G
3
C
proof system can be implemented in prob-
abilistic polynomial time when given an
-witness (i.e., a 3-coloring) as auxiliary
input, then the same holds for the prover in Construction 4.4.9.
NP
Proposition 4.4.10:
Suppose that the sub-protocol used in the last step of
Construction 4.4.9 is indeed an auxiliary-input zero-knowledge proof for G
3
C.
Then Construction 4.4.9 constitutes an auxiliary-input zero-knowledge proof
for L.
Proof:
The fact that Construction 4.4.9 constitutes an interactive proof for
L
is
immediate from the validity of the reduction (and the fact that it uses an interactive
proof for
G
3
C
). At first glance it seems that the zero-knowledge property of
Construction 4.4.9 follows just as easily. There is, however, a minor issue that
one should not ignore: The verifier in the zero-knowledge proof for
G
3
C
invoked
in Construction 4.4.9 possesses not only the common-input graph
G
but also
the original common input
x
that reduces to
G
. This extra information might
have helped this verifier to extract knowledge in the
G
3
C
interactive proof if it
were not the case that this proof system is also zero-knowledge with respect to
the auxiliary input. Details follow.
Suppose we need to simulate the interaction of a machine
V
∗
with the prover of
Construction 4.4.9, on common input
x
. Without loss of generality, we can assume
that machine
V
∗
invokes an interactive machine
V
∗∗
that interacts with the prover
241
