Cryptography Reference
In-Depth Information
there are no non-uniformly one-way functions. However, this situation (i.e., that one-
way functions exist
only
in the uniform sense) seems unlikely, and it is widely believed
that non-uniformly one-way functions exist. In fact, all candidates mentioned in the
preceding subsection are believed to be non-uniformly one-way functions.
2.3. Weak One-Way Functions Imply Strong Ones
We first remark that not every weak one-way function is necessarily a strong one.
Consider, for example, a one-way function
f
(which, without loss of generality, is
length-preserving). Modify
f
into a function
g
so that
g
(
p
,
x
)
=
(
p
,
f
(
x
)) if
p
starts
with log
2
|
.
4
We claim that
g
is a weak one-way function but not a strong one. Clearly,
g
cannot be
a strong one-way function (because for all but a
x
|
zeros, and
g
(
p
,
x
)
=
(
p
,
x
) otherwise, where (in both cases)
|
p
|=|
x
|
1
n
fraction of the strings of length 2
n
the function
g
coincides with the identity function). To prove that
g
is weakly one-way,
we use a “reducibility argument.”
Proposition 2.3.1:
Let f be a one-way function
(
even in the weak sense
)
. Then
g, constructed earlier, is a weakly one-way function.
Proof:
Intuitively, inverting
g
on inputs on which it does
not
coincide with the
identity transformation is related to inverting
f
. Thus, if
g
is inverted, on inputs
of length 2
n
, with probability that is noticeably greater than 1
1
n
, then
g
must be
inverted with noticeable probability on inputs to which
g
applies
f
. Therefore, if
g
is not weakly one-way, then neither is
f
. The full, straightforward but tedious
proof follows.
−
Given a probabilistic polynomial-time algorithm
B
for inverting
g
, we construct a
probabilistic polynomial-time algorithm
A
that inverts
f
with “related” success prob-
ability. Following is the description of algorithm
A
. On input
y
, algorithm
A
sets
n
def
=|
def
=
def
=
log
2
n
, selects
p
uniformly in
n
−
l
, computes
z
B
(0
l
p
,
y
),
and halts with output of the
n
-bit suffix of
z
. Let
S
2
n
denote the sets of all 2
n
-bit-long
strings that start with log
2
n
zeros (i.e.,
S
2
n
y
|
and
l
{
0
,
1
}
def
={
0
log
2
n
2
n
−
log
2
n
α
:
α
∈{
0
,
1
}
}
). Then,
by construction of
A
and
g
,wehave
[
A
(
f
(
U
n
))
f
−
1
(
f
(
U
n
))]
Pr
∈
f
−
1
(
f
(
U
n
)))]
=
Pr
[
B
(
g
(
U
2
n
))
∈
g
−
1
(
g
(
U
2
n
))
|
U
2
n
∈
S
2
n
]
≥
Pr
[
B
(0
l
U
n
−
l
,
(0
l
U
n
−
l
,
≥
Pr
f
(
U
n
))
∈
[
B
(
g
(
U
2
n
))
g
−
1
(
g
(
U
2
n
))]
∈
−
Pr
[
U
2
n
∈
S
2
n
]
Pr
[
U
2
n
∈
S
2
n
]
1
−
1
n
Pr
[
B
(
g
(
U
2
n
))
∈
g
−
1
(
g
(
U
2
n
))]
−
=
n
·
[
B
(
g
(
U
2
n
))
g
−
1
(
g
(
U
2
n
))])
=
1
−
n
·
(1
−
Pr
∈
4
Throughout the text, we treat log
2
|
x
|
as if it were an integer. A precise argument can be derived by replacing
log
2
|
x
|
with
log
2
|
x
|
and some minor adjustments.
