We discuss several advanced security concepts like semantic security and plaintext indistinguishability. We also describe several techniques to design cryptosystems that meet these strong security requirements. In particular, we discuss one-way functions, pseudorandom generators, and pseudorandom functions. Finally, we compare the security of cryptosystems used in practice (like AES and RSA) with advanced security concepts.

Module Information

  • Module III.2.2: Algorithmen II (algorithms II)
  • Module III.2.3: Komplexität und Kryptographie (complexity and cryptography)
  • Course: L.079.05829
  • V2 + Ü1 SWS (contact time)
  • 4 ECTS credits (workload)
  • Useful previous knowledge: 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.


  • Important Note: the lecture will only take place during the first half of the semester. The last appointment is on Tuesday, May 24th.
  • Lecture:
    • Tuesday, 11 a.m., F1.110
    • Tuesday, 2 p.m., F2.211
  • Additional lecture: An additional lecture on Goldreich-Levin predicates will be given on Tuesday, May 31st, 11a.m.
  • Tutorials:
    • Tuesday, 4 p.m., F2.211
    • The first tutorial will take place on April, 19'th, 2016

Lecture Notes

This course will make use of the literature given below. Beside this, there will be no lecture notes for this course. Extensive lecture notes in cryptography of Luca Trevisan are available online.

1. Introduction[PDF]
2. Perfect Secrecy[PDF]
3. Indistinguishable Encryptions & Pseudorandom Generators[PDF]
4. Pseudorandom Functions & Encryption[PDF]
5. Block Ciphers[PDF]
6. One-way Functions & Pseudorandom Generators[PDF]
7. Modes of Operation - Counter Mode[PDF]
8. Public Key Encryption[PDF]


Dates for oral exams have to be planned individually. To request a date, send a timely request to Claudia Jahn and the second professor for the exam, using an appropriate e-mail form from

Make sure you are registered for the exam within the PAUL system before requesting a date for your examination.


Here we will publish the home exercises. Note that we won't publish any solutions to these exercises. Solutions to selected exercises will be discussed in the tutorials. You can submit your solutions in the box at F2.108.  We encourage submissions of solutions by small groups of up to four students.

The first exercise will take place on April, 19'th, 2016.

Handout 12016-04-11updated 2016-04-13, corrections in Ex. 3b
Handout 22016-04-15
Handout 32016-04-22updated 2016-04-27, encourage group submissions
Handout 42016-04-29
Handout 52016-05-09
Handout 62016-05-13updated 2016-05-23, correction in Ex. 4
Handout 72016-05-20


  • 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!
  • 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.