## Advanced Topics in Cryptography - Lattices (Fall 2024)

Lattices in complexity theory, cryptography, and quantum computation.

Friday 9:50 - 12:15, 6B112

Office hour: Friday 13:30-14:30 in my office

Office hour: Friday 13:30-14:30 in my office

Email: [email protected]

TAs: Mengda Bi, Wenjie Li

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/13 Introduction

09/20 Complexity of lattice problems

09/27 Minkowski's theorems, SIS and LWE, q-ary lattices

10/11 Regev's quantum reduction from GapSVP to LWE

10/18 Relationship between SIS and LWE, lattice trapdoors

10/25 PKE and FHE from LWE

11/01 FHE bootstrapping, lattice trapdoors

11/08 Signature, project/open problem discussion

11/15 Identity-based encryption, Bonsai technique

11/22 GGH15 technique and witness encryption

11/29 Lattice and quantum: CLZ22 and AG11

12/06 Quantum and lattice: Liu's quantum curvelet transform algorithm

12/13 Presentation I

12/20 Presentation II

12/27 Presentation III

09/13 Introduction

09/20 Complexity of lattice problems

09/27 Minkowski's theorems, SIS and LWE, q-ary lattices

10/11 Regev's quantum reduction from GapSVP to LWE

10/18 Relationship between SIS and LWE, lattice trapdoors

10/25 PKE and FHE from LWE

11/01 FHE bootstrapping, lattice trapdoors

11/08 Signature, project/open problem discussion

11/15 Identity-based encryption, Bonsai technique

11/22 GGH15 technique and witness encryption

11/29 Lattice and quantum: CLZ22 and AG11

12/06 Quantum and lattice: Liu's quantum curvelet transform algorithm

12/13 Presentation I

12/20 Presentation II

12/27 Presentation III