Prove that there is no universal Hard-Core Predicates

Question

A polynomial-time-computable predicate $b:\{0,1\}^* \to \{0,1\}$ is called a universal hard-core predicate if for every one-way function $f$, the predicate $b$ is a hard-core of $f$.

I need to prove that there is no such universal hard-core predicate.

Answer 1

Assume $b$ is a universal hardcore predicate. Consider a one-way function $f$ and define $g(x) = f(x) \| b(x)$. Observe that $g$ is one way because

• Both $b$ and $f$ are polynomial time computable.
• If an adversary $\mathcal{A}$ can invert $g$ with a non-negligible advantage, then it can be used to invert $f$ as follows. On input $f(x)$, invoke $\mathcal{A}$ on two different inputs $f(x) \| 0$ and $f(x) \| 1$. For at least one of these instances, it would return a preimage $x'$ such that $f(x) = f(x')$ with a non-negligible advantage.

For this one-way function $g$, $b$ is not a hardcore predicate! This is because the last bit of the output of $g$ contains $b(x)$.