Introduction to Cryptography (2014-2015)

Lecturer: Dario Fiore, IMDEA Software Institute

Timetable: First semester, once per week (2 hours), from October 2nd to December 16th, 2014.

Current plan: Oct 2, 7, 21, 28. Nov 11, 18, 25. Dec 2, 9, 16. Time: 5pm-7pm.

Where: IMDEA Software Institute‘s building, Room: 379 (3rd floor)

Note: date, time and place have changed! (before it was Thu 7pm-9pm).

Office hours: after every class, otherwise on appointment.

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 deterministi 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 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: lecture notes by Yeveniy Dodis, A number theory primer by Dana Angluin.

Lecture Summaries

• Lecture 1 (Oct 2): problem of secret communication; one-time pad and definition of perfect security; Shannon’s theorem; motivation for computational security; mentioning of secret-key vs. public-key encryption; towards PKE: one-way functions/permutations, trapdoor permutations. [Katz-Lindell: chapters 1,2] [some useful notes (by Y. Dodis)]
• Lecture 2 (Oct 7): formal definitions of secret-key encryption and public-key encryption; families of OWFs, OWPs, TDPs; candidate examples of OWFs (integer multiplication), OWPs (modular exponentiation); TDPs (RSA); application of OWP for a secure password-authentication system. [Katz-Lindell: sec 3.1, 6.1.1-6.1.2, 7.1, 7.2, 7.3.1, 7.3.2(only discrete log)] [some useful notes (by Y. Dodis)] [A number theory primer by Dana Angluin]
• Lecture 3 (Oct 21): weak (one-way secure) public key encryption (definition and construction from TDPs); limitations of deterministic encryption: towards probabilistic encryption; hardcore bits; hardcore bits for specific OWFs and for any OWF, Goldreich-Levin theorem; construction of PKE for one bit. [Katz-Lindell: 6.1.3,6.2,6.3 ] [some lecture notes (by Y. Dodis): (sections 10-12), (sections 1-5)] Note: the proof presented in the class closely follows the one in the book.
• Lecture 4 (Oct 28): construction of PKE/SKE for many bits; definition of pseudorandom generators (PRG); construction of PRGs with one bit expansion; hybrid games; construction of PRGs with arbitrary expansion. [Katz-Lindell: 6.4 ] [some lecture notes (by Y. Dodis)]
• Lecture 5 (Nov 11): the Blum-Micali and the Blum-Blum-Shub PRGs; stream ciphers; public key encryption; one-way secure PKE; PKE constructions for one and many bits; definition of polynomial indistinguishability; IND-CPA security, semantic security and their equivalence. [Lecture Notes (by Y. Dodis)]
• Lecture 6 (Nov 18): IND-CPA security definition: single- vs. multi-challenge definition; efficient public key encryption schemes, Diffie-Hellman key exchange, the Decisional Diffie-Hellman (DDH) assumption, ElGamal and its properties. [Katz-Lindell: 7.3.2, 9.4, 10.5] [Lecture notes (by Y. Dodis)]
• Lecture 7 (Nov 25): the Goldwasser-Micali encryption scheme; security definition of secret-key encryption (SKE); towards constructing SKE, stream ciphers, pseudorandom function; the Goldreich-Goldwasser-Micali (GGM) pseudorandom function. [Katz-Lindell: 11.1, 3.5, 3.6.1, 6.5] [Lecture notes (by Y. Dodis)]
• Lecture 8 (Dec 2): the Naor-Reingold pseudorandom function; IND-CPA secure SKE from pseudorandom functions; pseudorandom permutations; Luby-Rackoff construction. [Lecture notes (by Y. Dodis)]
• Lecture 9 (Dec 9): Luby-Rackoff construction and its proof; block ciphers and modes of operation. Message authentication: MACs definition; PRF as a MAC; dealing with long messages, universal hash functions. [Lecture notes (by Y. Dodis): on PRPs, MACs, universal hash]
• Lecture 10 (Dec 16): collision-resistant hash functions (CRHF), domain extension of MACs using CRHFs, Merkle-Damgard transformation, number-theoretic CRHFs; digital signatures, definition, (in)security of trapdoor signatures, one-time signatures (Lamport), from one-time secure to regular digital signatures. [Lecture notes (by Y. Dodis): hash functions, signatures]