Hardcore predicate

From CRYPTUTOR

A hardcore predicate (or hardcore bit) of a one-way function f is a boolean predicate that is easy to compute given x, but hard to compute given f(x).

Definition

Let f be a one-way function, and B be a boolean predicate. B is a hardcore predicate of f if:

• Efficiently computable: B(x) can be computed in polynomial time in | x | .
• Hard to guess given f(x): For all non-uniform PPT (polynomial in the security parameter k) adversaries A, the advantage of A in the following experiment is negligible in k:

Hardcore Predicate Guessing Experiment:

1. We choose a random .
2. We compute z = f(x) and give it to the adversary A.
3. A outputs a bit b (a guess for B(x)).

We say that the advantage of A in this experiment is .

Another interpretation of the second requirement is that B(x) is pseudorandom given f(x).

Existence

Any one-way function can be slightly modified to give another one-way function that has a hardcore predicate, using the Goldreich-Levin construction.

Hardcore functions

Instead of a single bit, we can also consider longer functions of x which are hard to guess given f(x). For such a function , we modify the hardcore experiment in the following way:

Hardcore Function Experiment:
As before, given f(x) for a random x, the adversary tries to guess a value h for H(x) . We say that the advantage of A in this experiment is .

A function H is called a hardcore function of f if for all adversaries A, the advantage of A in the above experiment is negligible.

Using a longer hardcore function can often improve the efficiency in constructions that use hardcore bits, such as the construction of a PRG from a OWP.