Cryptography Reference
In-Depth Information
that the functions cannot be inverted even by non-uniform families of polynomial-size
circuits. We stress that the easy-to-compute condition is still stated in terms of uniform
algorithms. For example, the following is a non-uniform version of the definition of
strong (length-preserving) one-way functions.
Definition 2.2.6 (Non-Uniformly Strong One-Way Functions):
A function f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
is called
non-uniformly one-way
if the following two condi-
tions hold:
1.
Easy to compute:
There exists a polynomial-time algorithm A such that on input
x algorithm A outputs f
(
x
)
.
2.
Hard to invert:
For every
(
even non-uniform
)
family of polynomial-size circuits
{
C
n
}
n
∈N
, every positive polynomial p
(
·
)
, and all sufficiently large n's,
1
p
(
n
)
f
−
1
(
f
(
U
n
))]
Pr
[
C
n
(
f
(
U
n
))
∈
<
The probability in the second condition is taken only over all the possible values of
U
n
. We note that any non-uniformly one-way function is one-way (i.e., in the uniform
sense).
Proposition 2.2.7:
If f is non-uniformly one-way, then it is one-way. That is, if
f satisfies Definition 2.2.6, then it also satisfies Definition 2.2.1.
Proof:
We convert any (uniform) probabilistic polynomial-time inverting algo-
rithm into a non-uniform family of polynomial-size circuits, without decreas-
ing the success probability. This is in accordance with our meta-theorem (see
Section 1.3.3). Details follow.
Let
A
be a probabilistic polynomial-time (inverting) algorithm. Let
r
n
denote a
sequence of coin tosses for
A
maximizing the success probability of
A
(averaged
over input
f
(
U
n
)). Namely,
r
n
satisfies
[
A
r
n
(
f
(
U
n
))
f
−
1
(
f
(
U
n
))]
[
A
(
f
(
U
n
))
f
−
1
(
f
(
U
n
))]
Pr
∈
≥
Pr
∈
where the first probability is taken only over all possible values of
U
n
, and the
second probability is also over all possible coin tosses for
A
. (Recall that
A
r
(
y
)
denotes the output of algorithm
A
on input
y
and internal coin tosses
r
.) The
desired circuit
C
n
incorporates the code of algorithm
A
and the sequence
r
n
(which is of length polynomial in
n
).
We note that, typically, averaging arguments (of the form applied earlier) allow us
to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size
circuits. Thus, in general, non-uniform notions of security (i.e., robustness against non-
uniform polynomial-size circuits) imply uniform notions of security (i.e., robustness
against probabilistic polynomial-time algorithms). The converse is not necessarily true.
In particular, it is possible that one-way functions exist (in the uniform sense) and yet
42
