News
- 2008-02-04: No tutorial on Feb 9, lecture on Feb 11 held by Matteo Maffei, extra Q&A session on Feb 16
- 2008-10-23: The lecture hall is from now on: Hörsaal 1 (mathematics)
Course Outline
Short lecture notes can be found here. Photos of the black board can be found here (or as single PDF). All solutions as a single PDF. Errata can be found here.| Date | Topics | Homework | Solutions | References |
| 2008-10-22 | Basic intuition behind proofs and zero-knowledge | - | - | |
| 2008-10-29 | ZK proof for graph isomorphism, definitions of soundness and completeness | Sheet 1 | Sheet 1 | |
| 2008-11-05 | Definition of statistical zero-knowledge (without auxiliary input). Statistical distance | Sheet 2 | Sheet 2 | |
| 2008-11-12 | Auxiliary input. Sequential composition theorem | Sheet 3 | Sheet 3 | |
| 2008-11-19 | Proof for graph-3-colouring | Sheet 4 | Sheet 4 | |
| 2008-11-26 | Computational indistinguishability. Computational zero-knowledge. Proof for G3C is computationally ZK | Sheet 5 | Sheet 5 | |
| 2008-12-17 | Sequential composition of CZK. Proofs of knowledge | Sheet 6 | Sheet 6 | |
| 2009-01-07 | Schnorr's proof for dlog. Special soundness. Honest-verifier ZK | Sheet 7 | Sheet 7 | |
| 2009-01-14 | CRS model. CZK schemes from special HVCZK. | Sheet 8 | Sheet 8 | [Dam01] |
| 2009-01-21 | Combining ZK proofs (AND and OR). | Sheet 9 | Sheet 9 | [CDS94] |
| 2009-01-28 | Non-interactive zero-knowledge proofs. | Sheet 10 | Sheet 10 | |
| 2009-02-04 | Making CCA2-secure encryption from CPA-secure encryption. | Sheet 11 | Sheet 11 | [DDN91] |
Description and List of Topics
A zero
knowledge proof is a cryptographic protocol that allows to prove that a
statement is correct without revealing anything more than the bare fact
that the statement is true.
Zero knowledge proofs are widely used in cryptography; most advanced protocols use zero knowledge proofs as a building block at one place or another.
This lecture gives an introduction in the field of zero knowledge proof systems and presents basic and advanced techniques for building such proof systems.
Prerequisites
It is recommended that you have heard a lecture on cryptography, for example one of Prof. Backes’ lectures.
Reading
[Gol01] Goldreich, "Foundations of Cryptography, Volume 1 - Basic Tools", Cambridge University Press, 2001. ISBN 978-0521035361. Zero-Knowledge is covered in Chapter 4. A preliminary version can be found online at http://www.wisdom.weizmann.ac.il/~oded/foc-drafts.html.
[Dam00] Damgård, "Efficient Concurrent Zero-Knowledge in the Auxiliary String Model", Eurocrypt 2000. Online at http://www.iacr.org/archive/eurocrypt2000/1807/18070424-new.pdf.
[CDS94] Cramer, Damgård, Schoenmakers, "Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols", Crypto '94. Online at http://www.win.tue.nl/~berry/papers/crypto94.pdf.
[DDN91] Dolev, Dwork, Naor, "Non-Malleable Cryptography", SIAM Journal on Computing, 30(2):391-437, 2000. Online at http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/nmc.ps.
Further reading may be suggested during the course. See the references column in the course outline.