Cryptography Reference
In-Depth Information
The protocol for arguing that
x
∈
L
consists of the prover committing itself to a
satisfying assignment for
f
(
x
) using the foregoing scheme and the verifier checking
individual clauses by asking the prover to reveal the values assigned to the variables in
these clauses. The protocol can be shown to be computationally sound provided that it
is infeasible to find a distinct pair
). Specifically,
we need to assume that forming collisions under
H
is not possible in sub-exponential
time, namely, that for some
α,β
∈{
0
,
1
}
2
k
such that
H
(
α
)
=
H
(
β
0 forming collisions with probability greater than 2
−
k
δ
δ>
must take at least 2
k
δ
1
δ
and get a computa-
(log
n
)
1
+
time. In such a case, we set
k
=
tionally sound proof of communication complexity
O
(
log
n
o
(1)
polylog(
n
).
(Weaker lower bounds for the collision-forming task may yield meaningful results by
an appropriate setting of the parameter
k
; for example, the standard assumption that
claws cannot be formed in polynomial time allows us to set
k
=
n
ε
, for any constant
ε>
0, and obtain communication complexity of
n
ε
+
o
(1)
.) We stress that collisions can
always be formed in time 2
2
k
, and hence the entire approach fails if the prover is not
computationally bounded (and consequently we cannot get (perfectly sound) proof sys-
tems this way). Furthermore, one can show that only languages in Dtime(2
polylog
)have
proof systems with poly-logarithmic communication and randomness complexities.
·
(log
m
)
·
k
)
=
4.9.
∗
Constant-Round Zero-Knowledge Proofs
In this section we consider the problem of constructing
constant-round
zero-knowledge
proof systems
with negligible error probability
for all languages in
. To make the
rest of the discussion less cumbersome, we define a proof system to be
round-efficient
if it is
both constant-round and has negligible error probability
. We stress that none
of the zero-knowledge proof systems for
NP
presented and discussed thus far have
been round-efficient (i.e., they either had non-constant numbers of rounds or had non-
negligible error probability).
We present two approaches to the construction of round-efficient zero-knowledge
proofs for
NP
NP
:
1.
basing the construction of round-efficient zero-knowledge proof systems on constant-
round perfectly hiding commitment schemes (as defined in Section 4.8.2)
2.
constructing (round-efficient zero-knowledge)
computationally sound
proof systems (as
defined in Section 4.8) instead of (round-efficient zero-knowledge) proof systems
The advantage of the second approach is that round-efficient zero-knowledge computa-
tionally sound proof systems for
NP
can be constructed using any one-way function,
whereas it is not known if round-efficient zero-knowledge proof systems for
NP
can
be constructed under the same general assumption. In particular, we know how to con-
struct constant-round perfectly hiding commitment schemes only by using seemingly
stronger assumptions (e.g., the existence of claw-free permutations).
The two approaches have a fundamental idea in common. We start with an abstract
exposition of this common idea. Recall that the
basic
zero-knowledge proof for Graph
3-Colorability, presented in Construction 4.4.7, consists of a constant number of rounds.
However, this proof system has a non-negligible error probability (in fact, the error
