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