Introduction to Modern Cryptography 2012

University of Amsterdam course, Fall 2012
part of Master of Logic
Lecturer: Christian Schaffner (UvA / CWI; email)
Teaching assistant: Maria Velema (mariavelema@gmail.com)
30 Dec: Malvin (and two of his friends) solved the crypto challenge and won the price! Congratulations!
19 Dec: The final presentations and the course are over! You will hear from us about your grades soon. Check out the section about "life after Intro to Modern Crypto" below.
16 Dec: The pigeon-challenge has apparantly been solved! The crypto challenge of this course is still open. You have time until the end of January 2013 to claim the price!
21 Nov: werkcolleges on Wednesday will now be from 11-13 instead of 9-11
19 Nov: topics and procedure for final exam online
15 Nov: see here for an advertisement for Mark Steven's Master student project
13 Nov: second hint for crypto challenge released (see below)
7 Nov: where to hand in your exercises
6 Nov: Hint for crypto challenge released: "Many-Time Pad"
30 October: crypto challenge online
See here for the 2011 edition of this course

Life after "Introduction to Modern Cryptography"

If you got hooked on the world of Alice, Bob and Eve, you have several options after the course:

Crypto challenge

At the end of the first lecture, a crypto challenge will be handed out to all students attending. You have to be on the student list in order to win the price, but feel free to try anyway. The first person emailing the correct solution to Christian will receive a prize. On Nov 8, a first hint was released: "Many-Time Pad". On Nov 13, the scheme was revealed. The eleven ciphertexts are one-time pad encryptions where the same one-time pad was re-used. In other words, for every \(j \in \{1,\ldots,11\}\), we have that \(c_j = r \oplus m_j\), where \(m_j\) is the \(j\)-th plaintext, \(c_j\) is the \(j\)-th ciphertext and \(\oplus\) is the bit-wise XOR function. On Dec 30, Malvin was the first to submit the correct solution and win the price, congratulations!

Contents of the course

Cryptography has a very long and exciting history. For centuries, political leaders and military forces have used cryptographic techniques, primarily to communicate securely. Modern cryptography is concerned with an enormous variety of scenarios where the involved parties do not fully trust each other such as internet banking, electronic voting, integrity of data, security of computer networks and many more.

This course offers an introduction to this fascinating subject. After a quick treatment of historic cryptographic schemes, we will set out the formal definitions to be able to investigate perfectly-secret and computationally-secure encryption, pseudorandomness, hash functions, and message authentication codes and block ciphers. While these primitives are referred to as symmetric-key primitives (because the involved parties use the same keys), another important class are public-key (or asymmetric) primitives which allow for public-key encryption and digital signatures. The most well-known example is the widely-used RSA system.

If time allows, we will cover more advanced cryptographic notions such as secret sharing, bit commitment, zero-knowledge and multi-party computation.

Over the last years, cryptography has been transformed from an ad-hoc collection of mysterious tricks into a rigorous science based on firm mathematical grounds. Our treatment will therefore be rather formal and precise in the mathematical definitions. In particular, this is NOT a course in computer security. You will not learn how to break or hack systems. We will not teach you "how to secure your system"; cryptography is only one aspect of security.

Prerequisites

Ability to understand and write formal mathematical definitions and proofs, familiarity with the basics of probability theory (independence, conditional probabilities, expectation, Bayes' Law), and basic number theory (modular arithmetic). It's helpful but not necessary to have some familiarity with the Chinese Remainder Theorem, algorithms (analyzing running time) and complexity theory (NP-completeness, reductions).

Material

We will mainly follow the following book: You can order it from bol.com or amazon.co.uk for approximately 50 EUR. The authors' web site has some minor errata and samples.

There will be material and research articles to read which are not in the book. Here is a useful list of other text books and references by Jon Katz.

Lectures and Exercise sessions (2 x 45min each)

starting 30 October 2012
Lectures (Hoorcollege)
Times: Tuesdays, 11-13, location: Science Park B0.208
Thursdays, 11-13, location: mostly Science Park B0.207
please check Datanose for the definite locations.

Exercises (Werkcollege)
Time: Wednesdays 11-13, location: Science Park, B0.207
first exercises: 31 October 2012

Homework, exam, and grading

This is a 6 ECTS course, which comes to roughly 20 hours of work per week.

There will be homework exercises every week, handed out after the Tuesday lecture, to be handed in one week later before the start of the exercise session on Wednesday. The answers should be in English (feel free to use LaTeX, but readable handwritten solutions are fine). Cooperation while solving the exercises is allowed and encouraged, but everyone has to hand in their own solution set in their own words. Exercises can be handed over to Maria at the werkcollege on Wednesday or should be put in Christian Schaffner's mailbox at the ILLC on Wednesdays before 10:55.

There will be a final written exam on Wednesday, December 19, 2012 from 13:00 - 16:00, probably in Science Park, B0.208. The final exam will consist of student presentations about slightly more advanced cryptologic topics. The detailed procedure and list of topics can be found here.

The final grade for the course consists by 1/2 of the average homework grade (ignoring the worst grade) and 1/2 of the grade obtained at the final exam.

Questions about the material are always welcome, and should be sent to Maria.

Preliminary course schedule 2012

Tue, 30 Oct Overview of the course, historical crypto systems

Chapter 1 of [KL] (available online).

Homework #1,   Slides,  Quiz

Thu, 1 Nov Perfectly-Secure Encryption, Shannon's theorem

Chapter 2 of [KL]

Slides (including possibly useful information about probability theory)

Tue, 6 Nov Computationally Secure Private-Key Encryption and Pseudorandomness

Chapters 3.1-3.4 of [KL]

Homework #2,   Slides (including possibly useful information about poly-time Turing machines)

Thu, 8 Nov Pseudorandom Functions and Chosen-Plaintext Security

rest of Chapter 3 of [KL]

Slides (encryption modes)

Tue, 13 Nov Message Authentication Codes, CBC-MAC and CCA encryption

Chapters 4.1-4.5 and 4.9 of [KL]

Homework #3,   Slides (CBC encryption vs CBC-MAC, CCA security)

Thu, 15 Nov Collision-Resistant Hash Functions, Merkle-Damgaard construction, Application to MACs

rest of Chapter 4 of [KL]

Slides (Merkle-Damgaard, SHA-256, NMAC, HMAC)

Tue, 20 Nov Practical Block Ciphers: DES and AES

Chapter 5 of [KL]

Homework #4,  Slides (DES, AES),   Prezi (DES, AES)

Thu, 22 Nov Private-Key Management and the Public-Key Revolution

Chapter 9 of [KL]

Slides (Key Distribution Centers)

A good read: New Directions in Cryptography by Whitfield Diffie and Martin Hellman, 1976.

Tue, 27 Nov Algorithmic Number Theory

Chapters 7 and 8 of [KL]

Homework #5,   Slides

Thu, 29 Nov Discrete Logarithms, Public-Key Encryption

Chapter 10 in [KL] (Sections 10.1 to 10.3)

Tue, 4 Dec Public-Key Encryption: RSA and El Gamal Encryption

Sections 10.4, 10.5

Homework #6,   PubK cca

Thu, 6 Dec Homomorphic Public-Key Encryption: Paillier Encryption

Section 11.3 in [KL]

Tue, 11 Dec Digital Signature Schemes: Definitions, RSA Full-Domain Hash, Public-Key Infrastructures

Sections 12.1-12.3, 13.3, 12.8 in [KL]

Thu, 13 Dec free for preparations of presentations
Wed, 19 Dec
13:00 - 16:00
Exam: Student Presentations
end of semester