Pseudo-random functions

Definition A cryptographically secure pseudorandom function is an efficient algorithm that when given an n-bit seed s, and an n-bit argument x, returns an n-bit string f_s(x) such that it is infeasible to distinguish f_s(x) for random s from a truly random function.

Theorem [Goldreich, Goldwasser, Micali] Cryptographically secure pseudorandom functions can be constructed from cryptographically secure pseudorandom bit bit generators.

Theorem [Luby & Rackoff] The existence of cryptographically secure pseudorandom functions implies the existence of block ciphers that are secure against chosen plaintext attacks.

Most amazing: the construction resembles DES!