4. Hard-core Bit (Hard-core Prediction)

Hard-core Bit is not a “bit”, but a True/False prediction, so it is often called Hard-core prediction.

Hard-core Bit \(B\) is used to measure the leakage of information about \(x\) from the trapdoor function \(f\). So, a hard-core bit \(B\) should be:

• Easy to compute/predict if \(x\) is known

• Hard to compute/predict if only \(f(x)\) is known. The hardness is measure in the following way: There doesn’t exist a probabilistic polynomial-time (PPT) algorithm which can do better prediction of \(B(x)\) than flipping a coin with indistinguishable threshold.

For example. Assume the function \(f(x) = x^2\) and \(x \neq 0\). Hard-core bit \(B\) is to predict whether \(x > 0\).

If \(x\) is given, \(B(x)\) is pretty easy. But if only \(f(x)\) is known, you cannot predict \(B(x)\) better than randomly guessing. So \(B\) here is a hard-core prediction for \(f\). But if you choose \(B'\) to predict whether \(\|x\| > 100 `, the situation is the opposite. :math:`B'\) is not a hard-core prediction.