Uploaded October 2026 | Updated November 2026, 3 hours ago
Lecture 18 in Ryan O'Donnell's Graduate Computational Complexity course at Carnegie Mellon University.
Lecture 18 in Ryan O'Donnell's Graduate Computational Complexity course at Carnegie Mellon University.










![From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit
Definitions of cryptographic pseudorandom generators (PRGs), one-way functions (OWFs), and related concepts. The famous [HILL] Theorem proving that PRGs and hence symmetric key encryption (SKE) can be constructed from (weak) OWFs is mentioned, as are Impagliazzos Five Worlds. Lecture 25c of CS Theory Toolkit: a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture:
A course in cryptography by Pass and Shelat.
Taught by Ryan ODonnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMUs Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (https://www.rebeccakphoto.com/) From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit](https://i.ytimg.com/vi/c4SrYqN6ItY/mqdefault.jpg)