Skip to main content.
Cryptography (CS 578)
Core lecture in Summer Term 2006

Lecture Time
Tue 11-13, Fri 11-13
Location
E 1.3, HS 002
Course Material
available here
Language
English
Contact
cs578@mail-inf
v7qfrcdsf7
sec.cs.u
opypko63q9
ni-sb.de
43zivt4wam

duerm
mc3s86zxtt
uth@cs.uni-sb.
hccbgnyiul
de
yogku55m2t

News

+++ Inspection of the Backup Exam +++
The inspection of the backup exam will take place at Tuesday, Oktober 17, from 2pm to 4pm, in the seminar room in the ground floor of building E1 1 (right in front of our group).

Participants of the backup exam will receive their grades per email on Thursday.


+++ Backup Exam +++
The Backup Exam takes place on October 4, 9:30-11:30, in HS I, E2.5 (math building). Registered participants of the cryptography course are permitted to write the backup exam if they (i) qualified for the final exam, and (ii) failed or did not participate in the final exam.


The final exam takes place on Friday, 07/21/2006, from 13:00 to 15:00. Please check your matriculation in the list below!

Family names Lecture Hall
A - Hei HS 002, E1.1 (CS)
Hen - Z HS I, E2.5 (Math)

+++ please check +++
The list of admitted students for the final exam can be found here.



The Information Sheet is available here (.ps .pdf).

The discussion board is located here.

Your assignment to the tutorials can be found here.

The slides of the lecture can be downloaded here. Registered course participants will receive the login data in a separate mail. 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.

Assignment to groups for the midterm exam is available here.

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:
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).

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 tutorials are available:
Your assignment to the tutorials can be found here.

Why are two tutorials at the same time? See the section on quizzes below.

The tutors will be available for your questions at the following times in building E 1 1, Room U19:
Prof. Backes will be available for your questions at the following times in building E 1 1, Room U15:

Homeworks

Weekly homework exercises will be handed out in class and posted to the course page each Tuesday, starting Tuesday, April 25. 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 two quizzes 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 four 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 quiz on May 30, 2006, and a final exam on July 21, 2006.

The mid-term quiz 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
Final = 0.3*Q + 0.2*M + 0.5*E,
you pass the course if
Q ≥50% and E≥50% and Final≥50%.



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

The backup exam will take place on October 4, 2006. 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/21/2006 Organizatorial aspects. Historical overview of cryptography. Information theoretic security. Perfect secrecy. One-time pad .ps .pdf
Stinson p.1-13, 25-34, 45-54
Tue 04/25/2006 Optimality of the One-time Pad. Attacks against the One-time Pad. Stream ciphers. .ps .pdf
 .ps .pdf
ciphertext.txt
solution: .ps .pdf
 Stinson p. 45-54, 21-24
Fri 04/28/2006 Idea of Block Ciphers. DES (Data Encryption Standard). AES (Advanced Encryption Standard) .ps .pdf
Stinson p. 73-79, 95-108
Tue 05/02/2006 Variants of DES. Various attacks against block ciphers. Modes of operation for block ciphers.   "
 .ps .pdf
solution: .ps .pdf
 Stinson p. 79-95, 100-101, 109-112
Fri 05/05/2006 Block ciphers formally. Semantic Security. Basic cryptographic primitives.  .ps .pdf

Tue 05/09/2006 Semantic Security under CPA. Security of CBC and randCTR.
 "
 .ps .pdf
solution: .ps .pdf
Fri 05/12/2006 MACs (Message Authentication Codes). CBC-MAC and PMAC. Hash functions. .ps .pdf
Stinson p. 136 - 141
Tue 05/16/2006 HMAC. Secure Channels via Ciphers and MACs. WEP (802.11b encryption) additional material:
.ps .pdf
 .ps .pdf
solution: .ps .pdf
Fri 05/19/2006 Introduction to number theory. Finite groups. Efficient algorithms for computing in finite groups. .ps .pdf
Stinson p. 157  -166
Tue 05/23/2006 (no lecture)


Fri 05/26/2006 Question & Answers (Mid-term exam)


Tue 05/30/2006 Mid-term exam .ps .pdf

Fri 06/02/2006 Public-key Encryption in groups of prime order. Discrete logarithms. ElGamal encryption, Diffie-Hellman key exchange. .ps .pdf
 .ps .pdf
solution: .ps .pdf
Tue 06/06/2006 Stronger security definitions. Cramer-Shoup encryption. .ps .pdf
 .ps .pdf solution: .ps .pdf
Fri 06/09/2006 Security of Cramer Shoup.
 "

Tue 06/13/2006 (Trapdoor) One-way functions. Arithmetic modulo composites. Naive RSA. Factoring/RSA assumption.  .ps .pdf
 .ps .pdf
solution: .ps .pdf
 Stinson p. 155 -170
Fri 06/16/2006 Variants of RSA encryption. OAEP.  OAEP+. Detailed investigation of RSA security (small secret keys, too many recipients, etc) .ps .pdf
Stinson p. 194 - 204, 212 - 218
Tue 06/20/2006 Digital signatures. Security definitions. Common Schemes. DSS .ps .pdf
 .ps .pdf
solution: .ps .pdf
 Stinson p. 274 - 300
Fri 06/23/2006 Trust Management. Certificates. Certificate chains and revocation. PKI .ps .pdf

Tue 06/27/2006 Authentication Methods. SSL. More security protocols. .ps .pdf
 .ps .pdf
solution: .ps .pdf
Fri 06/30/2006 Bit Commitment. .ps .pdf

Tue 07/04/2006 (no lecture)
.ps .pdf
solution: .ps .pdf

Fri 07/07/2006 Bit Commitment. Secret Sharing.
 .ps .pdf

Tue 07/11/2006 Zero-knowledge.
 .ps .pdf

Fri 07/14/2006 Question & Answers (Final exam)


Tue 07/18/2006 Current research topics. Excerpts of our own research.


Fri 07/21/2006 Final exam




Wed 10/04/2006 Backup Exam


Errata of Lecture Notes

+++ Update +++
The errata of the lecture notes is available here: .ps .pdf (Version 07/16/2006).

Further Reading