Advanced Cryptography
Advanced lecture in winter term 2008/2009
Instructor
Teaching Assistant
Tutor
Sebastian Meiser
Lecture Period
Thu, March 12 - Fri, March 27 (block course)
Lectures
Daily (Mon-Fri) 10-12, Building E 1.3, HS 003
Tutorials
Daily (Mon-Fri) 15-17, HS 003 (first tutorial: Friday, March 13)
Course Material
Short lecture notes (complete notes), slides and papers suggested during the course
Language
English
Exam
Thursday, 16 April 2009, 10 - 12 a.m., HS 003
Contact
mohammadi@cs.uni
xza57bck6a
-0dw8n353h6
saarland.de4xj792blju
Course Outline
| Date | Topics | Slides | Homework | References | |
| Thu 03/12/2009 | Logistics, Introduction to One-Way Functions | .pdf .pdf(3 on 1) |
Goldreich (Chapter 1, 2.1, 2.2) | ||
| Fri 03/13/2009 | On Weak vs. Strong One-Way Functions | .pdf .pdf(3 on 1) |
Goldreich (Chapter 2.3) | ||
| Mon 03/16/2009 | Collections of OWF and TP, hard-core predicates | .pdf .pdf(3 on 1) |
Goldreich (Chapters 2.4.2, 2.4.4, 2.5) | ||
| Tue 03/17/2009 | Computational indistinguishability, pseudorandom generators | .pdf .pdf(3 on 1) |
Goldreich (Chapters 3.2, 3.3, 3.4, 3.5) | ||
| Wed 03/18/2009 | Pseudorandom functions | .pdf .pdf(3 on 1) |
Goldreich (Chapters 3.6.1, 3.6.2) | ||
| Thu 03/19/2009 | Interactive proof systems, zero-knowledge proofs | .pdf .pdf(3 on 1) |
Goldreich (Chapters (4.1), 4.2, 4.3) | ||
| Fri 03/20/2009 | Zero-knowledge for all of NP | .pdf .pdf(3 on 1) |
Goldreich (Chapter 4.4) | ||
| Mon 03/23/2009 | Encryption Schemes I | .pdf .pdf(3 on 1) |
Goldreich II (Chapter 5) | ||
| Tue 03/24/2009 | Encryption Schemes II | .pdf .pdf(3 on 1) |
Goldreich II (Chapter 5) | ||
| Wed 03/25/2009 | Signatures I | .pdf .pdf(3 on 1) |
Goldreich II (Chapter 6) | ||
| Thu 03/26/2009 | Signatures II | .pdf .pdf(3 on 1) |
Goldreich II (Chapter 6) | ||
| Fri 03/27/2009 | Question and Answer Session |
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.
The list of topics comprises:
- Complexity-theoretic foundations of cryptography: on weak/strong 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.
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
The lecture will follow the books:- Oded Goldreich. Foundations of Cryptography: Volume I Basic Tools. Cambridge University Press, 2001
- Oded Goldreich. Foundations of Cryptography: Volume II Basic Applications. Cambridge University Press, 2004
Further reading will be suggested during the course.