Cryptography Reference
In-Depth Information
Exercise 16:
On the improbability of strengthening Theorem 2.3.2 (Part 2) (due to
Steven Rudich): Suppose that the definition of a strong one-way function is further
strengthened such that it is required that every probabilistic polynomial-tim
e
algorithm
fails to invert the function with some specifiednegligible probability (e.g., 2
−
√
n
). Demon-
strate the difficulty of extending the proof of Theorem 2.3.2 to this case.
Guideline:
Suppose that we construct the strong one-way function g as in the original
proof. Further suppose that there exists an inverting algorithm Athat inverts the function
gon g(U
n
) with probability
(n). Show that any inverting algorithm for the weakly one-way
function f that uses algorithm Aas a black box must invoke it at least
ε
1
poly(n)
times.
·ε
(n)
Exercise 17:
Advancedtopic:distributionallyone-wayfunctions[131]: We say that a
polynomial-time-computable function f :
}
∗
is
distributionally one-way
if there exists a positive polynomial psuch that for every probabilistic polynomial-time
algorithm Aand all sufficiently large n's, the statistical difference between (U
n
, f(U
n
))
and ( A(1
n
, f(U
n
)), f(U
n
)) is greater than 1
}
∗
→{
{
0, 1
0, 1
p(n). (That is, the inverting task is to provide
a uniformly distributed pre-image rather than an arbitrary one, and failure is measured
in terms of the deviation of A's output from this distribution.)
1.
Prove that if f is weakly one-way (as in Definition 2.2.2), then it is distributionally one-way.
2.
Prove that if there exist distributionally one-way functions, then there exist one-way func-
tions.
Guideline (Part 2):
Use hashing ideas as in Section 3.5. Specifically, given a distribu-
tionally one-way function f, consider the function F(x, i, h)
/
( f(x), h
i
(x), i, h), where
=
x
n
is a hashing function, and h
i
(x) de-
notes the i-bit-long prefix of h(x). Prove that F is weakly one-way.
Guideline (Part 2, extra help):
Suppose, to the contrary, that F can be inverted on at
least a 1
∈{
0, 1
}
n
, i
∈{
1,...,n
}
, h:
{
0, 1
}
n
→{
0, 1
}
n. Then for any
: N
→
N, the function F can be inverted on at least a 1
−
n
ε
(n) fraction of the inputs
(x,
log
2
|
f
−
1
( f(x))
|
+
(n), h). Given y
=
f(x), we generate a random pre-image of y
under f as follows. First, for
(n)
=
O(log n), we find an i such that i
=
log
2
|
f
−
1
( f(x))
|
+
(n)
±
O(1). (This is done by trying to invert F on (y, i, r, h), where hand r
∈{
0, 1
}
− ε
(n)
>
1
−
(2n)
−
1
fraction of the inputs (x, i, h), where
|
x
|
=
i
are
uniformly chosen, and choosing i if a pre-image is found with probability approximately
2
−
(n)
.) Next, using this i, we output a pre-image of (y, i, r, h) under F, where (again) h
and r
∈{
0, 1
}
i
are uniformly chosen. (In case inversion fails, we try again.) Show that
the output distribution of this algorithm deviates from the desired distribution by at most
O(2
(n)
+
2
2
(n)
+
2log
2
n)
· ε
(n)), and so the claim follows.
Exercise 18:
One-wayfunctionsandcollectionsofone-wayfunctions:
1.
Given any collection of one-way functions (I, D, F), represent it as a single one-way
function.
2.
Given any one-way function f, represent it as a collection of one-way functions. (Remark:
This direction is quite trivial.)
Exercise 19:
Aconventionforcollectionsofone-wayfunctions: Show that without loss
of generality, algorithms I and D of a collection (of one-way functions) can be modified
so that each of them uses a number of coins that exactly equals the input length.
Guideline:
Apply padding.
