Latest News

• Mininotes available for download (.ps, .pdf)
• Discussion board is online.

Date	Topics	Slides	Homework	Solutions	References
10/20/2006	Logistics, Introduction to One-Way Functions	PDF,PDF-3to1			Goldreich (Chapter 1, 2.1, 2.2)
10/27/2006	On Weak vs. Strong One-Way Functions	PDF,PDF-3to1	PDF	PDF	Goldreich (Chapter 2.3)
11/03/2006	(no lecture)
11/10/2006	Collections of OWF and TP, hard-core predicates	PDF,PDF-3to1	PDF	PDF	Goldreich (Chapters 2.4.2, 2.4.4, 2.5)
11/17/2006	Computational indistinguishability, pseudorandom generators	PDF,PDF-3to1
11/24/2006	Pseudorandom functions	PDF,PDF-3to1	PDF		Goldreich (Chapters 3.6.1, 3.6.2)
12/01/2006	(no lecture)
12/08/2006	Interactive proof systems, zero-knowledge proofs	PDF,PDF-3to1	PDF	PDF (partial)	Goldreich (Chapters (4.1), 4.2, 4.3)
12/15/2006	Zero-knowledge for all of NP	PDF,PDF-3to1			Goldreich (Chapter 4.4)
12/22/2006	"	PDF,PDF-3to1			Goldreich (Chapter 4.4)
01/12/2007	Non-interactive zero-knowledge proofs	none	PDF	PDF	Goldreich (Chapter 4.10)
01/19/2007	Encryption Schemes I	PDF,PDF-3to1			Goldreich II (Chapter 5)
01/26/2007	Encryption Schemes II	PDF,PDF-3to1	PDF	PDF (partial)	Goldreich II (Chapter 5)
02/02/2007	Signatures	PDF,PDF-3to1			Goldreich II (Chapter 6)
02/09/2007	Signatures II	PDF,PDF-3to1	PDF	PDF	Goldreich II (Chapter 6)
02/16/2007	Identity-based Encryption and Pairings	PDF,PDF-3to1

Description and List of Topics (tentative)

This course will cover more advanced, foundational aspects of cryptography than those covered by the core lecture cryptography. In particular, things are treated more formally and from a more theoretical point of view. 

The following list of topics is still tentative:

• Complexity-theoretic foundations of cryptography: on weak/strong one-way functions, universal one-way functions, hardcore predicates, pseudorandom generations, computational indistinguishability, pseudorandomness in general, etc.
• Zero-knowledge proofs in many variations and extensions: ZK for all NP, non-interactive zero-knowledge, proofs of knowledge, generalizations, efficiency improvements, etc.
• Digital signatures: Provably secure schemes, minimal requirements, Fiat-Shamir paradigm, etc.
• Secure Multi-party computation: basic constructions, adaptive adversaries, definitional issues and relaxed MPC definitions, quantified reductions, secure computation of approximations, etc.
• Definitional issues and composition of secure protocols: The Reactive Simulatability (RSIM) framework, formulating standard cryptographic primitives within the framework, composition theorems, etc.
• Cryptographic soundness of symbolic cryptography
• Bilinear Maps and their applications
• Identity-based techniques, e.g., identity-based/attribute-based encryption

The first half of the lecture will follow the following book:

• Oded Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001

The second half will deal with different foundational aspects of cryptography not covered there, and we will give detailed references to papers and provide suitable lecture notes.

Prerequisites

This course is an advanced lecture on foundational issues in cryptography. You should have attended the core theory lecture on cryptography and have a solid background in theoretical computer science. Knowledge especially in complexity theory and elementary probability theory will prove useful.

Tutorials

The tutorial will take place on Thursday, 4-6pm.

Office Hours

The tutor will be available for your questions at the following times in building E 1 1, Room U18: Tuesday 9-11am

Prof. Backes will be available for your questions at the following times in building E 1 1, Room U15: Thursday 12-13

Homeworks

Homework exercises will be handed out every second week in class and posted on the course web page each Friday, starting October 27. Their solutions will be posted two weeks later (after the next exercise sheet has been handed out). 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; they serve as a preparation for the quizzes, see below.

(Bi-)Weekly Quizzes, Exams

Every second week, the tutorial starts with a short (approx. 20 minutes) quiz covering the topics of the same two lectures that were addressed in the last homework exercise. (The tutorials in the remaining weeks will be treated as office hours, i.e., you can ask questions but are not required to write a quiz or present a solution.) Your overall quiz-grade is determined by dropping the quiz with the lowest grading, and calculating the average of the remaining quizzes. (There will be approximately 5-6 quizzes overall.) Quizzes will affect your final grading by 30%, and you need an overall quiz-grading of at least 50% to pass the course.

The final exam will be a written test of two hours. It will make up 70% of your final grade and you need at least 50% to pass the course. The final exam will take place on Friday, February 23, 11am-1pm.

The date of the backup exam has not been fixed yet. If the number of participants is small, oral examinations will be scheduled according to individual preferences.

Reading

Further reading will be suggested during the course.