Lattices and the NIST PQ-crypto Standardization Process
summary
NIST receives 76 proposals, 69 pass initial checks and 26 reach Round Two, of which 9 KEMs, 3 signatures are lattice-based; most KEMs use the same A·s framework instantiated as NTRU-like or LWE-like schemes and get CCA via random-oracle transforms (SXY or Fujisaki–Okamoto) in the QROM. Security targets include 2^64 decryption/signature queries and level‑5 ≈ AES‑256. Concrete notes: ~700‑byte Falcon signatures, Dilithium/Tesla trade smaller code for larger signatures, keygen oracles can be costly, and open problems include decryption‑error impact, tight QROM reductions, and realistic BKZ/sieve cost estimates.
AI-written summary · about
chapters (23)
- 0:00Intro
- 0:42The NIST PQ.crypto standardization process
- 5:41Timeline and status
- 7:30Lattice submissions
- 10:23Why should we care?
- 11:02The rest of the talk
- 11:54General design
- 14:10Two instances of the setting
- 17:35Security
- 21:21Which algebraic setup?
- 22:44Which distributions for the small vectors?
- 24:24How to set size parameters?
- 27:57Falcon
- 32:59Dilithium and Tesla
- 33:45Efficiency comparison
- 35:08Roadmap
- 35:41Best known algorithms
- 39:07The choice of the assumption
- 47:17Stretching assumptions
- 53:44Choice of polynomial ring
- 54:58Impact of decryption errors
- 56:00QROM proofs?
- 59:32Post-NIST post-quantum crypto!
related talks
44mPost-quantum cryptography migration strategy for cloud services
36mUpdate on the NIST standardization of additional signature schemes
40mPost-Quantum
29mstandardization of additional signature schemes
43mStatus report on Post Quantum Cryptography Standardization
13mNavigating the Quantum Readiness Journey: Open-Source Cryptography, PKI and Signing Tools
41mLattice based cryptography
39mLattice Based Cryptography Primer