Zero-Knowledge Proof Systems - Foundations of Cryptography: Basic Tools - page 326

Exercise 13: Prove that the existence of bit-commitment schemes implies the exis-
tence of one-way functions.
Guideline: Following the n otation of Definition 4.4.1, consider the mapping of (v,s,r)
to the receiver's view (r, m). Observe that by the unambiguity requirement, range ele-
ments are very unlikely to have inverses with both possible values of v. The mapping
is polynomial-time computable, and any algorithm that inverts it with success probability
that is not negligible can be used to contradict the secrecy requirement.

Exercise 14: Considering the commitment scheme of Construction 4.4.4, suggest a
cheating sender that induces a receiver's view (of the commit phase) that is unlikely
to have any possible opening and still is computationally indistinguishable from the
receiver's view in interactions with the prescribed sender. That is, present a probabilistic
polynomial-time interactive machine S ∗ such that the following two conditions hold:
1. With overwhelmingly high probability, S ∗ (0), R (1 n ) is neither a possible 0-commitment
nor a possible 1-commitment.
2. The ensembles S ∗ (0), R (1 n ) and S(0), R (1 n ) are computationally indistinguishable.
Guideline: The sender simply replies with a uniformly chosen string.

Exercise 15: Using Construction 4.4.4 as a commitment scheme in Construction
4.4.7: Prove that when the commitment scheme of Construction 4.4.4 is used in the
G3C protocol, then the resulting scheme remains zero-knowledge. Consider the modi-
fications required to prove Claim 4.4.8.2.

Exercise 16: Strong reductions: Let L 1 and L 2 be two languages in NP , and let
R 1 and R 2 be binary relations characterizing L 1 and L 2 , respectively. We say that the
relation R 1 is Levin-reducible 37 to the relation R 2 if there exist two polynomial-time-
computable functions f and gsuch that the following two conditions hold:

Standardrequirement: x L 2 .

Additionalrequirement: For every (x, w ) ∈ R 1 , it holds that ( f(x), g(x, w )) ∈ R 2 .

∈ L 1 if and only if f(x) ∈

Prove the following statements:
1. Let L ∈ NP , and let R L be the generic relation characterizing L (i.e., fix a non-
deterministic machine M L , and let (x, w) ∈ R L if w is an accepting computation of M L on
input x). Let R SAT be the standard relation characterizing SAT (i.e., (x, w) ∈ R SAT if w
is a truth assignment satisfying the CNF formula x). Prove that R L is Levin-reducible to
R SAT .
2. Let R SAT be as before, and let R 3SAT be defined analogously for 3SAT. Prove that R SAT
is Levin-reducible to R 3SAT .
3. Let R 3SAT be as before, and let R G3C be the standard relation characterizing G3C (i.e.,
(x, w) ∈ R G3C if w is a 3-coloring of the graph x). Prove that R 3SAT is Levin-reducible to
R G3C .
4. Levin reductions are transitive.

37 We name this reduction after Levin because it was he who, upon discovering (independently of Cook and
Karp) the existence of NP -complete problems, used a stronger definition of a reduction that implies the one here.
We assume that the reader is familiar with standard reductions among languages such as Bounded Halting, SAT,
and 3SAT (as in [86]).