Cryptography (Fall 2025)

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).

Lecture time: Tuesday (8:00am - 11:00am) and Friday (11:00am - 13:00am).
Location: Aula 1L (RM018) - 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] Simone Bianco, Lecture Notes for the Cryptography Course, Sapienza University of Rome, A. Y. 2025/2026 (work in progress).

Exams

The exam dates for academic year 2025/2026 will appear below. Please always register via Infostud. Exam 8. Reserved to part-time and working students a.y. 2024/2025 (you must make a formal request to the secretariat; registration in Infostud is still required). Date: 05/11/2025. Aula: 4 (RM158). Time: 08:00-11:00. Scores [pdf].

Announcements

20/09/2025: The course will start on September 23, 2025.
02/10/2025: Due to the national strike announced for tomorrow, the lecture on October 3 will be exceptionally remote at this link.
30/10/2025: The lecture on 04/11/2025 will not take place.

Lectures