Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2010 

The art of cryptography: integral lattices

Corresponding entry in Aachen Campus, Bonn University.


Prof. Joachim von zur Gathen


Daniel Loebenberger

Time & Place

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

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


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.


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

Second exam: Friday, 17 September 2010 at 1300-, 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.


There will be lecture notes available soon.


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).

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

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


None, but a basic course on Cryptography is helpful.



We will put each member on the mailing list

[Sorry, you need to enable Javascript to see this.]
. 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.

Imprint, webmaster & more