Prospectus

nl en

Lattices and Their Algorithms

Course
2023-2024

Admission requirements

Linear algebra, (abelian) groups, rings, fields, comparable to the courses Lineaire Algebra 1 and 2 and Algebra 1 and 2 of the Leiden Bachelor Wiskunde. See the lecture notes at
https://websites.math.leidenuniv.nl/algebra/
Algorithms in Algebra from the first semester (by Streng and de Boer)

Recommended:
Some course on Algebraic Number Theory (e.g. Dirichlet Unit Theorem and Class Groups will be considered for about two lectures).

Description

This course will propose to study euclidean lattices (discrete subgroups of the Euclidean vector space Rn) and related questions arising in various areas of mathematics and computer science (Geometry of Numbers, Algebraic Number Theory, Coding Theory, Cryptography). What are the densest sphere packings, and how to find them? Are two given lattice similar? How to compute the class-group of a Number Field? How to use lattices to communicate reliably over a noisy analog channel? Or how to use them to encrypt a message only decipherable by the secret-key holder? What is Fully-Homomorphic Encryption, and why should I care?
This course is intended to give a peak at various research and application areas where lattices are used, while providing a solid background on these mathematical objects. It is aimed at MSc students.
Topics include:

  • Algorithms and Complexity

  • Sphere Packing

  • Fourier Analysis

  • Index Calculus

  • Coding, cryptography and Cryptanalysis

Course objectives

Students understand the fundamental properties of lattices, and key algorithms for them. Students get a preview of various research and application areas, including post-quantum and public-key cryptography.

Timetable

The schedule for the course can be found on MyTimeTable.

You will find the timetables for all courses and degree programmes of Leiden University in the tool MyTimetable (login). Any teaching activities that you have sucessfully registered for in MyStudyMap will automatically be displayed in MyTimeTable. Any timetables that you add manually, will be saved and automatically displayed the next time you sign in.

MyTimetable allows you to integrate your timetable with your calendar apps such as Outlook, Google Calendar, Apple Calendar and other calendar apps on your smartphone. Any timetable changes will be automatically synced with your calendar. If you wish, you can also receive an email notification of the change. You can turn notifications on in ‘Settings’ (after login).

For more information, watch the video or go the the 'help-page' in MyTimetable. Please note: Joint Degree students Leiden/Delft have to merge their two different

Mode of instruction

Lecture, problem class, self-study, computer class, about two homework assignments that count for a grade.

Assessment method

The final grade consists of practical assignments (20%), a participation grade (10%) and a written (retake) exam (70%). To pass the course, the (unrounded) grade for the final exam should be at least 5 and the (unrounded) weighted average of the three partial grades at least 5.5. No minimum grade is required for the homework in order to take the exam or to pass the course. The homework counts as a practical and there is no retake for it.

Reading list

Various related courses can be found online, the closest in topics and spirit might be the two followings:

  • Daniel Dadush & Leo Ducas on “Intro to Lattices, Algorithms and Cryptography “ https://homepages.cwi.nl/~dadush/teaching/lattices-2018/

  • Daniele Micciancio's course on "Lattice Algorithms and Applications": link

More specialized courses and books on cryptographic applications and complexity theory include:
Oded Regev's course on "Lattices in Computer Science": link.
Chris Peikert's course on "Lattices in Cryptography": link
Vinod Vaikuntanathan's course on "Lattices in Cryptography": link
Daniele Micciancio and Shafi Goldwasser: “Complexity of Lattice Problems: A Cryptographic Perspective “ https://cseweb.ucsd.edu/~daniele/papers/book.html

A fraction of this course will cover Voronoi’s algorithm for Perfect Quadratic Form Enumeration, which is beautifully exposed in the book of Achill Schurmann “Computational Geometry of Positive Definite Quadratic Forms” https://bookstore.ams.org/ulect-48/
For the required background on Algebraic Number Theory, in particular to students not having followed such a course, Pierre Samuel’s book “Algebraic theory of Numbers” is warmly recommended. https://www.maa.org/press/maa-reviews/algebraic-theory-of-numbers

Registration

From the academic year 2022-2023 on every student has to register for courses with the new enrollment tool MyStudyMap. There are two registration periods per year: registration for the fall semester opens in July and registration for the spring semester opens in December. Please see this page for more information.

Please note that it is compulsory to both preregister and confirm your participation for every exam and retake. Not being registered for a course means that you are not allowed to participate in the final exam of the course. Confirming your exam participation is possible until ten days before the exam.
Extensive FAQ's on MyStudymap can be found here.

Contact

See the lecturer information on https://homepages.cwi.nl/~ducas/.

Remarks