Cryptography Reference

In-Depth Information

invokes the
F
-inverter (polynomially) many times, each time feeding it

with a sequence of random
f
-images that contains
y
at a random loca-

tion. (Indeed such a sequence corresponds to a random image of
F
.)

The analysis of this reduction, presented in (65, Sec. 2.3), demonstrates

that dealing with computational diculty is much more involved than

the analogous combinatorial question. An alternative demonstration of

the diculty of reasoning about computational diculty (in compar-

ison to an analogous purely probabilistic situation) is provided in the

proof of Theorem 2.5.

2.2

Hard-core predicates

Loosely speaking, saying that a function
f
is one-way implies that given

y
(in the range of
f
) it is infeasible to find a preimage of
y
under
f
.

This does not mean that it is infeasible to find out partial informa-

tion about the preimage(s) of
y
under
f
. Specifically it may be easy

to retrieve half of the bits of the preimage (e.g., given a one-way func-

tion
f
consider the function
g
defined by
g
(
x, r
)
de
=(
f
(
x
)
,r
), for every

|x|
=
|r|
). As will become clear in subsequent sections, hiding partial

information (about the function's preimage) plays an important role

in more advanced constructs (e.g., secure encryption). Thus, we will

first show how to transform any one-way function into a one-way func-

tion that hides specific partial information about its preimage, where

this partial information is easy to compute from the preimage itself.

This partial information can be considered as a “hard core” of the dif-

ficulty of inverting
f
. Loosely speaking, a
polynomial-time computable

(Boolean) predicate
b
, is called a hard-core of a function
f
if no feasible

algorithm, given
f
(
x
), can guess
b
(
x
) with success probability that is

non-negligibly better than one half.

Definition 2.4.
(hard-core predicates (31)):
A polynomial-time com-

putable predicate
b
:

}
∗
→{

is called a
hard-core
of a function

f
if for every probabilistic polynomial-time algorithm
A
, every positive

{

0
,
1

0
,
1

}