Advanced Topics in Cryptography - Lattices (Fall 2025)
Lattices in complexity theory, cryptography, and quantum computation.
Friday 9:50 - 12:15, 4305
Office hour: Friday 13:30-14:30 at FIT building, 6th floor, 4-6008
Office hour: Friday 13:30-14:30 at FIT building, 6th floor, 4-6008
Email: [email protected]
TAs: Liheng Ji, Han Luo
Main reference for lattice and complexity theory:
Micciancio and Goldwasser: Complexity of lattice problems: A cryptographic perspective
Micciancio and Goldwasser: Complexity of lattice problems: A cryptographic perspective
Websites/Lecture notes/Surveys related to lattices:
Damien Stehle's collection of lattice papers [ site ]
Oded Regev 2004 [ site ]
Vinod Vaikuntanathan 2015 [ site ] 2020 [ site ]
Daniele Micciancio 2016 [ site ]
TAU lattice course 2019 [ site ]
H. Lenstra: Lattices in number theory, algorithm, and applications [ link ]
A. Joux and J. Stern: Lattice reduction, a toolbox for cryptanalyst [ link ]
P. Q. Nguyen and J. Stern: The two faces of lattice in cryptology [ link ]
Damien Stehle's collection of lattice papers [ site ]
Oded Regev 2004 [ site ]
Vinod Vaikuntanathan 2015 [ site ] 2020 [ site ]
Daniele Micciancio 2016 [ site ]
TAU lattice course 2019 [ site ]
H. Lenstra: Lattices in number theory, algorithm, and applications [ link ]
A. Joux and J. Stern: Lattice reduction, a toolbox for cryptanalyst [ link ]
P. Q. Nguyen and J. Stern: The two faces of lattice in cryptology [ link ]
Main reference for cryptography:
A Course in Cryptography, Rafael Pass & abhi shelat
https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf
A Course in Cryptography, Rafael Pass & abhi shelat
https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf
A graduate course in applied cryptography, Dan Boneh & Victor Shoup
Foundations of Cryptography I, II, Oded Goldreich
Foundations of Cryptography I, II, Oded Goldreich
Topics:
Part 1: Introduction: Minkowski's two theorems, all what you want to know about lattices
Part 2: Algorithms for SVP and CVP: LLL and others
Part 3: Complexity: NP hardness of CVP, SVP (Ajtai, Micciancio, Khot), NP intersect coNP
Part 4: Worst-case to average-case reduction (LWE, SIS, DCP)
Part 5: The cryptographic applications of lattice problems: fully homomorphic encryptions, lattice trapdoors, identity and attribute-based encryptions.
Part 6: Quantum and lattices
Part 7: Whatever interesting, if we have time
Last two weeks: Project presentations
Part 1: Introduction: Minkowski's two theorems, all what you want to know about lattices
Part 2: Algorithms for SVP and CVP: LLL and others
Part 3: Complexity: NP hardness of CVP, SVP (Ajtai, Micciancio, Khot), NP intersect coNP
Part 4: Worst-case to average-case reduction (LWE, SIS, DCP)
Part 5: The cryptographic applications of lattice problems: fully homomorphic encryptions, lattice trapdoors, identity and attribute-based encryptions.
Part 6: Quantum and lattices
Part 7: Whatever interesting, if we have time
Last two weeks: Project presentations
Tentative Schedule:
09/19 Introduction
09/26 Minkowski's theorem, complexity of lattice problems
10/03 Holiday
10/10 SIS and LWE, q-ary lattices, and their mathematical properties
10/17 Regev's reduction from GapSVP to LWE
10/24 Public-key encryption from LWE
10/31 Fully homomorphic encryption from LWE
11/07 Lattice trapdoors, Signature
11/14 Signature, project/open problem discussion
11/21 Identity-based encryption, Bonsai technique
11/28 Pseudorandom functions from lattices
12/05 GGH15 technique and obfuscation
12/12 *Quantum and lattice: algorithms and quantum money
12/19 *Quantum and lattice: cryptographic applications, and Presentation I
12/26 Presentation II
01/02 Presentation III
09/19 Introduction
09/26 Minkowski's theorem, complexity of lattice problems
10/03 Holiday
10/10 SIS and LWE, q-ary lattices, and their mathematical properties
10/17 Regev's reduction from GapSVP to LWE
10/24 Public-key encryption from LWE
10/31 Fully homomorphic encryption from LWE
11/07 Lattice trapdoors, Signature
11/14 Signature, project/open problem discussion
11/21 Identity-based encryption, Bonsai technique
11/28 Pseudorandom functions from lattices
12/05 GGH15 technique and obfuscation
12/12 *Quantum and lattice: algorithms and quantum money
12/19 *Quantum and lattice: cryptographic applications, and Presentation I
12/26 Presentation II
01/02 Presentation III