Cryptography Reference
In-Depth Information
Guideline:
Execute the weaker interactive proof sufficiently many times, using indepen-
dently chosen coin tosses for each execution, and rule by comparing the number of
accepting executions to an appropriate threshold. Observe that the bounds on complete-
ness and soundness need to be efficiently computable. Be careful when demonstrating
the soundness of the resulting verifier (i.e., do not assume that the cheating prover ex-
ecutes each copy independently of the other copies). We note that the statement remains
valid regardless of whether these repetitions are executed sequentially or “in parallel,” but
demonstrating that the soundness condition is satisfied is much easier in the sequential
case.
Exercise 2:
Theroleofrandomizationininteractiveproofs,Part1: Prove that if L has
an interactive proof system in which the verifier is deterministic, then L
.
Guideline:
Note that if the verifier is deterministic, then the entire interaction between the
prover and the verifier can be determined by the prover.
∈
NP
Exercise 3:
The role of randomization in interactive proofs, Part 2: Prove that if L
has an interactive proof system, then it has one in which the prover is deterministic.
Furthermore, prove that for every (probabilistic) interactive machine V, there exists a de-
terministic interactive machine Psuch that for every x, the probability Pr [
P, V
(x)
1]
=
equals the supremum of Pr [
1] taken over all interactive machines B.
Guideline:
For each possible prefix of interaction, the prover can determine a message
that maximizes the accepting probability of the verifier V.
B, V
(x)
=
Exercise 4:
The role of randomization in interactive proofs, Part 3: Consider the fol-
lowing (bad) modification to the definition of a pair of linked interactive machines (and
interactive proofs). By this modification, also the random tapes of the prover and verifier
coincide (i.e., intuitively, both use the same sequence of coin tosses that is known to
both of them). We call such proof systems shared-randomnessinteractiveproofs. Show
that only languages in
MA
have a shared-randomness interactive proof system, where
a language L is in
MA
if there exists a language R
L
in
BPP
and a polynomial psuch
p(
|
x
|
)
such that (x, y)
that x
R
L
.
Guideline:
First convert a shared-randomness interactive proof system into an interactive
proof system (of the original kind) in which the verifier reveals all its coin tosses up-front.
Next, use reasoning as in Exercise 2.
Show that
∈
L if and only if there exists y
∈{
0, 1
}
∈
actually equals the class of languages having shared-randomness
interactive proof systems.
MA
Exercise 5:
The role of error in interactive proofs: Prove that if L has an interactive
proof system in which the verifier never (not even with negligible probability) accepts a
string not in the language L, then L
.
Guideline:
Define a relation R
L
such that (x, y)
∈
R
L
if yis a full transcript of an interaction
leading the verifier to accept the input x. We stress that ycontains the verifier's coin tosses
and all the messages received from the prover.
∈
NP
Exercise 6:
Simulatorerrorinperfectzero-knowledgesimulators,Part1: Consider a
modification of Definition 4.3.1 in which condition 1 is replaced by requiring that for some
function
), Pr[M
∗
(x)
β
(
·
=
⊥
]
<β
(
|
x
|
). Assume that
β
(
·
) is polynomial time-computable.
Show that the following hold:
