Cryptography Reference
In-Depth Information
Modify the inverting algorithm so that it inverts
F
k
with overwhelming proba-
bility on a 1
−
β
(
m
)
+
ε
(
m
) fraction of the inputs of length
m
, where
ε
(
m
)
=
ε
2. (This can be done by first observing that the inverting algorithm must
invert at least a 1
(
m
)
β
(
m
)
/
+
ε
(
m
) fraction of the inputs with probability at least
ε
(
m
) and then increasing its success on such inputs by
m
−
β
(
m
)
/ε
(
m
) independent tries.)
Denote the resulting algorithm, which has running time (2
m
(
m
)),
by
A
. Note that inputs to
A
correspond to
k
(
n
)-long paths on the graph
G
n
.
Consider the set, denoted
I
n
, of paths (
x
·
T
(
m
))
/
(
ε
(
m
)
β
,
p
) such that
A
inverts
F
k
(
x
,
p
) with
2
−
n
).
overwhelming probability (e.g., probability at least 1
−
def
=
k
(
n
),
m
def
=
n
+
k
log
2
d
,
ε
def
=
ε
(
m
),
In the sequel, we use the shorthand
k
ε
def
def
=
β
(
m
),
α
def
=
α
(
n
), and
I
def
=
I
n
. Recall that
|
I
|≥
(1
−
β
+
ε
)
·
2
m
.
Let
P
v
be the set of all
k
-long paths that pass through
v
, and let
I
v
be the subset
of
I
containing paths that pass through
v
(i.e.,
I
v
=
I
∩
P
v
). Define
v
as
good
if
|
I
v
|
/
|
P
v
|≥
ε
/
k
(and
bad
otherwise). Intuitively, a vertex
v
is called good
if at least a
ε
/
k
fraction of the paths going through it can be inverted by
A
.
Let
I
=
I
\∪
v
bad
I
v
; namely,
I
contains all “invertible” paths that pass solely
through good nodes. Clearly, we have the following:
=
ε
(
m
),
β
Claim 2.6.6.1:
The density of
I
in the set of all paths is greater than 1
−
β
.
Proof:
Denote by
µ
(
S
)
=|
S
|
/
|
P
|
the density of the set
S
in the set of all paths.
Then
µ
(
I
)
=
µ
(
I
)
−
µ
(
∪
v
bad
I
v
)
≥
(1
−
β
+
ε
)
−
v
bad
µ
(
I
v
)
ε
k
·
µ
(
P
v
)
>
1
−
β
+
ε
−
v
≥
1
−
β
where the last inequality is due to the fact that each path in
P
contributes to at
most
k
of the
P
v
's.
Using the random-path property, we have the following:
−
α
Claim 2.6.6.2:
The density of good nodes is greater than 1
.
Proof:
Otherwise, let
S
be the set of bad nodes, and suppose that
|
S
|≥
α
·
2
n
.
By the random-path property, since
S
has measure (at least)
α
, the fraction of
paths that pass through vertices of
S
is at least
β
. That is, the fraction of paths
that pass through a bad vertex is at least
. But
I
does not contain paths that pass
through bad vertices, and so
I
can contain at most a 1
β
−
β
fraction of all paths,
in contradiction to Claim 2.6.6.1.
The following algorithm for inverting
f
is quite natural. The algorithm uses as
subroutine an algorithm, denoted
A
, for inverting
F
k
. Inverting
f
on
y
is done by
placing
y
on a random point along a randomly selected path
p
, taking a walk from
