Cryptography Reference
In-Depth Information
y
according to the suffix of
p
, and asking
A
for the pre-image of the resulting
pair under
F
k
.
Algorithm for inverting
f
:
On input
y
,
repeat
2
nk
εβ
times:
1.
Select randomly
i
∈{
1
,
2
,...,
k
}
and
σ
1
,σ
2
,...,σ
k
∈{
1
,
2
,...,
d
}
.
2.
Compute
y
=
,σ
i
+
1
...σ
k
).
3.
Invoke
A
to obtain
x
←
F
(
g
σ
i
(
y
)
y
).
A
(
σ
1
σ
2
,...,σ
k
,
=
F
(
x
,σ
1
...σ
i
−
1
).
4.
Compute
x
5.
If
f
(
x
)
=
y
, then halt and output
x
.
Analysis of the inverting algorithm (for a good
x
):
Since
x
is good, a random path
going through it (selected as before) corresponds to an “invertible path” with probability
at least
ε
/
2
k
. If such a good path is selected, then we obtain the inverse of
f
(
x
) with overwhelming probability. The algorithm for inverting
f
repeats the process
sufficiently many times to guarantee overwhelming probability of selecting an “invertible
path.”
By Claim 2.6.6.2, the good
x
's constitute at least a 1
k
=
εβ/
fraction of all
n
-bit strings.
Thus, the success probability of our inverting algorithm on input
f
(
U
n
) is at least
−
α
2
−
n
)
2
−
n
−
α
(
n
)
(1
−
α
(
n
))
·
(1
−
>
1
−
α
(
n
)
−
≥
1
The running time of our inverting algorithm is
T
(
m
)
2
nk
(
n
)
2
m
·
4
nmk
(
n
)
(
m
)
2
·
T
(
m
)
≤
T
(
n
)
(
m
)
·
(
m
)
=
ε
β
ε
β
ε
(
m
)
2
β
(
m
)
(
m
)
where the last inequality uses
β
(
m
)
≥
α
(
n
). Hence, the existence of an algorithm
inverting
F
k
in time
T
(
·
) with probability at least 1
−
(1
−
ε
(
·
))
β
(
·
) implies the
existence of an algorithm inverting
f
in time
T
(
·
) with probability at least 1
−
α
(
·
). The latter constitutes a contradiction to the hypothesis of the lemma, and
hence the lemma follows.
Finishing the Proof of Proposition 2.6.4.
When Lemma 2.6.5 is applied to the graph
G
f
,
n
, it follows that, for every set
S
⊆
V
of measure
α
(
n
), a random walk of length
t
on
G
f
,
n
−
−
.
·
α
(
n
))
t
. Recall that edges in
G
f
,
n
hits
S
with probability at least 1
(1
0
5
represent
-edge paths in
G
f
,
n
, and so the vertices visited in a
k
-step walk on
G
f
,
n
are a
subset of those visited in a corresponding (
k
/
)-step walk on
G
f
,
n
. It follows that a ran-
dom walk of length
k
(
n
)on
G
f
,
n
hits
S
with probability at least 1
−
(1
−
0
.
5
·
α
(
n
))
k
(
n
)
/
.
Applying Lemma 2.6.6, with
α
(
n
)
=
α
(
n
)
+
2
−
n
and
β
(
n
+
k
(
n
)
·
log
2
d
)
=
1
−
(1
−
0
.
5
·
α
(
n
))
k
(
n
)
/
, we conclude that if
f
is
α
(
n
)-one-way with respect to time
T
(
·
), then
F
k
is ((1
−
ε
(
·
))
β
(
·
))-one-way with respect to time
T
(
·
), where
β
and
T
are as in
Proposition 2.6.4. This completes the proof.
An Alternative Analysis.
Our analysis of Construction 2.6.3 is conducted using the
eigenvalue ratio of expander graphs, rather than their natural combinatorial definition (in
