Foundations of Cryptography (Spring 2018)

Lecturers: Antonio Faonio and Dario Fiore, IMDEA Software Institute

Timetable: February 21, 26; March 7, 14; April 4 (canceled), 11, 18, 25; May 9, 16, 23, 30. Time: 5pm-7pm. UPDATE: The class of April 4th will be held Friday 13th April, 2pm

Where: 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) imdea.org

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.

Syllabus

• 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. 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): PKE for 1-bit from TDP [Katz-Lindell, 13.1] [Lecture notes 4 (by Y.Dodis)]; Definition of Pseudo Random Generator (PRG) [Katz-Lindell, 3.3.1] [Lecture notes 4 (by Y.Dodis)]; PRG with minimal expansion [Katz-Lindel, 7.4.1] [Lecture notes 5 (by Y.Dodis)]; Hybrid argument and PRG with poly-expansion [Lecture notes 5 (by Y.Dodis)],[Katz-Lindel, 7.4.2].
• Lecture 6 (April 13): The Blum-Micali and the Blum-Blum-Shub PRGs; Stream Chipers; One-Way Secure PKE; Indistinguishability for PKE; PKE construction for many bits; CPA-IND for PKE; Semantic Security for PKE; CPA-IND implies Semantic Security;
• Lecture 7 (April 18): IND-CPA and Semantic Security are equivalent; Multi-message IND-CPA vs IND-CPA; Diffie-Hellman Key-Exchange and CDH; Decisional Diffie-Hellman assumption and ElGamal; [Lecture notes 6 (by Y.Dodis)], [Lecture notes 7 (by Y.Dodis)], [Katz-Lindel, 11.2.2, 11.4.1 8.3.2, 8.3.3]
• Lecture 8 (April 25): security definition of secret-key encryption (SKE); towards constructing SKE, stream ciphers, pseudorandom function; the Goldreich-Goldwasser-Micali (GGM) pseudorandom function. [Katz-Lindell: 3.5, 3.6.1, 7.5] [Lecture notes 8 (by Y.Dodis)]
• Lecture 9 (May 9): the Naor-Reingold pseudorandom function; secret-key encryption from PRFs. [Katz-Lindell 3.5] [Lecture notes 9 (by Y.Dodis)]
• Lecture 10 (May 16): Pseudorandom permutations, Feistel Networks, Luby-Rackoff construction and proof, modes of operation. [Katz-Lindell 3.6, 7.6] [Lecture notes 9 (by Y.Dodis)]
• Lecture 11 (May 23): Message Authentication Codes (MAC); MACs from PRFs; Dealing with long messages; Universal hash Functions; Collision Resistant Hash functions. [Lecture notes 10 (by Y.Dodis)], [Lecture notes 11 (by Y.Dodis)]