The art of cryptography: lattices and cryptography

This course is listed in Aachen Campus as The art of cryptography: lattices and cryptography and in Bonn Basis as MA-INF 1312 The art of cryptography: lattices and cryptography.

Lecture

Prof. Dr. Joachim von zur Gathen

Tutorial

Dr. Daniel Loebenberger

Time & Place

Monday, 13⁰⁰-14³⁰, b-it 1.25.
Thursday, 13⁰⁰-14³⁰, b-it 1.25.
Tutorial: Monday, 14⁴⁵-16¹⁵, b-it 1.25.

First meeting: Thursday, 11 April 2013.

Mailinglist

This lecture's mailing list can be reached under

Additional information will be posted there and students are encouraged to ask and answer any questions related to the course. Information on how to subscribe and unsubscribe can be found on the list's Info page.

Exam

Exam: 19 July 2013, 11:00, b-it

2nd Exam: 28 August 2013, 11:00, b-it

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.

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.

Slides

Introduction and subset sums (PDF, last updated 17 April 2013, 14:25).
Truncated linear congruential generators (PDF, last updated 25 April 2013, 07:48).
Close vectors (PDF, last updated 30 April 2013, 13:43).
The basis reduction algorithm (PDF, last updated 07 May 2013, 11:32).
Cost estimates for basis reduction (PDF, last updated 14 May 2013, 10:53).
The hidden number problem (PDF, last updated 28 May 2013, 10:52).
Security of Diffie-Hellman bits (PDF, last updated 04 June 2013, 10:11).
The Coppersmith method (PDF, last updated 10 June 2013, 10:51).
Security of leading bits of an RSA prime (PDF, last updated 11 June 2013, 12:43).
Security of a secret CRT-RSA exponent (PDF, last updated 16 June 2013, 08:39).
Learning with errors and the Peikert cryptosystem (PDF, last updated 11 July 2013, 14:05).

Exercises

Exercise 1 (PDF, last updated 16 April 2013, 09:24).
Exercise 2 (PDF, last updated 23 April 2013, 08:18).
Exercise 3 (PDF, last updated 29 April 2013, 12:08).
Exercise 4 (PDF, last updated 05 May 2013, 12:04).
Exercise 5 (PDF, last updated 14 May 2013, 10:53).
Exercise 6 (PDF, last updated 28 May 2013, 10:50).
Exercise 7 (PDF, last updated 04 June 2013, 10:37).
Exercise 8 (PDF, last updated 11 June 2013, 12:42).
Exercise 9 (PDF, last updated 18 June 2013, 06:54).
Exercise 10 (PDF, last updated 25 June 2013, 11:54).
Exercise 11 (PDF, last updated 02 July 2013, 14:13).
Exercise 12 (PDF, last updated 11 July 2013, 13:35).

Additional files

Exercise 1: NTL example (cpp).
Exercise 6: A DSA challenge (txt).
Exercise 7: A Diffie-Hellman challenge (txt).

Prerequisites

Basic knowledge in cryptography is needed, as for example the course Cryptography held in the previous winter. Compare our programme.