Cryptography Reference
In-Depth Information
Exercise 20:
Justificationforaconventionconcerningone-waycollections: Show that
giving the index of the function to the inverting algorithm is essential for a meaningful
definition of a collection of one-way functions.
Guideline:
Consider a collection
{
f
i
:
{
0, 1
}
|
i
|
→{
0, 1
}
|
i
|
}
, where f
i
(x)
=
x
⊕
i.
Exercise 21:
Rabin'scollectionandfactoring: Show that the Rabin collection is one-
way if and only if the factoring of integers that are the products of two primes of equal
binary expansions is intractable in a strong sense (i.e., every efficient algorithm suc-
ceeds with negligible probability).
Guideline:
See Appendix A.
Exercise 22:
Claw-free collections imply one-way functions: Let (I, D, F) be a claw-
free collection of functions (see Section 2.4.5). Prove that for every
σ ∈{
0, 1
}
, the
triplet (I, D, F
σ
), where F
σ
(i, x)
def
, i, x), is a collection of strong one-way functions.
Repeat the exercise, replacing the word “functions” with “permutations.”
F(
σ
=
Exercise 23:
More on the inadequacy of graph isomorphism as a basis for one-way
functions: In continuation of the discussion in Section 2.4.6, consider another sug-
gestion to base one-way functions on the conjectured difficulty of the Graph Isomor-
phism problem. This time we present a collection of functions defined by the algorith-
mic triplet (I
GI
, D
GI
, F
GI
). On input 1
n
, algorithm I
GI
selects uniformly a d(n)-regular
graph on n vertices (i.e., each of the n vertices in the graph has degree d(n)). On
input a graph on n vertices, algorithm D
GI
randomly selects a permutation in the
symmetric group of n elements (i.e., the set of permutations of n elements). On in-
put an (n-vertex) graph G and an (n-element) permutation
π
, algorithm F
GI
returns
)
def
G.
1.
Present a polynomial-time implementation of I
GI
.
2.
In light of the known algorithms for the Graph Isomorphism problem, which values of d(n)
should definitely be avoided?
3.
Using a known algorithm, prove that the foregoing collection does not have a one-way
property, no matter which function d(
f
G
(
π
=
π
) one uses.
Guideline:
A search of the relevant literature is indeed required for Items 2 and 3. Specif-
ically, for certain values of d(n), there exists a polynomial-time algorithm for deciding
isomorphism. Furthermore, for proving 3, it suffices to have an algorithm that runs fast
on randomly selected pairs of d-regular graphs.
·
Exercise 24:
Assuming the existence of one-way functions, prove that there exists
a one-way function f such that no single bit of the pre-image constitutes a hard-core
predicate.
Guideline:
Given a one-way function
f, construct a function g such that g(x, I)
def
=
( f(x
I
), x
I
, I), where I
⊆{
1, 2, . . .
|
x
|}
, and x
S
denotes the string resulting by taking only
the bits of x with positions in the set S(i.e., x
{
i
1
,...,i
s
}
def
=
x
i
1
···
x
i
s
, where x
=
x
1
···
x
|
x
|
).
How well can you predict each bit? To obtain more “dramatic” predictability, consider
g(x, I
1
,..., I
t
)
def
=
( f(x
∩
t
j
=
1
I
j
), x
∪
t
j
=
1
I
j
, I
1
,..., I
t
). What value of t (as a function of
|
x
|
)
should be used?
