Succinct Randomized Encodings from Lattices

on YouTube ↗01h 05m

" summary

Construction gives witness encryption for P and hence succinct randomized encodings with runtime and memory cost polylogarithmic in program time T and memory M, assuming a circular, decomposed LWE variant. It builds homomorphic lattice encodings, a rate-1 lattice encodings booster via bootstrapping, and a Merkle-tree style recursion to evaluate RAM read/write steps and reuse precomputed K_P values; the scheme meets near‑optimal parameters under the assumption but still relies on circularity and heavy lattice/FHE ingredients.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 5:02Lattice-based constructions
3. 13:37Talk outline and homomorphic encodings
4. 15:01Witness encryption attempt
5. 22:53Problems with witness encryption
6. 24:19RAM programs with lattice encodings
7. 32:46Merkle tree for succinctness
8. 41:10Bootstrapping for reduced evaluation time
9. 50:21Assumptions and heuristic
10. 53:54Applications and open problems
11. 1:02:23Q&A

" related talks

• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 46mCandidate Witness Encryption from Lattice TechniquesRotem Tsabary · Quantum and Lattices Joint Reunion Workshop
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 54mGraph-Induced Multilinear Maps from LatticesShai Halevi · The Mathematics of Modern Cryptography
• 01h 40mHistorical Talk on Lattice-Based CryptographyDaniele Micciancio · The Mathematics of Modern Cryptography