「Cryptography-MIT6875」: Lecture 7

In this series, I will learn MIT 6.875, Foundations of Cryptography, lectured by Vinod Vaikuntanathan.
Any corrections and advice are welcome. ^ - ^

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)$.

Topics Covered:

• 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.)