Foundations of Cryptography (Spring 2018)

Lecturers: Antonio Faonio and Dario Fiore, IMDEA Software Institute

Timetable: February 21, 26; March 7, 14; April 4, 11, 18, 25; May 9, 16, 23, 30. Time: 5pm-7pm.
Where: UPDATED IMDEA Software Institute, room 379 (3rd floor) (previous: ETS de Ingenieros Informáticos – Universidad Politecnica de Madrid, Campus Montegancedo – Aula H-1003 )
Office hours: before every class, otherwise on appointment.

Registration: students from Universidad Politecnica de Madrid (UPM), Master in Software and Systems and Universidad Rey Juan Carlos (URJC) can officially register and get credits for this seminar. Other students are also welcome to attend. If you are interested please send us an email to dario.fiore (at)

Course Outline

Cryptography is a fundamental tool for protecting information and communication in computer systems. This course is a graduate-level introduction to cryptography, suitable for students interested in mathematics and computer science. The course will primarily focus on definitions and constructions of various cryptographic primitives, including pseudorandom generators, pseudorandom functions, encryption schemes, digital signatures and message authentication codes. Students will learn how to reason about the security of cryptographic constructions and how to properly use these constructions in real-world applications. No prior knowledge of cryptography is required, as well as no formal mathematical prerequisites are needed. However, mathematical maturity (e.g., reading and writing proofs) is expected.


  • General introduction to the problem of secret communication. Perfect security; one-time pad cipher and Shannon impossibility result. Introduction to computational security.
  • Encryption and motivation for basic functionalities: one-way functions/permutations, trapdoor permutations
  • Number theory and realizations of (trapdoor) one-way functions
  • Toy public key encryption; from deterministic to probabilistic encryption. Hardcore bits and Goldreich-Levin theorem.
  • Pseudorandom generators
  • Public key encryption: definition of semantic security and constructions.
  • Secret key encryption and stream ciphers
  • Pseudorandom functions: definitions and realizations
  • Message Authentication Codes
  • Digital Signatures
  • Collision-resistant hash functions
  • More topics (such as full-domain-hash signatures and the random oracle model) could be covered according to the available time.


Credits: 2 ECTS for UPM students. 1,2 ECTS for URJC students.

Language: English

Assessment Method: Periodic exercise sheets

References: most of the material is covered in: Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. See
Other useful readings: A number theory primer by Dana Angluin.


Lecture Summaries

  • Lecture 1 (Feb 21): problem of secret communication; one-time pad and definition of perfect security; Shannon’s theorem; motivation for computational security; probabilistic polynomial time and negligible functions.
    [Katz-Lindell, Chapters 1, 2, 3.1] [some useful notes (by Y. Dodis)]
  • Lecture 2 (Feb 26): implication of computational security and distinction between secret-key encryption (SKE) and public-key encryption (PKE); formal definitions of SKE and PKE; towards PKE: one-way functions, one-way permutations and trapdoor permutations; candidate examples of OWFs (integer multiplication), OWPs (modular exponentiation); TDPs (RSA).
    [Katz-Lindell, Chapters 7.1.1, 8.4.1, 13.1.1, 7.1.2, 8.1, 8.2] [some useful notes (by Y. Dodis)] [A number theory primer (by D. Angluin)]
  • Lecture 3 (Mar 7): application of OWP for a secure password-authentication system; weak (one-way secure) public key encryption (definition and construction from TDPs); limitations of deterministic encryption: towards probabilistic encryption; definition of hardcore predicated.
    [Katz-Lindell, Chapters 7.1.3,] [some useful notes (by Y. Dodis)]
  • Lecture 4 (Mar 14): hardcore bits for specific OWFs; most significant bit is hardcore for modular exponentiation (DLog); hardcore predicates from OWFs, Goldreich-Levin theorem.
    [Katz-Lindell, 7.3] [some useful notes (by Y. Dodis)]
  • Lecture 5 (April 11):