Cryptography Reference
In-Depth Information
1.
The family of graphs
{
G
n
}
n
∈N
is an explicitly constructed family of
(
d
,
c
)
-expanders.
α
(
2.
The permutation f is polynomial-time-computable as well as
·
)
-one-way with
α
(
n
)
2
−
n
.
respect to time T
:
N → N
, where
=
α
(
n
)
+
3.
The function
α
:
N → R
is polynomial-time-computable.
4
+
c
2
c
2
4.
≥
·
d.
Then the permutation F
k
is polynomial-time-computable, and for every poly-
nomial-time-computable
ε
:
N → R
, the permutation F
k
is
((1
−
ε
(
·
))
β
(
·
))
-one-
way with respect to time T
:
N → N
, where
1
k
(
n
)
/
−
α
(
n
)
2
log
2
d
)
def
β
(
n
+
k
(
n
)
·
=
1
−
(
ε
(
n
)
·
α
(
n
))
2
O
(
n
T
(
n
+
k
(
n
)
·
log
2
d
)
def
=
k
(
n
))
3
·
T
(
n
)
+
For
k
(
n
)
=
3
·
n
and
α
(
n
)
=
1
/
poly(
n
), we get
β
(
O
(
n
))
=
1
−
(1
−
0
.
5
·
α
(
n
))
3
n
and
T
(
O
(
n
))
=
poly(
ε
(
n
)
/
n
)
·
T
(
n
). In particular, for
α
(
n
)
=
o
(1
/
n
)wehave
β
(
O
(
n
))
≈
1
.
5
n
·
α
(
n
), for
α
(
n
)
≤
1
/
2
n
we have
β
(
O
(
n
))
>
1
.
02
n
·
α
(
n
), and for constant
α
we
have
β
(
O
(
n
))
>
1
−
2
−
(
n
)
.
Proof of Theorem 2.6.2:
Theorem 2.6.2 follows by applying Proposition 2.6.2
δ
+
δ
·
1 times, where
is the degree of the polynomial
p
(
) (specified in the hy-
1
p
(
pothesis that
f
is
)
-one-way). In all applications of the proposition, we use
·
k
(
n
)
def
=
3
n
. In the first
δ
applications we use
ε
(
n
)
=
0
.
01. For
i
≤
δ
, the func-
1
tion resulting from the
i
th application of the proposition is
2
n
δ
−
i
-one-way. In
1
particular, after
δ
applications, the resulting function is
2
-one-way. (It seems that
1
the notion of
2
-one-wayness is worthy of special attention and deserves a name
such as
mostly one-way
.) In the last (i.e.,
δ
+
1) application we use
ε
(
n
)
=
(
n
).
The function resulting from the last (i.e.,
δ
+
1) application of the proposition
satisfies the statement of Theorem 2.6.2.
Overview of the Proof of Proposition 2.6.4.
The proposition itself is proved by
combining two different types of arguments, the main parts of which are stated in
Lemmata 2.6.5 and 2.6.6, below. Lemma 2.6.5 is a purely combinatorial lemma re-
garding the behavior of random walks on expander graphs. Lemma 2.6.6 presup-
poses such behavior (of random walks on the graphs
{
G
f
,
n
}
, defined below) and
uses it in order to establish Proposition 2.6.4. The proof of Lemma 2.6.6 is by a re-
ducibility argument, which generalizes the proof of Theorem 2.3.2. We start with the
combinatorics.
The Combinatorics.
First note that we are not interested in random walks on
G
n
,
but rather in random walks on the graph
G
f
,
n
def
=
(
{
0
,
1
}
n
,
E
f
,
n
) obtained from
G
n
=
def
={
(
. The first observation is that
G
f
,
n
preserves the expansion property of
G
n
, since
f
is a permutation over
{
0
,
1
}
n
,
E
n
) by letting
E
f
,
n
(
u
,v
):(
f
(
u
)
,v
)
∈
E
n
}
{
0
,
1
}
n
.
