In cryptography, a hard-core predicate of a one-way functionf is a predicate b which is easy to compute but is hard to compute given f. In formal terms, there is no probabilistic polynomial-time algorithm that computes b from f with probability significantly greater than one half over random choice of x. In other words, if x is drawn uniformly at random, then given f, any PPT adversary can only distinguish the hard-core bit b and a uniformly random bit with negligible advantage over the length of x. A hard-core function can be defined similarly. That is, if x is chosen uniformly at random, then given f, any PPT algorithm can only distinguish the hard-core function valueh and uniformly random bits of length |h| with negligible advantage over the length of x. A hard-core predicate captures "in a concentrated sense" the hardness of invertingf. While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimagec from the image f. 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 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 = 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 is a hard core predicate of g. Note that b = <x, r> where <·, ·> denotes the standard inner product on the vector spacen. This predicate is hard-core due to computational issues; that is, it is not hard to compute because g is information theoretically lossy. Rather, if there exists an algorithm that computes this predicate efficiently, then there is another algorithm that can invert f efficiently. A similar construction yields a hard-core function with O output bits. Suppose f is a strong one-way function. Define g = where |r| = 2|x|. Choose a length functionl = O s.t. l ≤ n. Let Then h := b1 b2... bl is a hard-core function with output length l. It is sometimes the case that an actual bit of the input x is hard-core. For example, every single bit of inputs to the RSA function is a hard-core predicate of RSA and blocks of O bits of x are indistinguishable from random bit strings in polynomial time. 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 permutationf, and s is a random seed, then is a pseudorandom bit sequence, where fn means the n-th iteration of applying f on s, and b is the generated hard-core bit by each roundn. Hard-core predicates of trapdoor one-way permutations can be used to construct semantically securepublic-key encryption schemes.
