Cryptography Reference
In-Depth Information
PPT algorithms fail with non-negligible probability, see e.g., [86, Chap. 2], [90,
Chap. 2]).
Since the existence of one-way functions has not been unconditionally proven, we
have to settle for working with
candidate one-way functions
, which are functions that
can be proved one-way under the hypothesis that some well-studied computational
problem is hard. The most famous of these problems is the integer factorization prob-
lemwhich we have already mentioned. Its presumed hardness leads to the conjecture
that the function
y
is one-way if
x
and
y
are integers (or even primes)
of the same length. Formally, if we want to view this as a function from
(
x
,
y
)
→
x
·
}
∗
{
0
,
1
to
}
∗
,
mult
(
itself, we may define for a string
s
∈{
0
,
1
s
)
=
xy
, where
x
is the integer
represented by the first
n
/
2
bits of
s
and
y
the one corresponding to the last
n
/
2
bits of
s
.
Remark 3.5
The necessity of putting some condition on the lengths of the factors
x
,
y
above when defining the candidate one-way function comes from the fact that
factoring a number with small factors is easy. Since the product
xy
is even most of
the time, without this restriction it would be easy to return the pair of factors 2,
xy
/
2.
The previous definition considers a single function but, to apply this concept
to cryptographic practice, it is more convenient to deal with a family of one-way
functions parameterized by a security parameter 1
n
.
Definition 3.10
A family of functions
R
i
}
i
∈
I
, where
I
is a set and
D
i
,
R
i
are finite sets, is
one-way
if the following conditions hold:
1. There exists a PPT parameter generation algorithm
Gen
which takes as input a
security parameter 1
n
and outputs an index
i
such that len
{
f
i
:
D
i
→
n
.
2. There exists a PPT sampling algorithm
Samp
which, on input
i
(
i
)
≥
∈
I
, outputs
←
(with uniform distribution)
x
D
i
(except possibly with probability negligible
).
3. There exists a deterministic polynomial-time evaluation algorithm
Eval
which,
on input
i
in len
(
i
)
∈
I
and
x
∈
D
i
, outputs
f
i
(
x
)
.
4. For every PPT algorithm
A
there exists a negligible function
negl
such that if
1
n
i
←
Gen
(
)
,
x
←
Samp
(
i
)
,
y
:=
Eval
(
i
,
x
)
:
Pr
(
f
i
(A(
i
,
y
))
=
y
)
≤
negl
(
n
).
If, moreover,
D
i
=
R
i
for each
i
∈
I
and the
f
i
are bijections, then
{
f
i
}
I
is called a
family of one-way permutations.
Remark 3.6
The existence of a family of one-way functions is equivalent to the
existence of a single one-way function as previously defined (see, e.g., [90, Theorem
2.13]).
Exercise 3.11
Define an
inversion experiment
for a family of functions (given by
algorithms
Gen
,
Samp
,
Eval
as above) similar to the experiment inDefinition 3.8 and
formulate the definition of a family of one-way functions in terms of this experiment.
