From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit

From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences Science — General & History GPResearch and information: generalGPJCoding theory and cryptology
🎙 Ryan O'Donnell 👥 14K 📅 July 10, 2020 ⏱ 27 min 👁 792 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

pseudorandom generatorone-way functionsymmetric key encryptioncomputational securityHILL theorem

Summary

This lecture, part of CMU’s CS Theory Toolkit, explores the foundational relationship between cryptographic primitives. It begins by defining cryptographic pseudorandom generators (PRGs) as deterministic polynomial-time functions that expand a short random seed into a longer string computationally indistinguishable from uniform. The lecture emphasizes that PRGs are a basic assumption, stronger than P ≠ NP, and sketches how to stretch a PRG from n+1 bits to polynomial expansion using a hybrid argument. It then demonstrates how a PRG can be used to construct a computationally secure symmetric key encryption (SKE) scheme for single messages, essentially a one-time pad with a pseudorandom pad. The limitations of this scheme (one-time use) are discussed, leading to the notion of chosen-plaintext attack (CPA) security, which can be achieved via pseudorandom functions (PRFs), themselves constructible from PRGs. The lecture then introduces one-way functions (OWFs) as the weakest assumed primitive, defines them, and mentions the HILL theorem (1999) showing that PRGs can be constructed from OWFs. It also discusses weak OWFs and a construction to strengthen them. A candidate OWF based on subset sum is presented. Finally, the lecture situates these results within Impagliazzo’s Five Worlds, distinguishing between Minicrypt (where OWFs exist) and Cryptomania (where public-key encryption exists).

202 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides high-value information by clearly explaining the logical dependencies between core cryptographic primitives. It offers rigorous definitions and proofs, such as the construction of a PRG with polynomial expansion from a single-bit-stretching PRG using a hybrid argument, and the proof that a PRG-based encryption scheme is computationally secure. The argumentation is solid, building from assumptions to constructions with clear reasoning. The discussion of the HILL theorem and Impagliazzo’s Five Worlds adds depth, showing the broader theoretical landscape. The lecture is well-structured, progressing from PRGs to SKE to OWFs, and effectively conveys the importance of average-case hardness in cryptography.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with precise definitions and proofs. It references the HILL theorem (Håstad, Impagliazzo, Levin, Luby, 1999) and Impagliazzo’s ‘A Personal View of Average-Case Complexity’ (1995), both foundational works. The course resource ‘A Course in Cryptography’ by Pass and Shelat is cited. The title accurately reflects the content, which indeed covers the path from one-way functions to symmetric key encryption. The lecture is delivered by a recognized expert, enhancing credibility. No comments were provided for analysis.

194 words

Title / Content Match

The title accurately describes the content: the lecture covers the construction of symmetric key encryption from one-way functions via pseudorandom generators.

Quality & Reliability

9/10

Lecture by a renowned CMU professor, rigorous definitions and proofs, references to foundational results (HILL theorem, Impagliazzo's Five Worlds), and a course resource. No unsubstantiated claims.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

  • A Course in Cryptography — Textbook by Pass and Shelat, referenced as a resource for the lecture.

Contribution & Novelties

This lecture provides a clear and rigorous exposition of the foundational connections in cryptography, from one-way functions to symmetric key encryption. It effectively explains the role of computational indistinguishability and the importance of average-case hardness. The lecture’s contribution lies in its pedagogical clarity and the way it ties together key results like the HILL theorem and Impagliazzo’s Five Worlds.

Pour aller plus loin :

  • HILL theorem — The HILL theorem is a foundational result showing that pseudorandom generators can be constructed from one-way functions.
  • Impagliazzo’s Five Worlds — A framework for understanding possible worlds of average-case complexity.
  • Pseudorandom generator — General concept and cryptographic applications.
  • One-way function — Definition and examples.
  • Symmetric-key algorithm — Overview of symmetric key encryption.

119 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous, with strong reliability. The balance between quantity and quality is excellent, making it a valuable resource for advanced students.

Reliability 9/10