In formal terms, there is no probabilistic polynomial-time (PPT) algorithm that computes b(x) from f(x) with probability significantly greater than one half over random choice of x.
[1]: 34 In other words, if x is drawn uniformly at random, then given f(x), any PPT adversary can only distinguish the hard-core bit b(x) and a uniformly random bit with negligible advantage over the length of x.
That is, if x is chosen uniformly at random, then given f(x), any PPT algorithm can only distinguish the hard-core function value h(x) and uniformly random bits of length |h(x)| with negligible advantage over the length of x.
[3][4] 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.
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.
is a hard core predicate of g. Note that b(x, r) =
A similar construction yields a hard-core function with O(log |x|) output bits.
[7] Hard-core predicates give a way to construct a pseudorandom generator from any one-way permutation.
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 round n.[1]: 132 Hard-core predicates of trapdoor one-way permutations (known as trapdoor predicates) can be used to construct semantically secure public-key encryption schemes.