The art of cryptography: Heads and tails - Cryptographic random generation

This course is listed in Aachen Campus as "The art of cryptography" and in Bonn Basis as "The art of cryptography".

Lecture

Prof. Dr. Joachim von zur Gathen
Dr. Daniel Loebenberger

Tutorial

Dr. Daniel Loebenberger

Time & Place

Monday, 13⁰⁰-14³⁰, B-IT, 2.1

Thursday, 12⁴⁵-14¹⁵, B-IT, 2.1

Tutorial: Monday, 14⁴⁵-16¹⁵, B-IT, 2.1

First meeting: Thursday, 09 April 2015.

Exam

Exam: 23 July 2015, 13⁰⁰ - 16⁰⁰, b-it, Rheinsaal

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.

Randomness has become an important tool in the design of efficient algorithms. But what is a random bit? 0? 1? The necessary quality of randomness depends on the application: In cryptography such bits have to satisfy more requirements than when they are used for Monte-Carlo simulations in particle physics (from where their computational use originated). Cryptographic protocols require random help, and their security depends on the quality of the randomness used.

In the course we will discuss various aspects of randomness used for algorithmic purposes. Here are some examples:

Sources of true randomness: Rolling dice by computer (and playing poker).
Extending a small amount of true randomness to a huge amount of pseudorandomne
ss; the latter is just as good for computational purposes.
Distilling excellent randomness out of a miserable source of randomness: turning a loaded die into an (almost) fair one.
Finger-printing huge databases, congestion-avoiding routing in networks
Testing integers for primality.

Slides

Introduction (PDF, last updated 14 April 2015, 08:12).
True random generators (PDF, last updated 14 April 2015, 08:12).
pseudorandom generators (PDF, last updated 21 April 2015, 12:05).
Distinguishers (PDF, last updated 28 April 2015, 12:08).
Predictors (PDF, last updated 28 April 2015, 12:08).
From short to long generators (PDF, last updated 05 May 2015, 12:25).
The Nisan Wigderson generator (PDF, last updated 18 May 2015, 12:12).
The Blum Blum Shub generator (PDF, last updated 02 June 2015, 14:12).

Exercises

Exercise 1 (PDF, last updated 14 April 2015, 08:12).
Exercise 2 (PDF, last updated 21 April 2015, 12:05).
Exercise 3 (PDF, last updated 28 April 2015, 19:42).
Exercise 4 (PDF, last updated 10 May 2015, 09:26).
Exercise 5 (PDF, last updated 11 May 2015, 14:35).
Exercise 6 (PDF, last updated 19 May 2015, 15:54).
Exercise 7 (PDF, last updated 02 June 2015, 14:13).
Exercise 8 (PDF, last updated 08 June 2015, 15:31).
Exercise 9 (PDF, last updated 22 June 2015, 11:12).
Exercise 10 (PDF, last updated 23 June 2015, 12:06).
Exercise 11 (PDF, last updated 30 June 2015, 12:24).
Exercise 12 (PDF, last updated 08 July 2015, 12:26).

Additional files

Exercise 1.1: NIST Special Publication 800-90A (pdf)
Exercise 1.2: Plain output (rnd ), AES postprocessed output (rnd)
Exercise 1.2: AIS31 (pdf)

Prerequisites

Basic knowledge in cryptography is needed, as for example the course Cryptography held in the previous winter. However, participation does not mandatorily require participation in the aforementioned course.

Allocation

4+2 SWS.

Master in Media Informatics: Computer and Communication Technology.
8 ECTS credits.
Master in Computer Science at University of Bonn: MA-INF 1312.
9 CP.
Students have to register this course with POS/BASIS.
Recommendation for diploma students of University of Bonn - Computer Science: A or A1, respectively.