What is a hard-core predicate? I read this article on Wikipedia: Hard-core predicate.

Still I don't understand what exactly is a hard-core predicate. Is it possible to put this in simple English terminology, and perhaps with a simple example?
In the Lecture Notes on Cryptography of Goldwasser and Bellare, one can find (page 35) the following text:

Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the least significant bit of x from f(x) by a simple Legendre symbol calculation. Yet, it seems likely that there is at least one bit about x which is hard to “guess” from f(x), given that x in its entirety is hard to compute. The question is: can we point to specific bits of x which are hard to compute, and how hard to compute are they. The answer is encouraging. A number of results are known which give a particular bit of x which is hard to guess given f(x) for some particular f’s such as RSA and the discrete logarithm function. We will survey these results in subsequent sections.
More generally, we call a predicate about x which is impossible to compute from f(x) better than guessing it at random a hard-core predicate for f.

So a predicate over $x$ is &quot;a bit of $x$&quot;. Not necessarily a bit in the sense of &quot;$x$ can be represented as a sequence of bits&quot;; rather, a function which, from $x$, returns 0 or 1. The predicate is thus a function which &quot;says something&quot; about $x$ where the something is a binary choice.
For instance, over plain integers, &quot;is multiple of 7&quot; is a predicate (any integer is multiple of 7, or not).
A hard-core predicate of a function $f$ is a predicate of $x$ (an input to $f$) which can easily be computed from $x$ but not from $f(x)$. There are very trivial hard-core predicates when the information is simply lost (e.g. if $f(x)$ is defined as &quot;SHA-256 of $y$ where $y$ is the bit sequence of $x$ with the first bit removed&quot; then the predicate &quot;first bit of $x$&quot; cannot, by definition, be recomputed from $f(x)$); these are not interesting for cryptography. More interesting are predicates which do have a well-defined value for a given $f(x)$ (i.e. for a given value $z$, the predicate $b(x)$ has always the same value for all $x$ such that $f(x) = z$).
One example of hard-core predicate is in the BBS pseudo-random generator. Let $n = pq$ a big integer (like a RSA modulus), where both $p$ and $q$ are equal to $3$ modulo $4$. Consider the subset of integers modulo $n$ which are coprime to $n$ and are quadratic residues (a quadratic residue is a value $x$ such that there exists an integer $y$ such that $y^2 \equiv x \mod n$; in plain words, it is &quot;a value which has at least one square root&quot;). It can be shown that a quadratic residue (coprime to $n$) has 4 distinct square roots, and exactly one of them is itself a quadratic residue.
Thus, we can define the function $f(x) = x^2 \mod n$. It is a permutation of the quadratic residues modulo $n$. For a given quadratic residue $y$, there is a single quadratic residue $x$ such that $f(x) = y$.
Now, the predicate: I define $b(x)$ to be the XOR of all the bits of the binary representation of $x$. It returns 0 or 1 (it is a predicate). Given $x$, computing it is trivial. However, given $f(x)$ (i.e. $x^2 \mod n$), computing $b(x)$ appears to be as hard as factoring $n$. If you can factor $n$, you can compute $x$ from $x^2$ and thus computing $b(x)$ becomes easy; the strange part is that there is no known better way to compute $b(x)$ given $x^2$. The predicate $b$ is then said to capture the essence of the one-wayness of $f$: given the output of $f$, not only is it hard to find the matching input, but &quot;only&quot; finding the XOR of the bits of the input is already as hard as that.
Thus, we call the predicate &quot;hard-core&quot;.
It is like saying that to invade the USA you have to defeat the whole of fighting-able US citizens, one of them being Chuck Norris. It is reasonable to assume that if you can beat Chuck Norris, then the rest of them should be a piece of cake. Chuck Norris is the hard-core predicate of US military supremacy.