# Cryptography (Fall 2024)

Master's Degree in Computer Science, Master's Degree in Cybersecurity, Master's Degree in Mathematics

## 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

The exam dates for academic year 2024/2025 will be displayed here when available.

__ Exam (October 2024)__. Reserved to part-time and working students (you must make a formal request to the secretariat; registration in INFOSTUD is still required). Date: 21/10/24. Aula: G50 (Viale Regina Elena 295). Time: 11:00-14:00.

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

## Lectures

Date | Topics | References |
---|---|---|

Lecture 1 24/09/24 | Modern cryptography. Overview of the course. Syntax of secret-key encryption (SKE), public-key encryption (PKE), message authentication codes (MACs) and digital signatures. Definition of perfect secrecy. | [PDF] |

Lecture 2 27/09/24 | Equivalent notions of perfect secrecy. The one-time pad and Shannon's impossibility result. Definition of statistically-secure (one-time) MACs. | [PDF] |

Lecture 3 01/10/24 | Constructions of pairwise independent hash functions and one-time statistically secure MACs. Randomness extraction. Impossibility of randomness extraction from a single min-entropy source. Definition of seeded extractors. | [PDF] |

Lecture 4 04/10/24 | Leftover hash lemma. Beginning of computational security. | [PDF] |

Lecture 5 08/10/24 | Computational security. Definition and examples of one-way functions. Definition of pseudorandom generators (PRGs). | [PDF] |

Lecture 6 11/10/24 | Definition of one-time computationally secure SKE. Construction from any PRG. | [PDF] |

Lecture 7 15/10/24 | Constructing PRGs. Proof that one bit of stretch implies unbounded polynomial stretch. PRGs from one-way functions and hard-core bits. Applications to real-world PRGs. Definition of chosen-plaintext attacks (CPA) security for SKE. | [PDF] |

Lecture 8 18/10/24 | Definition of pseudorandom functions (PRFs). Application to constructing CPA-secure SKE for fixed input length (FIL) messages. Definition of universal unforgeability under chosen-message attacks (UFCMA) for MACs. | [PDF] |

Lecture 9 22/10/24 | Proof that PRFs imply CPA-secure SKE for FIL messages. Proof that PRFs imply UFCMA MACs for FIL messages. Modes of operation for SKE. | [PDF] |

Lecture 10 25/10/24 | Proof of CPA security for the CTR mode. Domain extension for MACs. | [PDF] |

Lecture 11 30/10/24 | Domain extension for MACs. Universal hashing and CBC-MAC. XOR-MAC. | [PDF] |

Lecture 12 05/11/24 | Definition of CCA security for SKE. Combining encryption and authentication. | [PDF] |

Lecture 13 08/11/24 | Exercises. | [PDF] |