「Cryptography-MIT6875」: Lecture 7
It is indeed possible for $F(x)$ to leak a lot of information about $x$ even if $F$ is one-way.
The hardcore predicate $B(x)$ represent the specific piece of information about $x$ which is hard to compute given $F(x)$.
- Definition of one-way functions (OWF)
- Definition of hardcore bit/predicate (HCB)
- One-way permutations → PRG.
(In fact, one-way functions → PRG, but that’s a much harder theorem.)
- Goldreich-Levin Theorem: every OWF has a HCB.
(Proof for an important special case.)