Lattice Based Cryptography

This is a module on lattice-based cryptography. The pre-requisites are elementary linear algebra: vector spaces, matrices, linear maps, etc … Acknowledgment: we are grateful to Shi Bai for all the help with the planning and design of this module. 

Linear Algebra Recap

Lecture One

Learning Objectives:

a) The students will be able to perform arithmetic operations on matrices.

b) The students will be able to compute determinants with cofactors.

c) The students will be able to invert matrices with cofactors.

d) The students will be able to use matrices to change the basis of a vector space.

e) The students will be able to use matrices to evaluate linear maps

Lecture Notes PDF

The LWE Problem

LectureTwo

Learning Objectives:

a) The students will be able to perform Gaussian elimination.

b) The students will be able to produce instances of the LWE problem.

c) The students will be able to sample according to the rounded Gaussian distribution.

d) The students will be able to use an encryption scheme based on LWE.

Lecture Notes PDF

The Gram-Schmidt Orthogonolization

Lecture Three

Learning Objectives:

a) The students will be able to recognize an inner product.

b) The students will be able to evaluate projection maps from an orthonormal basis.

c) The students will be able to compute an orthonormal basis of a vector space.

Lecture Notes PDF

Euclidean Lattices

Lecture Four

Learning Objectives

a) The students will be able to compute lattice points from the matrix of a basis of a lattice.

b) The students will be able to compute the volume of a lattice.

c) The students will be able to derive an upper bound on the minimum distance of a lattice.

d) The students will be able to prove Minkovski's convex body theorem.

Lecture Notes PDF

Modular Polynomials

Lecture Five

Learning Objectives:

a)The students will know how to perform arithmetic operations on polynomials over any ring.

b) The students will know how to perform polynomial divisions.

c) The students will know how to use circulant matrices to reduce modular arithmetic to matrix operations.

Lecture Notes PDF

A KEM based on Module-LWE

Lecture Six

Learning Objectives:

a) The students will know how to produce instances of the Module LWE problem.

b) The students will know how to solve LWE using a lattice technique.

c) The students will know how to reduce the resolution of Module LWE to the resolution of LWE.

d) The students will know how to use an encryption scheme based on Module-LWE

e) The students will know how to turn a public key encryption scheme into a KEM.

Lecture Notes PDF