Cryptography Reference
In-Depth Information
Construction 4.8.3, consider replacement of the iterative hashing step with the following
step (where band the r
i
's are as in Construction 4.8.3):
(Ordinary hashing): The receiver sends the message (r
1
,...,r
n
−
1
) to the
sender, which replies with the message (c
1
,...,c
n
−
1
), where c
i
def
b(y, r
i
),
=
for i
1,...,n
−
1.
=
That is, the prescribed sender computes the c
i
's as in Construction 4.8.3, but a
cheating sender can determine all c
i
's based on all r
i
's (rather that determine
each c
i
based only on (r
1
,...,r
i
)).
Present an efficient strategy that allows the sender to violate the unambiguity condition.
Guideline:
Given any one-way permutation f
, first construct a one-way permutation f
satisfying f(0
|
x
|
, x
)
=
(0
|
x
|
, x
) and f(x
,0
|
x
|
)
=
(x
,0
|
x
|
) for every x
. (Hint: First
obtain a one-way permutation f
that satisfies f
(0
n
)
=
0
n
for all n's,
38
and then let
f(0
|
x
|
, x
)
def
=
(0
|
x
|
, x
), f(x
,0
|
x
|
)
def
f(x
, x
)
def
=
(x
,0
|
x
|
),
=
(f
(x
), f
(x
))
and
for
x
, x
∈{
0, 1
}
|
x
|
\{
0
}
|
x
|
.)
Assuming that the modified protocol is executed with f as constructed here, consider a
cheating sender that upon receiving the message (r
1
,...,r
n
−
1
) finds y
1
∈{
0, 1
}
n
/
2
{
0
}
n
/
2
,
y
2
∈{
0
}
n
/
2
{
0, 1
}
n
/
2
, and c
(c
1
,...,c
n
−
1
) such that the following conditions hold:
=
1.
c
i
b(y
j
, r
i
)fori
1,...,n
−
1 and j
1, 2
=
=
=
2.
b(y
j
, r
n
)
1, 2
(where r
n
is the unique vector independent of r
1
,...,r
n
−
1
).
Note that f is invariant under such y
j
's, and thus they can serve as valid decommit-
ments.
Finally, prove that such a solution y
1
, y
2
, calways exists and can be found by solving
a linear system. (Hint: Consider the linear system b(x
1
0
n
/
2
, r
i
)
=
b(0
n
/
2
x
2
, r
i
)fori
=
1,...,n
−
1 and b(x
1
0
n
/
2
, r
n
)
≡
b(0
n
/
2
x
2
, r
n
)
+
1(mod 2). Extra hint: Things may become
more clear when writing the conditions in matrix form.)
≡
j
(mod 2) for j
=
Exercise 34:
Non-interactive zero-knowledge, bounded versus unbounded: Show
that Construction 4.10.4 is not unboundedly zero-knowledge unless
.
Guideline:
Consider invoking this proof system twice: first on a graph consisting of a
simple cycle and then on a graph for which a Hamiltonian cycle is to be found.
NP
⊆
BPP
Exercise 35:
Regarding the definition of a two-sender commitment scheme
(Definition 4.11.4), show that for every pthere exist senders' strategies such that each
resulting receiver view can be 0-opened with probability pand 1-opened with probability
1
−
p.
Guideline:
Use the perfect-secrecy requirement and the fact that you can present com-
putationally unbounded senders' strategies.
38
See Exercise 13 in Chapter 2.
