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 $x_{j}$ denote the j^th bit of x and $r_{j}$ the j^th bit of r. Then

$b(x,r)=\bigoplus _{j}x_{j}r_{j}$

is a hard core predicate of g. Note that $b(x,r)=\langle x,r\rangle$ where $\langle \cdot ,\cdot \rangle$ denotes the standard inner product on the vector space $(\mathbb {Z} /2\mathbb {Z} )^{n}$. 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(f^{n}(s))\}_{n}$

is a pseudorandom bit sequence.

References

• Oded Goldreich and Leonid A. Levin, A Hard-Core Predicate for all One-Way Functions, STOC 1989, pp25–32.