陈 一 镭 Yilei Chen
  • Main
  • Next
  • Outputs
  • Inputs
  • Life
  • Misc
    • Cryptographers seldom sleep well
    • My Favorite Open Problem
    • Random tapes
    • Superluminal fiction
    • Top 10 fake college ranking
    • Why study Chinese
  • Courses
    • Cryptography S2023
    • Lattices F2022
    • Cryptography S2022
    • Cryptography S2021

Advanced Topics in Cryptography - Lattices (Fall 2022) 


​Lattices in complexity theory, cryptography, and quantum computation.

Monday 9:50 - 12:15, 6B201
Office hour: Monday 13:30 - 14:30
Email: chenyilei@mail.tsinghua.edu.cn
TAs: Zewen Fan, Xiaxi Ye
​
Main ​reference for lattice and complexity theory:
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 ]


Main ​reference for cryptography:
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
​

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 SIS and LWE: FHE, lattice trapdoor, IBE, ABE.
Part 6: Quantum and lattices
Part 7: Whatever interesting, if we have time
Last two weeks: Project presentations


Schedule:
09/12 Moon festival
09/19 Introduction, lattice problems
09/26 Minkowski's theorems, NP hardness of CVP, SVP is no harder than CVP
10/03 National holiday, moved to 11/19
10/10 The LLL algorithm
10/17 Short integer solution and learning with errors, q-ary lattices
10/24 Regev's quantum reduction from GapSVP to LWE
10/31 Fully homomorphic encryption, gadget matrices
11/07 Lattice trapdoor and its applications to signature
11/14 Lattice trapdoor II, identity-based encryption,
11/19 The Bonsai technique, signature without random oracle (substitution for 10/03)
11/21 Attribute-based encryption, open problems
11/28 Multilinear maps from lattices, GGH15
12/05 Witness encryption and program obfuscation from lattices
12/12 Presentation I, RingSIS and RingLWE
12/19 Presentation II
12/26 Presentation III
​