Cryptography Reference
In-Depth Information
Exercise 17:
Prove the existence of a Karp reduction of any
NP
language L to SAT
that when considered as a function can be inverted in polynomial time. Same for the
reduction of SAT to 3SAT and the reduction of 3SAT to G3C. (In fact, the standard
Karp reductions have this property.)
Exercise 18:
Applications of Theorem 4.4.11: This exercise assumes a basic famil-
iarity with the notions of a public-key encryption scheme and a signature scheme.
Assuming the existence of non-uniformly one-way functions, present solutions to the
following cryptographic problems:
1.
Suppose that party Ssends, over a public channel, encrypted data to several parties,
R
1
,..., R
t
. Specifically, the data sent to R
i
are encrypted using the public encryption key
of party R
i
. We assume that all parties have access to the ciphertexts sent over the public
channel. Suppose that Swants to prove to some other party that it has sent the same
data to all R
i
's, but it wants to do so without revealing the data.
2.
Referring to the same communication setting, consider a party Rthat has received data
encrypted using its own public encryption key. Suppose that these data consist of two
parts, and party R wishes to reveal to someone the first part of the data but not the
second. Further suppose that the other party wants a proof that Rhas indeed revealed
the correct content of the first part of the data.
3.
Suppose that party Swishes to send party Ra signature to a publicly known document
such that only R receives the signature, but everyone else can verify that such a signature
was indeed sent by S. (We assume, again, that all parties share a public channel.)
Exercise 19:
Onknowledgetightness: Prove that the protocol resulting from executing
Construction 4.4.7 for k(n)
O(log n) times in parallel is zero-knowledge. Furthermore,
prove that it has knowledge tightness (3
=
2)
k(n)
(approximately).
/
Exercise 20:
Moreefficientzero-knowledgeproofsfor
NP
: Consider the basic proof
system for the Hamiltonian-cycle problem (HC) presented in Construction 4.7.14.
1.
Evaluate its acceptance probabilities (i.e., completeness and soundness bounds).
2.
Provide a sketch of the proof of the zero-knowledge property (i.e., describe the simulator).
Specifically, present a simulator that establishes knowledge tightness of approximately 2.
If you are really serious, provide a full proof of the zero-knowledge property.
Exercises for the Advanced Sections.
The rest of the exercises refer to the mate-
rial in the advanced sections (i.e., Sections 4.5-4.11).
Exercise 21:
An alternative formulation of black-box zero-knowledge: Here we say
that a probabilistic polynomial-time oracle machine M is a
black-box simulator
forthe
proverPandthelanguageLif for every (not necessarily uniform) polynomial-size circuit
family
M
B
|
x
|
(x)
}
x
∈
L
are indistinguish-
able by (non-uniform) polynomial-size circuits. Namely, for every polynomial-size circuit
family
{
B
n
}
n
∈
N
, the ensembles
{
P, B
|
x
|
(x)
}
x
∈
L
and
{
n
{
D
n
}
n
∈
N
, every polynomial p(
·
), all sufficiently large n, and x
∈{
0, 1
}
∩
L,
Pr [D
n
(
P, B
n
(x))
=
1]
−
Pr
D
n
M
B
n
(x)
=
1
<
1
p(n)
Prove that the current formulation is equivalent to the one presented in Definition 4.5.10.
