Introduction to Modern Cryptography 2014
part of Master of Logic
Teaching assistant: Malvin Gattinger (malvin@w4eg.de)
News:
3 Nov 2014: The challenge has been solved!29 Oct 2014: revealed the prize for the challenge
24 Oct 2014: added a second hint for the challenge
16 Oct 2014: updated homework template to include a experiment description
9 Oct 2014: the room for Marc's guest lecture about bitcoin is: CWI L0.17.
Please be at 10:50 at the reception inside the main entrance of CWI
8 Oct 2014: assigned exam topics. Detailed schedule coming soon.
6 Oct 2014: added a hint for the challenge
5 Oct 2014: added details and list of topics about final presentations
5 Sept 2014: updated homework template to include encryption schemes
3 Sept 2014: announced challenge, how to submit homework
31 Aug 2014: register for RISC seminar
28 Aug 2014: added preliminary schedule
24 July 2014: added Malvin as TA
9 April 2014: first website update
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.
Intended learning outcomes
At the end of the course, you will be able to:- distinguish modern-day cryptography from ancient cryptography
- compare different security notions for private- and public-key encryption
- apply security notions for private- and public-key authentication
- produce/carry out cryptographic security proofs by reduction
- recognize the discrepancy between theoretically secure and practically used cryptography
- recognize and explain aspects of number theory which are relevant to cryptography
- combine number theory and cryptography
- select, summarize and defend a research topic in cryptography
- relate and compare that research topic with material in the course
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:- [KL] Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, Chapman & Hall / CRC, 2008
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.
Location
please check Datanose for the definite locations.
starting 1 September 2014Lectures (Hoorcollege)
Times: Mondays, 11-13, location: Science Park A1.06
Times: Thursdays, 9-11, location: Science Park A1.20
Exercises (Werkcollege)
Time: Thursdays 11-13, location: Science Park, A1.20
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 (and put online) after the Monday lecture, to be handed in one week later before the start of the lecture on Monday. Please note that also if you send the homework via email the same deadline applies. Our goal is to hand you back the corrected exercises in the exercise hour on the following Thursday. The answers should be in English. Feel free to use LaTeX, here is a template to get you started, but readable handwritten solutions are fine, too. Cooperation while solving the exercises is allowed and encouraged, but everyone has to hand in their own solution set in their own words.
The final exam consists of student presentations about slightly more advanced cryptologic topcis. 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 can be addresse to Christian or Malvin.
Crypto challenge
At the end of the second lecture, this crypto challenge was handed out.
On Sun, 2 November, Eli has won the challenge! Congratulations!
Course schedule 2014
Date | Content | Homework | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Mon, 1 Sep |
Overview of the course, historical crypto systems Chapters 1.1-1.3 of [KL] |
Homework #1 | ||||||||||||||||
Thu, 5 Sep |
The lecture from 9:00-11:00 is not taking place, as Christian is in Paris. Instead, the students are required to watch the 5 introductory lectures from Dan Boneh's online crypto course:
[In order to be able to watch the videos, you have to "enroll" in the 'Cryptography I' class on coursera. However, it's all free and only requires you to create an account using a valid email address. In case you have any difficulties accessing the videos, please ask Malvin for assistance.] The first two videos give a short overview of the fascinating field of cryptography. The third is a recap of some historic schemes, similar to those seen in the first lecture on Monday. The last two give a crash course on discrete probability as we will need it in the course. Check out this wikibook for a quick summary of discrete probability theory. The exercise session from 11:00-13:00 is taking place as scheduled. Malvin will be there to work through some exercises related to the watched videos, and answer all your burning questions. |
Class Exercises #1 | ||||||||||||||||
Mon, 8 Sep |
Perfectly-Secure Encryption, Shannon's theorem Chapter 1.4 & Chapter 2 of [KL] Slides #2 (including possibly useful information about probability theory) |
Homework #2 | ||||||||||||||||
Thu, 11 Sep |
Computationally Secure Private-Key Encryption and Pseudorandomness Chapters 3.1-3.4 of [KL] As preparation for this lecture, you should know what a Turing-machine is, and familiarize yourself with the notion of probabilistic polynomial time computation (read Section 3.1.2 of [KL]). |
Class Exercises #2 | ||||||||||||||||
Mon, 15 Sep |
Pseudorandom Functions and Chosen-Plaintext Security rest of Chapter 3 of [KL] |
Homework #3 |
||||||||||||||||
Thu, 18 Sep |
Message Authentication Codes, CBC-MAC and CCA encryption Chapters 4.1-4.5 and 4.9 of [KL] |
|||||||||||||||||
Mon, 22 Sep |
Collision-Resistant Hash Functions, Merkle-Damgaard construction, Application to MACs rest of Chapter 4 of [KL] |
Homework #4 | ||||||||||||||||
Thu, 25 Sep |
Practical Block Ciphers: DES and AES Chapter 5 of [KL] This will be a flipped-classroom lecture, meaning that you have to watch the following videos before the lecture:
The according slides are available in powerpoint and PDF format. It is a mandatory part of Homework #4 to watch these lectures and submit two types of questions before Wednesday, 24 September 2014, 14:00. |
Flipped-Classroom Exercises Class Exercises #4 OpenSSL examples: OFB vs. CBC |
||||||||||||||||
Mon, 29 Sep |
Private-Key Management and the Public-Key Revolution, Discrete Logarithms, CDH, DDH Chapter 9 of [KL] Slides (Key Distribution Centers) A good read: New Directions in Cryptography by Whitfield Diffie and Martin Hellman, 1976. |
Homework #5 | ||||||||||||||||
Thu, 2 Oct |
Public-Key Encryption, Elgamal encryption Chapter 10 in [KL] (Sections 10.1 to 10.3, 10.5) |
Class Exercises #5 | ||||||||||||||||
Mon, 6 Oct |
Public-Key Encryption: RSA Encryption, CCA Security Sections 10.4 |
Homework #6 | ||||||||||||||||
Thu, 9 Oct |
Digital Signature Schemes: Definitions, RSA Full-Domain Hash Sections 12.1-12.3, 13.3 in [KL] |
Class Exercises #6 | ||||||||||||||||
Mon, 13 Oct | Guest lecture by Marc Stevens about
Bitcoin
Location: L0.17, ground floor of the new wing of CWI Marc's slides Marc's notes Research Paper: The Bitcoin Backbone Protocol: Analysis and Applications |
Homework #7 | ||||||||||||||||
Thu, 16 Oct | There is no lecture today. The time will be used for talking about final presentations.
Please select one of the time slots here and come to Chris' office (SP107, F2.41) at the time you picked. The last exercise session will take place (at SP904, A1.20) but start 10 minutes late. |
|||||||||||||||||
Mon, 20 Oct | Presentations:
|
|||||||||||||||||
Wed, 22 Oct | Presentations:
|
|||||||||||||||||
Fri, 24 Oct | Presentations:
|
|||||||||||||||||
Wed, 29 Oct |
Deadline for the last homework: 14:00, If you are not handing in via email, please bring your homework to Malvin at F2.26 in SP107. |
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:- Talk to Christian about the possibilities of doing a semester project or master project in cryptography. He can also hook you up with other cryptographers, at CWI or in the rest of the Netherlands (and the world), working in all kind of different areas (crypto & algebraic geometry, elliptic curves, public-key crypto, information-security aspects etc.).
- Follow Ronald de Wolf's course about quantum computing at the university of Amsterdam, starting Spring 2015.
- Follow this mastermath course about crypology by Marc Stevens and Tanja Lange, starting in Spring 2015.
- Follow various excellent online classes such as Dan Boneh's crypto, crypto II, Jon Katz's crypto class or Umesh Vazirani's course about quantum computing.
- Join a Privacy Cafe in order to get your computer hardware up to speed. On 7 November 2014, there will be Privacy Cafe in the Brainwave bar at the Science Park.