Cryptography Reference
In-Depth Information
Guideline:
For Part 1, note that any two different transcripts in which the verifier accepts
will yield an isomorphism. In Part 2 this simple observation fails. Still, observe that
|
E
|
accepting transcripts that differ in any fixed copy of the basic system do yield a 3-coloring.
Exercise 28:
More efficient zero-knowledge proofs of knowledge for
NP
:Asin
Exercise 20, consider the basic proof system for the Hamiltonian-cycle problem (HC)
presented in Construction 4.7.14.
1.
Prove that the basic proof system is a proof of knowledge of a Hamiltonian cycle with
knowledge error
2
.
2.
Prove that the proof system that results from iterating the basic system ktimes is a proof
of knowledge of a Hamiltonian cycle with knowledge error 2
−
k
. Consider bothsequential
and parallel repetitions.
1
Exercise 29:
MoreontheequivalenceofDefinitions4.7.2and4.7.3: Suppose that R
is polynomially bounded and that the extractor in Definition 4.7.3 outputs either a valid
solution or a special failure symbol. Referring to this relation R, show that V satisfies the
validity-with-error
κ
condition of Definition 4.7.2 if and only if V satisfies the alternative
validity-with-error
κ
condition of (the modified) Definition 4.7.3.
Guideline:
Follow the outline of the proof of Proposition 4.7.4, noting that all references
to the hypothesis that Ris an
NP
-relation can be replaced by the hypothesis that the
extractor in Definition 4.7.3 outputs either a valid solution or a special failure symbol.
In particular, in the second direction, omit the exhaustive search that takes place with
probability 2
−
poly(
|
x
|
)
, and use the fact that p(x, y, r)
>κ
(
|
x
|
) implies p(x, y, r)
≥ κ
(
|
x
|
)
+
2
−
poly(
|
x
|
)
.
Exercise 30:
Zero-knowledge strong proofs of knowledge for
NP
: Consider again
the basic proof system for the Hamiltonian-cycle problem (HC) presented in Construc-
tion 4.7.14. Prove that the proof system that results from sequentially iterating the basic
system sufficiently many times is a strong proof of knowledge of a Hamiltonian cycle.
(Recall that it is indeed zero-knowledge.)
Exercise 31:
Errorreductionincomputationallysoundproofs: Given a computation-
ally sound proof (with error probability
1
3
) for a language L, construct a computationally
sound proof with negligible error probability (for L).
Guideline:
Use sequential repetitions. In fact, the error probability can be made expo-
nentially vanishing. Parallel repetitions may fail to reduce computational soundness in
some cases (see [19]).
Exercise 32:
Commitment schemes, an impossibility result: Prove that there ex-
ists no two-party protocol that simultaneously satisfies the perfect secrecy require-
ment of Definition 4.8.2 and the (information-theoretic) unambiguity requirement of
Definition 4.4.1.
Exercise 33:
Failure of ordinary hashing in Construction 4.8.3: Show that in Con-
struction 4.8.3, replacing the iterative hashing by an ordinary one results in a scheme
that is
NOT
binding (not even in a computational sense). That is, using the notation of
