Cryptography Reference
In-Depth Information
%./
C+D
0./
Figure 7.1
A hard-core predicate of a one-way function.
Pr[
A
(
f
(
x
)) =
B
(
x
)]
<
1
1
k
c
2
+
for all
k>k
0
, where the probability is taken over over the random coin tosses of
A
and random choices of
x
of length
k
(i.e., the success probability of
A
is only
negligibly smaller than 1
/
2). It is simple and straightforward to extend the notion of
a hard-core predicate for a family of one-way functions.
Historically, the notion of a hard-core predicate was first captured by Manuel
Blum and Silvio Micali in a paper on pseudorandom number generation [13]. In fact,
they showed that the
most significant bit
(MSB) is a hard-core predicate for the Exp
family. This is in contrast to the RSA family, for which the
least significant bit
(LSB)
represents a hard-core predicate [14]. In the context of probabilistic encryption,
Oded Goldwasser and Micali showed that Square has a hard-core predicate, as well
[15]. Andrew C. Yao
6
generalized the notion of a hard-core predicate and showed
that given any one-way function
f
, there is a predicate
B
(
x
) that is as hard to guess
from
f
(
x
) as to invert
f
[16].
6
In 2000, Andrew Chi-Chih Yao won the Turing Award for his seminal work on the theory of
computation in general, and pseudorandom number generation, cryptography, and communication
complexity in particular.
