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).