Cryptography Reference
In-Depth Information
n
Guideline:
Suppose that
|{
f(x):x
∈{
0, 1
}
}|≤
p(n). To invert f on y
=
f(U
n
), with
success probability 1
/
p(n), it suffices to select uniformly r
∈{
0, 1
}
n
and hope that f(r)
=
y. To invert f on y
=
f(U
n
) with success probability 1
− ε
(n), we select uniformly many
such r
i
's, with the hope that y is “heavy” and that all “heavy” f-images are hit by some
f(r
i
). (Extra hint: y
is heavy if Pr[ f(U
n
)
=
y
]
≥
ε
(n)
2 p(n)
.)
Exercise 11:
Prove that length-preserving one-wayfunctionscannothavepolynomi-
ally bounded cycles. Namely, for every function f, define cyc
f
(x) to be the smallest
positiveinteger i such that f
i
(x)
x, where f
j
+
1
(x)
f( f
j
(x)) and f
0
(x)
x. Prove
=
=
=
that if f is (even weakly) one-way, then for every polynomial p(
) and all sufficiently
large n's, the expected value of cyc
f
(U
n
) is greater than p(n), where U
n
is a random
variable uniformly distributed over
·
n
.
{
0, 1
}
Guideline:
Note that if Ecyc
f
(U
n
)]
>
p(n), then for every polynomial q, it holds that
Pr[cyc
f
(U
n
)
>
q(n)
·
p(n)]
<
1
/
q(n). Why is the length-preserving condition needed?
Exercise 12:
Assuming the existence of one-way functions (resp., permutations), con-
struct one-way functions (resp., permutations) in which there are no sub-exponential
cycles. That is, let cyc
f
(x) be defined as in Exercise 11; then the constructed f should
satisfy cyc
f
(x)
≥
2
|
x
|/
2
for all x's.
Guideline:
Given a one-way function (resp., permutation)
f(x
, x
)
def
f
, construct
=
( f
(x
), h(x
)) for some suitable hand
|
x
|
=
|
x
|
. What is a suitable h?
Exercise 13:
One-way function with a “fixed point”: Prove that if one-way functions
exist, then there exists a one-way function f such that f(0
n
)
0
n
for every n. Do the
=
same for one-way permutations.
Guideline:
The first part is trivial. For the second part, using any one-way permutation f
,
let f(x, y)
=
( f
(x), y)ify
∈{
0, 1
}
|
x
|
\{
0
}
|
x
|
, and f(x,0
|
x
|
)
=
(x,0
|
x
|
) otherwise.
Exercise 14:
Let
{
(a
n
, b
n
):n
∈
N
}
be recognizable in (deterministic) polynomial time,
where a
n
, b
n
∈{
n
. Prove that if one-way functions exist, then there exists a one-way
function f such that f(a
n
)
0, 1
}
b
n
for every n. Do the same for one-way permutations.
Guideline:
The first part is trivial. For the second part, consider any one-way permu-
tation f
, and suppose f
(a
n
)
=
b
n
. Construct a one-way permutation f as required by
switching two values of f
.
=
Exercise 15:
OntheimprobabilityofstrengtheningTheorem2.3.2(Part 1): Suppose
that the definition of a weak one-way function is further weakened so that it is required
that every probabilistic polynomial-time algorithm fails to invert the function with notice-
able probability. That is, the order of quantifiers in Definition 2.2.2 is reversed (we now
have “for every algorithm there exists a polynomial” rather than “there exists a polyno-
mial such that for every algorithm”). Demonstrate the difficulty of extending the proof of
Theorem 2.3.2 to this case.
Guideline:
Suppose that there exists a family of algorithms, one per each polynomial
p(
·
), such that an algorithm with time bound p(n) fails to invert the function with probability
1
/
p(n). Demonstrate the plausibility of such a family.
