Cryptography Reference
In-Depth Information
commitment scheme can be constructed based on any one-way 1-1 func-
tion
f
(with a corresponding hard-core
b
). To commit to a bit
σ
,the
sender uniformly selects
s
n
, and sends the pair (
f
(
s
)
,b
(
s
)
σ
).
Note that this is both binding and hiding. An alternative construction,
which can be based on any one-way function, uses a pseudorandom gen-
erator
G
that stretches its seed by a factor of three (cf. Theorem 3.4).
A commitment is established, via two-way communication, as follows
(cf. (101)): The receiver selects uniformly
r
∈{
0
,
1
}
⊕
3
n
∈{
0
,
1
}
and sends it to
n
the sender, which selects uniformly
s
G
(
s
)if
it wishes to commit to the value one and
G
(
s
)ifitwishestocommit
to zero. To see that this is binding, observe that there are at most 2
2
n
“bad” values
r
that satisfy
G
(
s
0
)=
r
∈{
0
,
1
}
and sends
r
⊕
G
(
s
1
)forsomepair(
s
0
,s
1
), and
with overwhelmingly high probability the receiver will not pick one of
these bad values. The hiding property follows by the pseudorandomness
of
G
.
⊕
Zero-knowledge proofs for other NP-sets.
By using the stan-
dard Karp-reductions to 3-Colorability, the protocol of Figure 4.2 can
be used for constructing zero-knowledge proofs for any set in
.We
comment that this is probably the first time that an NP-completeness
result was used in a “positive” way (i.e., in order to construct something
rather than in order to derive a hardness result).
4
NP
Eciency considerations.
The protocol in Figure 4.2 calls for
invoking some constant-round protocol for a non-constant number of
times (and its analysis relies on the preservation of zero-knowledge
under sequential composition). At first glance, it seems that one can
derive a constant-round zero-knowledge proof system (of negligible
soundness error) by performing these invocations in parallel (rather
than sequentially). Unfortunately, as indicated in (71), it is not clear
that the resulting interactive proof is zero-knowledge. Still, under stan-
dard intractability assumptions (e.g., the intractability of factoring),
constant-round zero-knowledge proofs (of negligible soundness error)
4
Subsequent positive uses of completeness results have appeared in the context of inter-
active proofs (96; 118), probabilistically checkable proofs (6; 55; 5; 4), “hardness versus
randomness trade-offs” (7), and statistical zero-knowledge (115).
