Cryptographic Protocols (SS 2012)


We will discuss authentication schemes, protocols for identification and their variants. Afterwards, we will go into zero knowledge protocols. Finally, we will build numerous cryptographic primitives upon these techniques.

In the first half of the semester there is a course on the foundations of provably secure cryptography.

Module information

  • Module III.2.2: Algorithmen II (algorithms II)
  • Module III.2.3: Komplexität und Kryptographie (complexity and cryptography)
  • V2 + Ü1 SWS (contact time)
  • 4 ECTS credits (workload)
  • Useful previos knowledge: Introduction to Cryptography or Einführung in Kryptographie (German) or any equivalent course
  • This course will be held in english.

For further information see the corresponding section in the module handbook (in German only).


This course will be held in the second half (June/July) of the semester.

  • Lecture:
    • Monday, 9 - 11 o'clock, room F0.530
    • Thursday, 11 - 13 o'clock, room F1.110
  • Tutorials
    • Monday, 13 - 14 o'clock, room F0.530

Lecture Notes

This course will make use of the literature given below. Beside this, there will be no lecture notes for this course.

Date Topic Section in Katz/Lindell
07.06. introduction, message authentication codes 4.1, 4.2, 4.3
10.06. pseudo random functions,
fixed-length MACs from PRFs
3.6.1, 4.4
14.06. hash-functions, collision-resistance,
"birthday" lower bound, one-wayness
4.6, (6.1.1)
17.06. collision-resistance vs. one-wayness,
Merkle-Damgård transform
(no section on CR vs OW),
21.06. Hash-and-MAC paradigm, NMAC,
privacy & authentication
(12.4), 4.7, 4.9
24.06. digital signature schemes,
RSA signatures
12.1, 12.2, (7.1, 7.2), 12.3
28.06. RSA signatures, Hash-and-Sign paradigm 12.3, 12.4
01.07. One-time security, Lamport signatures 12.5
05.07. Random oracle model,
RSA-FDH (full domain hash)
13.1, 13.3
08.07. Coron's analysis of RSA-FDH,
introduction to identification protocols
(no section in the book)
15.07. Fiat-Shamir protocol (no section in the book)
19.07. (no section in the book)
22.07. (no section in the book)


19.07.: in exercise 13 it should be gcd(f1-f2,e)=1 instead of gcd(f1-f2,phi(N))=1


  • Bellare, Rogaway: Lecture Notes on "Introduction to Modern Cryptography", University of California, San Diego, 2004--2005. Lecture notes available online!
  • Goldreich: "Foundations of Cryptography, Volume 1: Basic Tools", Cambridge University Press, 2001. ISBN: 0-521-79172-3. Early draft version available online!
  • Goldreich: "Foundations of Cryptography, Volume 2: Basic Applications", Cambridge University Press, 2004. ISBN: 0-521-83084-2.
  • Goldwasser, Bellare: Lecture Notes on "Cryptography", MIT, 1996--2001. Lecture notes available online!
  • Katz, Lindell: "Introduction to Modern Cryptography", Chapman & Hall / CRC Press, 2007. ISBN: 1-5848-8551-3
  • Lindell: Lecture Notes on "Introduction to Cryptography", Bar-Ilan University, 2005. Lecture notes available online!
  • Menezes, van Oorschot, Vanstone: "Handbook of Applied Cryptography", CRC Press, 1996. ISBN: 0-8493-8523-7. Complete book available online!
  • Shoup: "A Computational Introduction to Number Theory and Algebra", Cambridge University Press, 2005. ISBN: 0-521-85154-8. Complete book available online!
  • M. Sipser: "Introduction to the Theory of Computation", 3rd edition, Cengage Learning, 2013. ISBN: 1-133-18779-X.
  • Stinson: "Cryptography: Theory and Practice", 2nd edition, Chapman & Hall / CRC Press, 2001. ISBN: 1-5848-8206-9.
  • Trappe, Washington: "Introduction to Cryptography with Coding Theory", 3rd edition, Chapman & Hall / CRC Press, 2005. ISBN: 1-5848-8508-4.
  • Berry Schoenmakers: "Lecture Notes on Cryptographic Protocols", Chapter 4: Identification Protocols, available online

see also the corresponding entry in
PAUL (Paderborner 
Assistenzsystem für Universität und Lehre)

Impressum | Webmaster | Letzte Änderungen am : 16.10.2013