Latest News

• The backup exam will take place on Tuesday, October 16, 2007, from 11:00 to 13:00 in HS 002, E1.3.
• The exam inspection will take place on Friday, July 20, from 11:00 to 13:00, in Room U12, E1.1.
• Assignment for the final exam: Friday, July 13, 2007, 14:00 - 16:00 s.t. (!)
  

  Family Name	Room (all in building E1.3)
  A - P	HS 002
  R - Z	HS 003

• List of participants for the final exam.
• There will be no lecture on Tuesday, June 19, but lecture notes and homework exercises will be available online, and there will be quizzes on wednesday.
• Don't forget to register  in the HISPOS system before June, 22. Registering is necessary for grading your course.
• Assignment for the midterm-exam: Friday, May 25, 2007, 14:00 - 15:00 s.t. (!)
  
  

  Family Names	Room (all in building E1.3)
  A - Kro	HS 002
  Kün - Ran	HS 001
  Rei - Z	HS 003

• Registration is closed.
• The assignment for the tutorials is online. If there are problems with it, write us an email, or contact the tutor of the tutorial you wish to join.
• The discussion board is now available.
• Office hours are fixed now, see below.
• An information sheet is available.
• Registration is open until Friday, May 4. For deregistration, send us an email before Friday, May 11.
• The slides of the lecture can be downloaded here. Registered course participants will receive the login data in a separate mail in the first week of the course. In case you are registered but did not get such a mail, either ask one of your colleagues for the login data, or come to our offices.

Description

This course is an introduction to Modern Cryptography. It will introduce cryptography from scratch, i.e., no previous knowledge in cryptography or computer security is required. The list of topics comprises:

• Information-theoretic security and the One-time Pad
• Symmetric encryption, stream ciphers, block ciphers, Data Encryption Standard (DES), Advanced Encryption Standard (AES)
• Asymmetric encryption, cryptosystems based on RSA and on the discrete logarithm problem, Cramer-Shoup encryption
• Digital signature schemes
• Cryptographic hash functions
• Selected cryptographic protocols and their security
• Crypto in the "real world"
• Basic concepts of advanced cryptographic primitives and current research topics: Bit commitment, zero-knowledge proofs, simulatability, linking formal verification and cryptography

Most of these topics are covered by the following books, both are available in the computer science or math library (The terminology of the course will be closer to Stinson's, thus making this book the better choice if you intend to buy a new one).

• Douglas R. Stinson: Cryptography: Theory and Practice. CRC Press, 2005
• Nigel Smart: Cryptography: An introduction, McGraw-Hill, 2003

Prerequisites

This course is a core theory lecture. Basic knowledge in computability, complexity theory, and number theory is useful, but not utterly necessary, as it can be acquired during the course.

Tutorials

The following times for tutorials are available:  

• Wednesday, 2:00 pm - 4:00 pm
  • U12 (Building E1.1): Oana Ciobotaru
  • SR015 (Building E1.3): Marek Hamerlik
  • SR016 (Building E1.3): Kim Pecina
• Wednesday, 4:00 pm - 6:00 pm
  • U12 (Building E1.1): Esfandiar Mohammadi
  • SR013 (Building E1.3): Frank Steinbrücker
  • SR014 (Building E1.3): Matthias Berg

Why are all tutorials at the same day? See the section on quizzes below.

Michael Backes will be available for your questions on Friday, 2:00pm - 3:00pm in building E1.1, room U15.

Markus Dürmuth will be available for your questions on Tuesday, 2:00pm - 3:00pm, in building E1.1, room U13.

The tutors will be available for your questions at the following times in building E1.1, room U18:

• Tuesday: 9:00 am - 11:00 am
• Wednesday: 11:00 am - 1:00 pm
• Friday: 2:00 pm - 4:00 pm

Homeworks

Weekly homework exercises will be handed out in class and posted to the course page each Tuesday, starting in the second week. Their solutions will be posted one week later. No homeworks have to be submitted, but you are encouraged to ask any question you might have concerning the course in the office hours. Homework exercises will thus not influence your grade, however, by presenting solutions in the tutorials you may gain a better grading in the quiz, see below.

Weekly Quiz

Each tutorial starts with a short (approx. 15 minutes) quiz covering the topics of the same two lectures that were addressed in the last homework exercise. Your overall quiz-grade is determined by dropping the quiz with the lowest grading, and calculating the average of the remaining quizzes.

You can further improve your quiz-grade by presenting solutions of the homework exercises in the tutorials. For each correct solution you presented you may drop one additional quiz, up to a maximum of two additional quizzes, i.e., at most three quizzes may be dropped. Please be aware that there is a limited number of exercises, and if more than one student opts for one particular solution, a random student will be drawn. So start early enough!

Quizzes will affect your final grading by 30%, and you need an overall quiz-grading of at least 50% to pass the course.

Exams

There will be two mandatory exams: A mid-term exam on Friday, May 25, 2007, and a final exam on Friday, July 13, 2007.

The mid-term exam will be approx. one hour and consist of multiple-choice and simple questions intended to test your basic understanding of the course material covered so far. Your mid-term grade will affect your final grading by 20%, however, there is no lower bound that has to be reached in order to pass the course.

The final exam will be a written test of two hours. It will make up 50% of your final grade, you need at least 50% to pass the course.

Grading & Requirements for Passing the Course

Let Q be your quiz score, M your score in the mid-term exam, and E your score in the final exam, each in percent. Then your final overall score Final is calculated as
you pass the course if


Q: I got only 49% in the quizzes, but 100% in both exams, will I pass?
A: No, you need 50% in your quizzes to pass.

Q: I got only 49% in the final exam, but 100% in the quizzes and the mid-term exam, will I pass?
A: No, you need 50% in your final exam to pass.

Q: I got only 30% in the mid-term exam, but 100% in final exam and in the quizzes, will I pass?
A: Yes, there is no minimum requirement on the mid-term exam. However, of course, you need a final score of 50% to pass.

Backup Exams

Date and time of the backup exam will be announced later. You may take part in the backup exam if you qualified for the final exam, i.e., you got at least 50% score in the quizzes, and failed the final exam.

The backup exam will be oral or written, depending on the preference of every individual student (but necessarily written for everybody if too many opt for an oral exam).

Lecture Overview & Material

Date	Topics	Lecture Notes	Homework	References
Fri 04/20/2007	Organizatorial aspects. Historical overview of cryptography. Information theoretic security. Perfect secrecy. One-time pad.			Stinson p.1-13, 25-34, 45-54
Tue 04/24/2007	Optimality of the One-time Pad. Attacks against the One-time Pad. Stream ciphers.		solution:	Stinson p. 45-54, 21-24
Fri 04/27/2007	Idea of Block Ciphers. DES (Data Encryption Standard). AES (Advanced Encryption Standard)	.		Stinson p. 73-79, 95-108
Tue 05/01/2007	(public holiday)		solution:
Fri 05/04/2007	Variants of DES. Various attacks against block ciphers. Modes of operation for block ciphers.	"		Stinson p. 79-95, 100-101, 109-112
Tue 05/08/2007	Block ciphers formally. Security definitions. Basic cryptographic primitives.		solution:
Fri 05/11/2007	Semantic Security under CPA. Security of CBC and randCTR.	"
Tue 05/15/2007	MACs (Message Authentication Codes). CBC-MAC and PMAC. Hash functions.		solution:	Stinson p. 136 - 141
Fri 05/18/2007	Q&A session
Tue 05/22/2007	HMAC. Secure Channels via Ciphers and MACs. WEP (802.11b encryption)	"
Fri 05/25/2007	Mid-term exam (14:00-15:00 s.t.)
Tue 05/29/2007	Introduction to number theory. Finite groups. Efficient algorithms for computing in finite groups.		solution:	Stinson p. 157  -166
Fri 06/01/2007	Public-key Encryption in groups of prime order. Discrete logarithms. ElGamal encryption, Diffie-Hellman key exchange.
Tue 06/05/2007	Stronger security definitions. Cramer-Shoup encryption.		solution:
Fri 06/08/2007	Cramer-Shoup continued.	"
Tue 06/12/2007	(Trapdoor) One-way functions. Arithmetic modulo composites. Naive RSA. Factoring/RSA assumption.		solution:	Stinson p. 155 -170
Fri 06/15/2007	Variants of RSA encryption. OAEP. OAEP+. Detailed investigation of RSA security (small secret keys, too many recipients, etc).	"		Stinson p. 194 - 204, 212 - 218
Tue 06/19/2007	(no lecture)		solution:
Fri 06/22/2007	Digital signatures. Security definitions. Common Schemes. DSS.			Stinson p. 274 - 300
Tue 06/26/2007	Trust Management. Certificates. Certificate chains and revocation. PKI.		solution:
Fri 06/29/2007	Authentication Methods. SSL. More security protocols.
Tue 07/03/2007	Bit Commitment Schemes.		solution:
Fri 07/06/2007	Secret Sharing.
Tue 07/10/2007	Questions and Answers, Zero-knowledge, current research.
Fri 07/13/2007	Final exam (14:00-16:00)
Tue 10/16/2007	Backup Exam

Further Reading

• Summary of basic probability theory by David Joice (.pdf): A very concise introduction to probability theory
• Introduction to Probability by Albert Meyer (.pdf): Provides more material on probability theory
• A Primer on number theory for computer scientists by Victor Shoup (.pdf): Provides more material and more details on number theory and algebra.