The Learning With Errors Assumption and the Random Oracle Model
Stub. The random oracle model as an idealized proof heuristic (model a hash function as a truly random function); the standard definitions of symmetric encryption and its security (building on, but formalizing more carefully than, the one-time pad and CPA-security notions elsewhere in this vault); and the Learning With Errors (LWE) assumption — both its search and decisional forms — the lattice-based hardness assumption that quantum computers aren't known to break, underlying essentially all of this course's post-quantum constructions.
Corresponds to Chapter 15. The random oracle model is a standard proof heuristic (treat a hash function as if it returned a uniformly random, independent output on every new query) used to prove protocols secure, with the caveat that a security proof in this model doesn’t automatically transfer to any concrete hash function. Reviews the formal definitions of a symmetric encryption scheme and its security — the one-time pad (classical-cryptography-and-perfect-secrecy) and CPA security for single and multiple messages (private-key-encryption-and-pseudorandomness covers these classical definitions in full) — as the baseline this course’s quantum and lattice-based schemes are held to the same standard as. The Learning With Errors (LWE) assumption is the chapter’s main event: given many noisy linear equations over a finite field, it’s computationally hard to recover the secret vector (search-LWE) or even to distinguish such equations from uniformly random ones (decisional-LWE) — a problem with no known efficient quantum algorithm, unlike factoring/discrete-log, which is exactly why LWE-based cryptography is the leading candidate for post-quantum security.
Outline (TODO — flesh out each)
- The random oracle model
- Definition of a symmetric encryption scheme (classical setting)
- Definition of security — CPA security for single and multiple messages
- The Learning With Errors (LWE) assumption
- Search-LWE
- Decisional-LWE