News

• You can obtain your certificates (Scheine) from our secretary in room U 14, Building E1 1.
• Exam correction: You can access your grades in the HISPOS system. If you want to inspect your exam, please contact Matthias Berg in room U 18, building E1 1.
• Short notes available for download (.pdf)
• There is no lecture over Easter (March 21 - March 24).
• Lecture period changed to Wed, March 12 - Fri, March 28.
• Registration (including HISPOS) is not necessary before the course has started. The registration deadline will be afterwards. Just come to the lecture on Wed, March 12.

Course Outline

Date	Topics	Slides	Homework	Solutions	References
03/12/2008	Logistics, Introduction to One-Way Functions	.pdf	.pdf	.pdf	Goldreich (Chapter 1, 2.1, 2.2)
03/13/2008	On Weak vs. Strong One-Way Functions	.pdf	.pdf	.pdf	Goldreich (Chapter 2.3)
03/14/2008	Collections of OWF and TP, hard-core predicates	.pdf	.pdf	.pdf	Goldreich (Chapters 2.4.2, 2.4.4, 2.5)
03/17/2008	Computational indistinguishability, pseudorandom generators	.pdf	.pdf	.pdf	Goldreich (Chapters 3.2, 3.3, 3.4, 3.5)
03/18/2008	Pseudorandom functions	.pdf	.pdf	.pdf	Goldreich (Chapters 3.6.1, 3.6.2)
03/19/2008	Interactive proof systems, zero-knowledge proofs	.pdf	.pdf	.pdf	Goldreich (Chapters (4.1), 4.2, 4.3)
03/20/2008	Zero-knowledge for all of NP	.pdf	.pdf	.pdf	Goldreich (Chapter 4.4)
03/25/2008	Encryption Schemes I	.pdf	.pdf	.pdf	Goldreich II (Chapter 5)
03/26/2008	Encryption Schemes II	.pdf	.pdf	.pdf	Goldreich II (Chapter 5)
03/27/2008	Signatures I	.pdf	.pdf	.pdf	Goldreich II (Chapter 6)
03/28/2008	Signatures II	.pdf	.pdf	.pdf	Goldreich II (Chapter 6)

Description and List of Topics

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. 

• Complexity-theoretic foundations of cryptography: on weak/strong one-way functions, universal one-way functions, trapdoor permutations, hardcore predicates, pseudorandom generators, computational indistinguishability, pseudorandomness in general, etc.
• Zero-knowledge proofs: interactive proof systems, perfect and computational zero-knowledge, commitment schemes, ZK for all NP, etc.
• Encryption schemes: semantic security, indistinguishable encryptions, public and private key scenarios, security for single and multiple messages, block ciphers, minimal requirements, constructions, etc.
• Digital Signatures: unforgeable signatures, fixed length and general schemes, hash functions, one-time signatures, memory dependent signatures, minimal requirements, constructions, etc.

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.

Reading

Further reading will be suggested during the course.