Hard-core predicate
= Hard-core predicate
{wiki}
A <hard-core predicate> is an efficiently computable bit of an input to a <one-way function> that cannot be predicted from the function output with nonnegligible advantage over random guessing. For a <one-way function> $f$, padding it to $F(x,r)=(f(x),r)$ gives the inner-product predicate $h(x,r)=\sum_jx_jr_j\bmod2$. This is the Goldreich–Levin construction. It provides a way to mask a bit using an otherwise publicly revealed <one-way function> value.