Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from security.stackexchange.com Oct 28 '11 at 20:21

This question came from our site for Information security professionals.

    
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to IT security, and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Oct 28 '11 at 20:40
add comment

2 Answers

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 "a bit of x". Not necessarily a bit in the sense of "x can be represented as a sequence of bits"; rather, a function which, from x, returns 0 or 1. The predicate is thus a function which "says something" about x where the something is a binary choice.

For instance, over plain integers, "is multiple of 7" 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 "SHA-256 of y where y is the bit sequence of x with the first bit removed" then the predicate "first bit of x" 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 y2 = x mod n; in plain words, it is "a value which has at least one square root"). 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) = x2 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. x2 mod n), computing b(x) appears to be as hard as factoring n. If you can factor n, you can compute x from x2 and thus computing b(x) becomes easy; the strange part is that there is no known better way to compute b(x) given x2. 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 "only" finding the XOR of the bits of the input is already as hard as that.

Thus, we call the predicate "hard-core".

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.

share|improve this answer
add comment

I'm not sure how much simpler than Wikipedia one can explain this.

Assume you have a function $f$ which gets some input $x$, and produces from it some output $y = f(x)$. As one example, consider the function $f(x) = x·x$.

graph of this function

Assume that $x$ is a non-zero real (or rational, or integer) number. Then $y = f(x) = x·x$ is still a non-zero number, and in this case, always a positive number. I.e. the information about the sign of $x$ is lost.

A predicate in general is a function with only one bit of output, i.e. two different possible values. (Normally we look at functions with values $0$ and $1$, or false and true.)

For our example, we take the predicate $b(x) := (x \geq 0)$, or as a full formula:

$$ b(x) = \begin{cases} 1 \quad & \text{if } x \geq 0 \\ 0 & \text{if }x < 0\end{cases} $$

graph of the predicate

Now, it is easy to calculate $b(x)$ from $x$. But if I only give you $f(x)$ (for a secret number $x$), you have no chance to guess $b(x)$ from this information better than a random guess (i.e. without even knowing $f(x)$).

This means, $b$ is a hard-core predicate for $f$.

In cryptography, we would use instead of this simple quadratic function a cryptographic hash function, or an encryption function (where the attacker does not know the key), and we don't need "impossible to guess" (these functions/predicates are not that interesting), just "too much computation needed for a good chance to guess better than random".

This "too much" is then formally defined as "more than polynomial in some security parameter" (like the output size), i.e. this makes only really sense if we speak about a family of functions.

(Public-domain images from Wikimedia Commons: Parabola, Heaviside.)

share|improve this answer
    
If you give me $y=f(x)$ though, can't I just compute $x'=\sqrt{y}$ and know that the answer is either $b(x')$ or $b(-x')$ –  mikeazo Oct 28 '11 at 22:42
    
In this example, $b(x') = 1$ and $b(-x') = 0$, i.e. we know exactly nothing more than we would know without knowing $f(x)$. (This is not a cryptographic example, though. In cryptography, we usually have functions where $b(x)$ actually is determined by $f(x)$, just really hard to compute (just like $x$ itself).) –  Paŭlo Ebermann Oct 29 '11 at 12:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.