The art of cryptography: integral lattices

Corresponding entry in Aachen Campus, Bonn University.

Lecture

Tutorial

Time & Place

Monday, 13¹⁵-14⁴⁵sharp, Hörsaal, b-it.
Thursday, 12³⁰-14⁰⁰ sharp, Hörsaal, b-it.
Tutorial: Monday, 11⁰⁰-12³⁰ sharp, Meeting room, 1.25.

Exam date: Monday 9 August 2010 at 13⁰⁰-, t.b.a. Second exam: Friday, 17 September 2010 at 13⁰⁰-, t.b.a.

After term meeting: We will meet on Monday, 9 August 2010 at 18⁰⁰
at the Rheinpavillon. All participants of the lecture are invited to join us for some apple juice!

Allocation

4+2 SWS, 8 credits. Optionally, 3+2 SWS, 6 credits.

Successful completion of the course yields 8 credit points. For students who only want 6 credit points, a breakpoint at about 3/4 of the teaching time will be defined, and only the course material up to that point will be relevant for their exams and grades.

Media Informatics: Computer and Communication Technology.
Recommendation for University of Bonn - Computer Science: A or A1, respectively.

Exam

The exam is scheduled for Monday 9 August 2010 at 13⁰⁰-, b-itmax.

Second exam: Friday, 17 September 2010 at 13⁰⁰-, b-itmax.

Lattices are of great importance in the design and the analysis of cryptographic algorithms. The most important algorithm is the so called lattice basis reduction, which was invented by Lenstra, Lenstra and Lovasz in 1982 and revolutionized computational aspects of "the geometry of numbers", leading to breakthroughs in fields like computer algebra, cryptography and algorithmic number theory.

The Ajtai-Dwork cryptosystem and NTRU are two examples of lattice-based protocols. The knapsack cryptosystem and the linear congruential pseudo-random generator were completely broken with the help of lattices. They also provide an attack on RSA when partial information about the prime factors or the exponents is known, or when one of the exponents is small.

The course will start with an introduction to lattices. After having explored the main tool of basis reduction, we will delve into the various applications.

Notes

There will be lecture notes available soon.

Exercises

Sheet 1 (PDF, last updated 20 April 2010, 15:28).
Sheet 2 (PDF, last updated 20 April 2010, 15:28).
Sheet 3 (PDF, last updated 28 April 2010, 10:57).
Sheet 4 (PDF, last updated 05 May 2010, 11:37).
Sheet 5 (PDF, last updated 11 May 2010, 17:36).
Sheet 6 (PDF, last updated 01 June 2010, 13:00).
Sheet 7 (PDF, last updated 08 June 2010, 14:43).
Sheet 8 (PDF, last updated 15 June 2010, 16:43).
Sheet 9 (PDF, last updated 15 June 2010, 16:42).
Sheet 10 (PDF, last updated 22 June 2010, 16:05).
Sheet 11 (PDF, last updated 29 June 2010, 13:27).
Sheet 12 (PDF, last updated 06 July 2010, 16:51).
Sheet 13 (PDF, last updated 13 July 2010, 13:13).

Additional files

Please note that all the following source files are not tested very well. They should serve as examples for using Shoup's number theoretic library (NTL).

An example call of the basis reduction algorithm in NTL.
An ANSI-C like implementation of the subsetsum cryptosystem using libNTL.
A C++ class Lattices that allows convenient access to several lattice-related quantities. (header, source). Note: This is in a VERY early stage of the development. No cleaning up is done so far...
An implementation of an effective version of Fermat's two squares theorem using the Lattice class.

The following files are examples for lattice related code in Matlab/MuPAD:

A Matlab/MuPAD implementation of the basis reduction algorithm (Optimized version, 22 June 2010).
An implementation of the nearest hyperplane algorithm.
The challenge of Sheet 09 to crack the digital signature algorithm. (COOL!)
The challenge of Sheet 10 to solve the Diffie-Hellman problem given a leading bit oracle. (ALSO COOL!)

Look at Chris Peikert's webpage for references to his STOC 2009 paper "Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem"!

Prerequisites

None, but a basic course on Cryptography is helpful.

Literature

The LLL Algorithm - Survey and Applications, Springer, ISBN 978-3-642-02294-4

Mailinglist

We will put each member on the mailing list . You can also subscribe yourself. The list is intented for all participants of the course as a platform for discussions around the topic. Furthermore, announcements regarding the course are made here.