Cryptography Reference
In-Depth Information
The Algorithmics.
The second lemma (stated next) is analogous to the essence of the
proof of Theorem 2.3.2 (i.e., the simple amplification). However, there are two key
differences between the two proofs:
1.
In the proof of Theorem 2.3.2, we used a trivial combinatorial statement regarding the
number of
k
-sequences over
n
that each has an element in some set
S
(i.e., the
probability that such a uniformly chosen
k
-sequence has no element in the set
S
is
(1
{
0
,
1
}
)
k
). Here we use a generic hypothesis regarding the relationship between
the density of
S
and the fraction of
k
-sequences of a certain type that pass through it. That
is, here we consider only
k
-sequences that result from a
k
-step walk on a fixed regular
graph.
2.
More importantly, the proof of Theorem 2.3.2 refers to inverting the original function
f
on a sequence of (independently distributed) instances, whereas here we refer to inverting
successive applications of
f
(interleaved with
g
σ
-moves) on a single instance (and the
sequence in question is the one of intermediate results).
2
−
n
−
·|
S
|
Thus the proof that follows is more complex than the proof of Theorem 2.3.2. The
following lemma will be used, with
β
(
n
+
k
(
n
) log
2
d
)
=
1
−
(1
−
0
.
5
·
α
(
n
))
k
(
n
)
/
,as
provided by the earlier combinatorial argument.
n
,
E
n
)
}
,f
:
{
0
,
1
}
∗
Lemma 2.6.6 (Reducibility Lemma):
Let d,
{
G
n
=
(
{
0
,
1
}
}
∗
,k
:
→{
0
,
1
N → N
, and F
k
be as in Construction 2.6.3.
def
=
def
={
n
Let G
f
,
n
(
{
0
,
1
}
,
E
f
,
n
)
, where E
f
,
n
(
u
,v
):(
f
(
u
)
,v
)
∈
E
n
}
.
α,α
,β
Let
:
N →
[0
,
1]
, and k
:
N→N
be such that
β
(
n
+
k
(
n
) log
2
d
)
>α
(
n
)
α
(
n
)
2
−
n
.
and
≥
α
(
n
)
+
Suppose that G
f
,
n
satisfies the following
random-path property:
For every measure-
α
(
n
)
subset S of G
f
,
n
's nodes, at least a fraction
β
(
n
+
k
(
n
)
·
log
2
d
)
of the paths of length k
(
n
)
will pass through a node in S.
Suppose that f is
α
(
·
)
-one-way with respect to time T
(
·
)
. Then for every
polynomial-time-computable
ε
:
N → R
,
the
function
F
k
is
(1
−
ε
(
·
))
β
(
·
)
-
T
(
n
+
k
(
n
) log
2
d
)
def
T
:
N → N
,
one-way
with
respect
to
time
where
=
α
(
n
)
2
O
(
n
+
k
(
n
))
3
ε
(
n
)
2
·
T
(
n
)
.
Note that the lemma is of no interest in case
β
(
n
+
k
(
n
) log
2
d
)
≤
α
(
n
).
Proof Sketch:
The proof, as suggested by the name of the lemma, is by a reducibil-
ity argument. This argument is similar in flavor to the one used in the proof of
Theorem 2.3.2. Assume, to the contradiction, that for
m
def
=
n
+
k
(
n
) log
2
d
, the
permutation
F
k
can be inverted on
F
k
(
U
m
) in time
T
(
·
) with success probability
at least
1
−
(1
−
ε
(
m
))
·
β
(
m
)
=
1
−
β
(
m
)
+
ε
(
m
)
β
(
m
)
