A quick introduction to Lattice Cryptography

Here is a short video explaining the basic principles of lattice-based cryptography. This provides the general landscape without going into the details of reductions, nor security proofs. Some aspects like discrete Gaussian distributions, dual lattices, or lattice geometry that are primary in lattice cryptography are not covered.

The animations are done with the manim Python library developed by Grant Sanderson, owner of the 3Blue1Brown Youtube channel, and many other contributors. This video was submitted to the Summer Of Math Exposition 1 in July 2021, organized to encourage math explainers online.

References

[Ajtai96] M. Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1–32. Dept. Math., Seconda Univ. Napoli, Caserta, 2004. Preliminary version in STOC 1996.

[GPV08] C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 197–206. ACM, 2008.

[Regev05] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84–93, 2005.