Cryptography Reference
In-Depth Information
2.6.1. The Construction
The key to the amplification of a one-way permutation
f
is to apply
f
on many different
arguments. In the proof of Theorem 2.3.2,
f
is applied to unrelated arguments (which
are disjoint parts of the input). This makes the proof relatively easy, but also makes
the construction very inefficient. Instead, in the construction presented in the proof of
the current theorem, we apply the one-way permutation
f
to related arguments. The
first idea that comes to mind is to apply
f
iteratively many times, each time to the
value resulting from the previous application. This will not help if easy instances for
the inverting algorithm continue to be mapped, by
f
, to themselves. We cannot just
hope that this will not happen. So the second idea is to use randomization between
successive applications of
f
. It is important that we use only a small amount of random-
ization, since the “randomization” will be encoded into the argument of the constructed
function. The randomization between successive applications of
f
takes the form of a
random step on an expander graph. Hence a few words about these graphs and random
walks on them are in order.
A graph
G
|=
n
), every vertex in
V
has degree
d
(i.e.,
G
is
d
-regular), and
G
has the following
expansion property
(with
expansion factor c
=
(
V
,
E
) is called an (
n
,
d
,
c
)
-expander
if it has
n
vertices (i.e.,
|
V
n
>
0): For every subset
S
⊂
V
,if
|
S
|≤
2
,
then
|
N
(
S
)
|≥
(1
+
c
)
·|
S
|
, where
N
(
S
) denotes the set of neighbors of vertices in
S
(i.e.,
N
(
S
)
def
={
u
∈
V
:
∃
v
∈
S
s.t. (
u
,v
)
∈
E
}
).
16
By
explicitly constructed
(
d
,
c
)
-
expanders
we mean a family of graphs
{
G
n
}
n
∈N
such that each
G
n
is a (2
n
,
d
,
c
)-expander
and such that there exists a polynomial-time algorithm that on input a description of
a vertex in an expander outputs the list of its neighbors, where vertices in
G
n
are
represented by binary strings of length
n
. We stress that the constants
d
∈ N
and
c
>
0,
as well as the algorithm, are fixed for all graphs in the family. Such expander families
do exist. By a
random walk
on a graph we mean the sequence of vertices visited by
starting at a uniformly chosen vertex and randomly selecting at each step one of the
neighboring vertices of the current vertex, with uniform probability distribution. The
expanding property implies (via a non-trivial proof) that the vertices along random
walks on an expander have surprisingly strong “random properties.” In particular, for
every subset of constant density within the vertex set and every
l
, the probability
that no vertex along an
O
(
l
)-step-long random walk will hit the subset is at most
2
−
l
(i.e., as would have been the case if we had chosen
O
(
l
) vertices independently),
where the constant in the
O
-notation depends only on the expansion factor of the
graph.
We remind the reader that we are interested in successively applying the per-
mutation
f
, while interleaving randomization steps between successive applications.
Hence, before applying permutation
f
to the result of the previous application, we
take one random step on an expander. Namely, we associate the domain of the given
16
We use a somewhat non-standard definition. The standard definition of expansion with factor
c
>
0 is that for
n
2
), it holds that
|
N
(
S
)
|≥
c
·|
S
|
, where
N
(
S
) denotes the vertices in
V
\
S
that
every such
S
(i.e.,
S
⊂
V
and
|
S
|≤
have neighbors in
S
(i.e.,
N
(
S
)
def
={
u
∈
V
\
S
:
∃
v
∈
S
s.t. (
u
,v
)
∈
E
}
). Every (
n
,
d
,
c
)-expander under the stan-
dard definition can be easily transformed into an (
n
,
d
+
1
,
c
)-expander under our definition (e.g., by adding
self-loops).
