Introduction to Modern Cryptography

University of Amsterdam course, Fall 2011; part of Master of Logic
Lecturer: Christian Schaffner (UvA / CWI; email)
Teaching assistant: Joachim Schipper (IST; joachim@joachimschipper.nl)
18 March: News about the 2012 edition
5 Dec: congratulations to Lodewijk for solving the crypto challenge!

Introduction to Modern Cryptography 2012

The class will be given again in November/December 2012! All courses in the Master of Logic will switch to the new format of having 7 weeks of lectures with 2 times 2 hours of lectures plus 2 hours of exercises per week. Stay tuned for updates.

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 has been 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 the puzzle to Joachim will receive a prize.
UPDATE (Sep 19): The challenge is still on. Some hints are: use a computer, start decrypting the first large chunk of ciphertext.
UPDATE (Dec 5): Lodewijk has won the challenge. 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 cover selected material from the following book: You can order it from bol.nl 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 6 September 2011
Lectures (Hoorcollege)
Time: Tuesdays, 9-11
NEW Location: A1.08


Exercises (Werkcollege)
Time: Thursdays 11-13
first exercises: this week, 8 September 2011
NEW Location: Science Park, D1.113

Homework, exam, and grading

This is a 6 ECTS course, which comes to roughly 10 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 next lecture session. The answers should be in English. If you can, please send your solutions to Joachim (joachim@joachimschipper.nl) (LaTeX-generated PDFs preferred, but readable scans of handwritten solutions are fine). Cooperation is allowed, but everyone has to hand in their own solution set in their own words.

Instead of a final exam, students are required to study a research paper about a topic not covered in class and give a 30-minute presentation (20 minutes talk, 10 minutes questions) to the class in the week of 5 December. A list of possible topics is now online. For help in understanding the paper and preparing the presentation, students will have individual meetings with Joachim or Christian.

The final grade for the course consists by 2/3 of the average homework grade (ignoring the worst 2 grades) and 1/3 of the grade given for the final presentation.

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

Preliminary course schedule

6 Sep Overview of the course, historical crypto systems

Chapter 1 of [KL] (available online).

Homework,  Slides,  Quiz

13 Sep Perfectly-Secure Encryption, Shannon's theorem

Chapter 2 of [KL]

Homework,  Slides (including possibly useful information about probability theory)

20 Sep Computationally Secure Private-Key Encryption and Pseudorandomness

Chapters 3.1-3.4 of [KL]

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

27 Sep Pseudorandom Functions and Chosen-Plaintext Security

rest of Chapter 3 of [KL]

Homework,  Slides (encryption modes)

4 Oct Message Authentication Codes, CBC-MAC and CCA encryption

Chapters 4.1-4.5 and 4.9 of [KL]

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

11 Oct Collision-Resistant Hash Functions, Merkle-Damgaard construction, Application to MACs

rest of Chapter 4 of [KL]

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

18 Oct Practical Block Ciphers: DES and AES

Chapter 5 of [KL]

(updated) Homework,  Slides (DES, AES),  Prezi (DES, AES)

midterm break: time to relax and enjoy reading
New Directions in Cryptography by Whitfield Diffie and Martin Hellman, 1976.
1 Nov Private-Key Management and the Public-Key Revolution

Chapter 9 of [KL]

Homework,  Slides (Key Distribution Centers)

8 Nov Algorithmic Number Theory

Chapters 7 and 8 of [KL]

Homework

15 Nov Public-Key Encryption

Chapter 10 in [KL] (except of Section 10.5, El Gamal)

Homework

22 Nov Homomorphic Public-Key Encryption: El Gamal and Paillier Encryption

Sections 10.5 and 11.3 in [KL]

Homework

29 Nov Digital Signature Schemes: Definitions, RSA Full-Domain Hash, Public-Key Infrastructures

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

Homework,  Files for PGP-exercise

Tuesday, 6 Dec Student presentations (topics & schedule)
Thursday, 8 Dec Student presentations (topics & schedule). We begin at 10:30!
13 Dec No class, no exercises this week. Please hand in the homework by e-mail.
end of semester


$LastChangedDate: 2012-03-18 21:03:19 +0100 (Sun, 18 Mar 2012) $