Cryptography Reference

In-Depth Information

easy

x

f(x)

HARD

Fig. 2.1 One-way functions - an illustration.

2.1

One-way functions

One-way functions are functions that are eciently computable but

infeasible to invert (in an average-case sense). That is, a function
f
:

{

}
∗
is called
one-way
if there is an ecient algorithm

that on input
x
outputs
f
(
x
), whereas any feasible algorithm that tries

to find a preimage of
f
(
x
) under
f
may succeed only with negligible

probability (where the probability is taken uniformly over the choices

of
x
and the algorithm's coin tosses). Associating feasible computations

with probabilistic polynomial-time algorithms, we obtain the following

definition.

}
∗
→{

0
,
1

0
,
1

}
∗
→{

}
∗

Definition 2.1.
(one-way functions):
A function
f
:

{

0
,
1

0
,
1

is called
one-way
if the following two conditions hold:

(1)
easy to evaluate:
There exist a polynomial-time algorithm
A

such that
A
(
x
)=
f
(
x
)forevery
x

}
∗
.

(2)
hard to invert:
For every probabilistic polynomial-time algo-

rithm
A
,everypolynomial
p
, and all su
ciently large
n
,

∈{

0
,
1

1

p
(
n
)

Pr[
A
(
f
(
x
)
,
1
n
)

f
−
1
(
f
(
x
))]
<

∈