Cryptography Reference
In-Depth Information
algorithm inverting
f
uni
on inputs of the form
f
uni
(desc(
M
g
)
U
n
) with probability
p
(
n
) can be easily modified into an (efficient) algorithm inverting
g
on inputs
of the form
g
(
U
n
) with probability
p
(
n
). As in the proof of Proposition 2.3.1,
it follows that an algorithm inverting
f
uni
with probability at least 1
−
ε
(
n
)on
strings of length
|
desc(
M
g
)
|+
n
yields an algorithm inverting
g
with probability
at least 1
−
2
|
desc(
M
g
)
|
·
ε
(
n
) on strings of length
n
. (We stress that
|
desc(
M
g
)
|
is
a constant, depending only on
g
.) Hence, if
f
uni
is not weakly one-way (i.e., the
function
ε
is not noticeable), then also
g
cannot be (weakly) one-way (i.e., also
2
|
desc(
M
g
)
|
·
ε
is not noticeable).
Using Theorem 2.3.2 (to transform the weak one-way function
,
f
uni
into a
strong one), the proposition follows.
Discussion.
The observation by which it suffices to consider one-way functions that
can be evaluated within a specific time bound is crucial to the construction of
f
uni
,
the reason being that it is not possible to construct a polynomial-time machine that is
universal for the class of all polynomial-time machines (i.e., a polynomial-time machine
that can “simulate” all polynomial-time machines). It is, however, possible to construct,
for every polynomial
p
(
), a polynomial-time machine that is universal for the class of
machines with running time bounded by
p
(
·
).
The impracticality of the construction of
f
uni
stems from the fact that
f
uni
is likely to
be hard to invert only on huge input lengths (i.e., lengths allowing the encoding of non-
trivial algorithms as required for the evaluation of one-way functions). Furthermore, to
obtain a strongly one-way function from
f
uni
, we need to apply the latter on a sequence
of more than 2
L
·
n
, where
L
is a lower bound on the length
of the encoding of potential one-way functions, and
n
is our actual security parameter.
Still, Proposition 2.4.1 says that, in principle, the question of whether or not one-
way functions exist “reduces” to the question of whether or not a specific function is
one-way.
inputs, each of length
L
+
2.4.2. One-Way Functions as Collections
The formulation of one-way functions used thus far is suitable for an abstract dis-
cussion. However, for describing many natural candidates for one-way functions,
the following formulation (although being more cumbersome) is more serviceable.
Instead of viewing one-way functions as functions operating on an infinite domain
(i.e.,
}
∗
), we consider infinite collections of functions each operating on a finite do-
main. The functions in the collection share a single evaluating algorithm that when given
as input a succinct representation of a function and an element in its domain returns
the value of the specified function at the given point. The formulation of a collection
of functions is also useful for the presentation of trapdoor permutations and claw-
free functions (see Sections 2.4.4 and 2.4.5, respectively). We start with the following
definition.
{
0
,
1
Definition 2.4.2 (Collection of Functions):
A
collection of functions
consists
of an infinite set of
indices
,
denoted I , and a corresponding set of finite functions,
53
