Hard-core predicate

In cryptography, a hard-core predicate of a one-way function f is a predicate b (i.e., a function whose output is a single bit) 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 over random choice of x.

A hard-core function can be defined similarly.

A hard-core predicate captures "in a concentrated sense" the hardness of inverting f.

While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage c from the image f(x). 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.

It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate. Let f be a one-way function. 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}$. This predicate is hard-core due to computational issues; that is, it is not hard to compute because g(x, r) is information theoretically lossy. Rather, if an algorithm exists to compute this predicate efficiently, then an algorithm exists to invert f efficiently. A similar construction yields a hard-core function with log (|x|) output bits.

It is sometimes the case that an actual bit of the input x is hard-core. For example, the low-order bit is hard-core for RSA. It is in fact conjectured that the lower 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 generator 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

$\left\{b(f^{n}(s))\right\}_{n}$

is a pseudorandom bit sequence.

Hard-core predicates of trapdoor one-way permutations can be used to construct semantically secure public-key encryption schemes.

See also

List-decoding (describes list decoding; the core of the Goldreich-Levin construction of hard-core predicates from one-way functions can be viewed as an algorithm for list-decoding the Hadamard code).

References

• Oded Goldreich, Foundations of Cryptography vol 1: Basic Tools, Cambridge University Press, 2001.

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

External Links

• J. Håstad, M. Naslund, The Security of all RSA and Discrete Log Bits (2004): Journal of the ACM (JACM), 2004.