Opening From One-Way Functions to Symmetric Key Encryption
From One-Way Functions to Symmetric Key Encryption
- Length
- 27 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Cryptographic pseudorandom generators
Amplifies a one-bit-stretch pseudorandom generator by a hybrid argument, then uses its output as a one-time pad.
Cryptographic pseudorandom generators and symmetric key encryption can both be built from one-way functions through complexity-theoretic reductions. O'Donnell defines a PRG as a map stretching an -bit seed into a longer string no polynomial-time adversary can distinguish from random. A hybrid argument across sequential evaluations then amplifies a generator that stretches by one bit into one of polynomial stretch. Used as a pseudorandom one-time pad, the PRG gives single-message computationally secure symmetric key encryption. O'Donnell then outlines the HILL theorem of Håstad, Impagliazzo, Levin and Luby, which obtains PRGs from weak one-way functions. Impagliazzo's five worlds of average-case complexity round out this CMU 15-750: A Theorist's Toolkit session, which assumes computational indistinguishability and hybrid arguments.
Cryptographic pseudorandom generators and symmetric key encryption can both be built from one-way functions through complexity-theoretic reductions. O'Donnell defines a PRG as a map stretching an -bit seed into a longer string no polynomial-time adversary can distinguish from random. A hybrid argument across sequential evaluations then amplifies a generator that stretches by one bit into one of polynomial stretch. Used as a pseudorandom one-time pad, the PRG gives single-message computationally secure symmetric key encryption. O'Donnell then outlines the HILL theorem of Håstad, Impagliazzo, Levin and Luby, which obtains PRGs from weak one-way functions. Impagliazzo's five worlds of average-case complexity round out this CMU 15-750: A Theorist's Toolkit session, which assumes computational indistinguishability and hybrid arguments.
Hill '99
A personal view of average-case complexity

This lecture
Lecture 81 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in