Cryptography Reference
In-Depth Information
Exercise 22:
Prove that the protocol presented in Construction 4.4.7 is indeed a
black-box zero-knowledge proof system for G3C.
Guideline:
Use the formulation presented in Exercise 21.
Exercise 23:
Prove that black-box zero-knowledge is preserved under sequential
composition. (Note that this does not follow merely from the fact that auxiliary-input
zero-knowledge is preserved under sequential composition.)
Guideline:
Adapt the proof of Lemma 4.3.11.
Exercise 24:
Refutinganotherparallel-compositionconjecture: Prove that there exists
a zero-knowledge prover P such that the prover resulting from running two copies of
P in parallel yields knowledge
(
e.g., a cheating verifier can extract from this prover a
solution to a problem that is not solvable in polynomial time
)
.
Guideline:
Let P
1
and P
2
be as in Proposition 4.5.9, and consider the prover P that
randomly selects which of the two programs to execute. Alternatively, the choice can be
determined by the verifier.
Exercise 25:
Assuming that one-way permutations exist, present a witness-
indistinguishable proof system (with a probabilistic polynomial-time prover) that is
NOT
strongly witness-indistinguishable.
Guideline:
Consider a one-way permutation f, a hard-core predicate b of f, and the
witness relation
{
( f(w),w):w
∈{
0, 1
}
∗
}
. Consider a prover that on input f (w) (and
auxiliary input w) sends w to the verifier, and consider the ensembles
{
X
n
}
n
∈
N
and
{
X
n
}
n
∈
N
, where X
n
is uniform on
{
f(w):w
∈{
0, 1
}
n
& b(w)
=
i
}
.
Exercise 26:
Somebasiczero-knowledgeproofsofknowledge:
1.
Show that Construction 4.3.8 is a proof of knowledge of an isomorphism with knowledge
error
2
.
2.
Show that Construction 4.4.7 (when applied on common input G
(V, E)) is a proof of
=
knowledge of a 3-coloring with knowledge error 1
−
1
.
|
E
|
See also Part 1 of Exercise 28.
Guideline:
Observe that in these cases, if the verifier accepts with probability greater
than the knowledge error, then it accepts with probability 1. Also observe that the number
of possible verifier messages in these proof systems is polynomial in the common input.
Thus, the extractor can emulate executions of these systems with all possible verifier
messages.
Exercise 27:
Parallel repetitions of some basic proofs of knowledge: Let k: N
→
N
be polynomially bounded. Consider the proof systems resulting by executing each of
the basic systems mentioned in Exercise 26 for
ktimes in parallel.
1.
Show that the kparallel execution of Construction 4.3.8 constitutes a proof of knowledge
of an isomorphism with knowledge error 2
−
k(
·
)
. (Analogously for Construction 4.7.12.)
2.
Show that the kparallel execution of Construction 4.4.7 provides a proof of knowledge of
a 3-coloring with knowledge error (1
−
(1
/|
E
|
))
−
k(
|
G
|
)
.
Note that we make no claim regarding zero-knowledge.
See also Part 2 of Exercise 28.