Cryptography (Fall 2024)

Syllabus

The course is meant to be an introduction to modern cryptography, with a focus on provable security. Below is a tentative list of topics.

Information-Theoretic Cryptography:

• Perfect secrecy, one-time pad, Shannon's theorem.
• Perfect authentication, universal hashing, extractors, leftover-hash lemma.

Computational Security:

• One-Way Functions (OWF) and complexity theory.
• Brush-up on number theory, candidate OWF (Factoring, RSA, DL, LWE).
• Computational indistinguishability, decisional assumptions (DDH, LWE).

Symmetric Cryptography:

• Pseudorandom Generators (PRG), hard-core bits, PRG constructions.
• Pseudorandom Functions (PRF), PRF constructions, Feistel networks.
• Symmetric encryption: Definitions and constructions, modes of operation.
• Message authentication: Definitions and constructions, authenticated encryption.
• Hash functions: Random oracle model, first/second pre-image resistance, collision resistance, Merkle-Damgaard construction.

Public-Key Cryptography:

• Public-key encryption: Definitions, RSA and ElGamal cryptosystems. Cramer-Shoup encryption.
• Digital signatures: Definitions, full-domain hash, signatures from OWF, Waters' signatures.
• Identification schemes: Definitions, constructions and applications to signatures.
• Identity-based encryption and applications.

Logistics

Important: The lectures are offered exclusively in-person (with no registration taking place).

Important: The lecture on 08/11/24 will be exceptionally remote at this link.

Lecture time: Tuesday (8:00am - 11:00am) and Friday (11:00am - 13:00am).
Location: The lectures on Tuesday take place in Aula Magna - Viale Regina Elena 295. The lectures on Friday take place in Aula 1L - Via del Castro Laurenziano 7a.
Twitter: @SapienzaCrypto.
Google Group: SapienzaCrypto.

Grading

Written exam. The written exam lasts 3 hours and consists of 3 exercises and 3 open questions. Books, notes and electronic devices are not allowed during the exam.

References

We will not follow a single book; the following textbooks are suggested as reference and for deeper study:

• [1] Daniele Venturi, Crittografia nel Paese delle Meraviglie, Springer, Collana di Informatica, 2012.
• [2] Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, CRC Press, Second Edition, 2014.
• [3] Jonathan Katz, Digital Signatures, Springer, 2010.
• [4] Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science, Vol. 7, Issue 1-3, 2012. Freely available here.
• [5] Jonathan Katz, Lecture Notes for a course on Advanced Topics in Cryptography, (Sping 2004). Lecture 9 and Lecture 10 are about the Cramer-Shoup PKE scheme.
• [6] Sanjit Chatterjee and Palash Sarkar, Identity-Based Encryption, Springer, 2011.

You may also find useful the following lecture notes from a past edition of the course (although not reviewed by myself):

• [7] Michele Laurenti, Lecture Notes for the Cryptography Course, Sapienza University of Rome, A. Y. 2016/2017.

Exams

Below are the exam dates for academic year 2024/2025. Please register via Infostud.

Exam 1. Date: 13/01/25. Aula 3 (RM018). Time: 10:00-13:00. Scores [pdf].
Exam 2. Date: 03/02/25. Aula 1 (RM018). Time: 10:00-13:00. Scores [pdf].
Exam 3. Reserved to part-time and working students (you must make a formal request to the secretariat; registration in Infostud is still required). Date: TBA. Aula: TBA. Time: TBA. Scores [pdf].
Exam 4. Date: 09/06/25. Aula 1 (RM018). Time: 10:00-13:00. Scores [pdf].
Exam 5. Date: 14/07/25. Aula 1 (RM018). Time: 10:00-13:00. Scores [pdf].
Exam 6. Date: 08/09/25. Aula 1 (RM018). Time: 10:00-13:00. Scores [pdf].
Exam 7. Reserved to part-time and working students (you must make a formal request to the secretariat; registration in Infostud is still required). Date: TBA. Aula: TBA. Time: TBA. Scores [pdf].

Announcements

12/09/2024: The course will start on September 24th, 2024. Due to the ongoing construction works in Aula Magna, the lecture on 24/09/2024 will take place in Aula IV Matematica - Edificio Castelnuovo, Città Universitaria.
30/09/2024: Due to the ongoing construction works in Aula Magna, the lecture on 01/10/2024 will take place in Aula 301 - Palazzina D, Viale Regina Elena 295, 00161 Rome.
02/10/2024: Due to the ongoing construction works in Aula Magna, the lecture on 08/10/2024 will take place in Aula 301 - Palazzina D, Viale Regina Elena 295, 00161 Rome.
07/11/2024: Due to the national strike announced for tomorrow, the lecture on November 8th will be exceptionally remote at this link.
12/12/2024: Due to the national strike announced for tomorrow, the lecture on December 13th will be exceptionally remote at this link.

Lectures