# Hard-core predicate

(Redirected from Hard core predicate)

In cryptography, a hard-core predicate of a one-way function f(x) is a predicate b(x) which is easy to compute given x but is hard to compute given f(x). In formal terms, there is no probabilistic polynomial time algorithm that computes b(x) from f(x) with probability significantly greater than one half.

A hard-core predicate captures "in a concentrated sense" the hardness of inverting f. More generally, a hard-core function is a function that has the same property.

While a one-way function is hard to invert, it makes no guarantees about the feasibility of computing partial information about the preimage. For instance, while RSA is conjectured to be a one-way function, the Jacobi symbol of the preimage can be easily computed from that of the image.

Therefore a one-way function alone is not sufficient for encryption. This notion is called semantic security. Hard-core predicates are used to get around this problem; for instance see probabilistic encryption.

It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Goldreich and Levin (1989) showed how every length-preserving one-way function can be trivially modified so that it has a specific hard-core predicate. Let f be a length-preserving one-way function, that is, one for which | f(x) | = | x | for all x. Define

g(x, r) = (f(x), r),

where the length of r is the same as that of x. Let xj denote the jth bit of x and rj the jth bit of r. Then

$b(x, r) = \bigoplus_j x_j r_j$

is a hard core predicate of g. A similar construction yields a hard-core function with log (|x|) output bits.

It is often the case that an actual bit of x is hard-core, such as last bit of RSA is hard-core. It is in fact conjectured that the latter half of the bits are all hard-core for RSA; in other words, the latter-half bits constitute a hard-core function. Note that this is stronger than each of the latter bits being hard-core predicates individually, because f(x) may reveal correlations between certain bits of x without revealing anything about individual bits.

Hard-core predicates give a way to construct a pseudorandom sequence from any one-way permutation. If b is a hard-core predicate of a one way function f, and s is a random seed, then

{b(fn(s))}n

is a pseudorandom bit sequence.

## References

Top Encyclopedia Articles
 Encyclopedia Index animal human sexuality human growth hormone DNA human body human anatomy genetics human cloning human heart human brain human genome project amino acids gene human skeleton

07-14-2008 23:18:10