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 ))] <       Search WWH ::

Custom Search