Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
as the organisers put it
The semester will begin with a boot camp featuring introductory talks meant to create a common language among the participants and to highlight the important open questions in the field. Among the main topics to be covered are: (a) Algorithms for Lattice Problems; (b) Complexity of Lattice Problems; (c) Lattice-based Cryptography and (d) Algebraic Lattices and Practical Lattice Cryptography.
who it's for
lattice cryptographers, cryptographers, theoretical computer scientists, cryptanalysts, software implementers, quantum algorithms researchers, graduate students
topics
lattice basis reduction (BKZ and LLL); shortest vector problem (SVP); closest vector problem (CVP); learning with errors (LWE); short integer solution (SIS); Ring-LWE and ideal lattices; discrete Gaussian trapdoors and sampling; sieving algorithms for SVP; quantum algorithms for algebraic lattices; lattice trapdoors and IBE/ABE; lattice cryptanalysis and Coppersmith methods
| title | author | length |
|---|---|---|
| Mathematics of Lattices | Daniele Micciancio | 01h 42m |
Straightforward introduction to lattice math with no new results: precise definitions (determinant, successive minima, covering radius), basic theorems… | ||
| Algorithms for Lattice Problems | Noah Stephens-Davidowitz | 01h 13m |
Survey of concrete SVP algorithms and their costs: classic sieving is implemented and practical but lacks proofs; a provable 2^{n} provable sieving method via… | ||
| Complexity of Lattice Problems | Noah Stephens-Davidowitz | 01h 03m |
Defines precise reductions and runtimes: SVP reduces to CVP by doubling one basis coordinate, and CVP is NP‑hard via a subset‑sum basis construction that makes… | ||
| The Short Integer Solutions Problem and Cryptographic Applications | Daniele Micciancio | 01h 32m |
Defines SIS as solving A·x ≡ y (mod q) for short x (typically n, m, q matrix A and x in {0,1}^m), proves average-case hardness by reducing worst-case lattice… | ||
| The Learning With Errors Problem and Cryptographic Applications | Chris Peikert | 01h 28m |
Defines LWE with modulus q (typically polynomial in n) and Gaussian error (std ≈ √n), proves a quantum worst-case to average-case reduction from GapSVP/SIVP… | ||
| Algebraic Lattices and Ring Learning with Errors | Chris Peikert | 01h 15m |
Defines Ring-LWE over integer polynomial rings, proves a quantum worst-case→average-case reduction from approximate SIVP on ideal lattices, and gives a… | ||
| Algorithms for Algebraic Lattices: Classical and Quantum | Léo Ducas | 01h 36m |
Claim: quantum procedures turn ideal-SVP on cyclotomic rings from seemingly exponential hardness into an approx exp(√n) drop (and even polynomial beyond that… | ||
| Algorithms for Lattice Problems, in Practice | Elena Kirshanova, Pierre-Alain Fouque | 57m |
Gives a concrete criterion when lattice reduction actually recovers an LWE secret: compare the unusually short vector’s length to the BKZ/GSA output and pick… | ||
| Using Lattices for Cryptanalysis | Nadia Heninger | 01h 04m |
Lattice reduction using LLL and BKZ yields practical cryptanalysis: lattices up to a few thousand dimensions run (a reported 4096-dim / 6000-bit in four days… | ||
| Lattices and the NIST PQ-crypto Standardization Process | Damien Stehlé | 01h 02m |
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… | ||
| Lattices and Encrypted Computation | Vinod Vaikuntanathan | 01h 07m |
Shows a concrete path from LWE to practical fully homomorphic encryption: tensor ciphertexts to multiply, use bit-decomposition to do scalar products, and… | ||
| Lattice Trapdoors | Shweta Agrawal | 01h 02m |
Constructs practical lattice trapdoors by fixing a gadget matrix G (powers-of-two), showing how small Gaussian R yields a randomized public matrix A = [B | G −… | ||
| How to Use Lattice Trapdoors: IBE, ABE and More | Shweta Agrawal | 01h 16m |
Shows how to get IBE/ABE from lattice trapdoors by combining Regev encryption with explicit trapdoor sampling: sample fat matrix A with trapdoor and extend it… | ||
| Lattices, Multilinear Maps and Program Obfuscation | Yilei Chen | 01h 29m |
Describes a concrete lattice-based multilinear map construction that chains LWE samples by trapdoor preimage sampling so A0·D1·D2···Dk evaluates to (∏Si)·Aℓ… | ||
| nothing matches | ||