Course Instuctor: Dr. Avijit Dutta
Reading Objective: Lattice is discrete set of points in an n-dimensional hyperplane arranged in some regular pattern. Geometrical properties of lattice makes some computational tasks a real difficult. One such fundamental problem is finding a shortest lattice point in a lattice structure. Such infeasible computational problems gives rise to one way function which is the core object of any cryptographic constructions. Based on some computationally difficult lattice problems, various cryptographic schemes have been proposed, which are easy to implement, provably secure and so far resilient to quantum attacks. In this reading course, the objective is to understand the hardness of computational lattice problems and then explore different lattice based cryptographic schemes. Our long term goal is to design some efficient lattice based cryptographic objects.
Course Contents:
- Introduction to Lattice: Definition of lattice, Unimodular matrix, Equivalence of lattice bases, Hermite Normal Form, Grahm Schmidt Orthogonalization, Fundamental Region, Fundamental Parallelepiped, Determinant of lattice, Hadamard Inequalities
- Minimum Distance of a lattice, Successive Minima, Blechfeldt Theorem, Minkowski’s Convex Body Theorem, Upper bound on the minimum distance of a lattice, Minkowski’s Second Theorem
- Computational Problems on Lattice: Shortest vector problem, Closest vector problem (search, optimization and decision version), Approximate version of shortest vector and closest vector problem, Approximate version of shortest independent vector problems, Approximate version of successive minima problem.
- Promise problems on lattice: GAPSVP_{\gamma}, GAPCVP_{\gamma}, GAPSIVP_{\gamma}, GAPSIMP_{\gamma}. Reduction of problems, Definition of NP and NP-Complete problems. Decisional CVP is NP-Complete. Proof of GAPSVP_{\gamma} <= SVP_{\gamma} and SVP_{\gamma} <= GAPSVP_{\gamma}, Proof of SVP_{\gamma} <= CVP_{\gamma}, Proof of GAPSVP_{\gamma} <= GAPCVP_{\gamma}
- Babai Nearest Plane Algorithm, Hadamard Ratio, GGH Encryption Schemes
References: I mainly follow the below mentioned resources. You can also find an ample of useful resources on lattice in the internet.
- Book: Complexity of Lattice Problems: A Cryptographic Perspective by Daniele Micciancio and Shafi Goldwasser
- Book: An Introduction to Mathematical Cryptography by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman
- Lecture Notes of Daniele Micciancio
- Lecture Notes of Chris Peikert, Survey on “A Decade of Lattice Cryptography” by Chris Peikert
- Lecture Notes of Vadim Lyubashevsky
- Lecture Notes of Oded Regev
Class Lecture Notes: Day-I, Day-II, Day-III, Day-IV.
Scribe: [Lecture Notes]