• Pseudorandom Functions. • From OWFs to PRFs via PRGs: the GGM Construction. • From PRGs to One-Time Symmetric Encryption.

• PRG: short random seed s 7 → G(s) long “random looking ” output. • PRF: short random key K 7 → FK(·) “random looking ” function. Definition 1 [Pseudorandom Function] A pseudorandom function (PRF) is a family of functions {FK: {0, 1}m(n) → {0, 1}`(n)}n∈N,K∈{0,1}n such that: • Efficiency: one can compute FK(x) in poly(n)-time (given K and x); • Security: for any poly-time adversary A:∣∣∣Pr [AFK(·)(1n) = 1] − Pr [AR(·)(1n) = 1]∣∣ ∣ ≤ negl(n). where K $ ← {0, 1}n and R $ ← F({0, 1}m(n) → {0, 1}`(n)) with F({0, 1}m(n) → {0, 1}`(n)) denoting the set of all functions mapping m(n) bits to `(n) bits. Remark 1 Note that describing a truly random function R: {0, 1}m(n) → {0, 1}`(n) would require 2m(n) · `(n) bits. So we cannot even efficiently describe such functions, let alone evaluate them. However, the point of building pseudorandom functions, is to have a function FK that looks like a random function to the outside world, but can be described with only an n bit key K and can be evaluated efficiently. You might want to think of AR(·) as the experiment where the outputs of R(·) are chose