1 Answers
In cryptography, a hard-core predicate of a one-way function f 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 value h 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 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. 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.