Explore the foundations of lattice-based cryptography in this Richard M. Karp Distinguished Lecture by Daniele Micciancio from UC San Diego. Delve into the mathematical problems on point lattices that form the basis of modern cryptographic functions. Discover how these lattice-based systems offer resistance against quantum adversaries and enable computations on encrypted data. Learn about the evolution from subset-sum and knapsack problems to lattice problems, and understand key concepts like Learning With Errors (LWE) encryption. Examine the development of Fully Homomorphic Encryption (FHE), including homomorphic addition, multiplication, and bootstrapping techniques. Gain insights into the geometric aspects of lattices, public key encryption methods, and the timeline of FHE advancements. This comprehensive lecture provides a thorough overview of lattice-based cryptography, its theoretical foundations, and its potential applications in post-quantum security and homomorphic encryption.
Lattices, Post-Quantum Security and Homomorphic Encryption
Overview
Syllabus
Lattices, Post-Quantum Security, and Fully Homomorphic Encryption
Modern Cryptography
Factoring and Quantum (In)Security
Subset-Sum Problem
Subset-Sum / Knapsack • Also known as the "Knapsack" problem - Fill a knapsack of capacity b - using a selection of items of size ai.....an
Lattice/Knapsack Cryptgraphy: abridged (pre-)history . Knapsack public key cryptosystem
Subset-Sum vs Lattice Problems
Geometry of Lattices
Linear functions
Learning With Errors (LWE)
Encrypting with LWE
FHE Timeline
Homomorphic Addition
Multiplication by any constant
Public Key Encryption
How to multiply two ciphertexts
Multiplication by Encryption Nesting
Multiplication by Tensoring
Decryption is linear
Multiplication via Homomorphic Decryption
Homomorphic "decrypt and multiply"
Relation to GSW encryption
Bootstrapping and FHE
FHEW: gate bootstrapping
Summary
Additional References
Taught by
Simons Institute
