# Cryptography (Fall 2023)

## 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 Magna - Viale Regina Elena 295.

*Twitter:*@SapienzaCrypto.

*Google Group:*SapienzaCrypto.

## Grading

Written exam. The written exam lasts 3 hours and consists of 3 excercises and 1 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.

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

## Exams

__. Date: 11/01/24. Aula 1 (RM018). Time: 09:00-12:00.__

*Exam 1**Scores*[pdf].

__. Date: 07/02/24. Aula 1 (RM018). Time: 09:00-12:00.__

*Exam 2**Scores*[pdf].

__. Reserved to part-time and working students (you must make a formal request to the secretariat; registration in INFOSTUD is still required). Date: 08/04/24. Aula: 2L (Via del Castro Laurenziano 7a). Time: 09:30-12:30.__

*Exam 3**Scores*[pdf].

__. Date: 05/06/24. Aula 3 (RM018). Time: 08:30-11:30.__

*Exam 4**Scores*[pdf].

__. Date: 04/07/24. Aula 1 (RM018). Time: 09:30-12:30.__

*Exam 5**Scores*[pdf].

__. Date: 10/09/24. Aula 2 (RM018). Time: 09:30-11:30.__

*Exam 6**Scores*[pdf].

## Announcements

__24/09/2023:__The course will start on September 26th, 2023.

__25/09/2023:__The lecture on 29/09/2023 has been canceled due to personal reasons.

__19/10/2023:__The students are invited to join the next appointment in the series of seminars Distinguished Lectures, hosted by the Computer Science Department. The talk is on 23/10/23 and starts at 12pm in Viale Regina Elena 295, Building D, Room 101.

## Lectures

The whiteboard notes for each lecture can be downloaded by clicking on the corresponding lecture.Class/Date | Topics Covered | Readings |
---|---|---|

Lecture 1, 26/09/23 | Introduction to the course. Secure communication: message confidentiality and integrity. Symmetric encryption and perfect secrecy. Equivalent notions of perfect secrecy. The one-time pad and Shannon's impossibility result. | [2]: 2 [1]: 2 [7]: 1.1 |

Lecture 2, 03/10/23 | Message Authentication Codes (MACs). Definition of statistically-secure (one-time) MACs. Pair-wise independent hashing: Definition and construction using modular arithmetic. Application to statistically-secure message authentication. Limits of statistically-secure MACs. The problem of randomness extraction, and definition of min-entropy. The von Neumann extractor. Impossibility of seedless extractors for min-entropy sources. | [1]: 3 [2]: 4 [4]: 6 [7]: 1.2, 1.3 |

Lecture 3, 06/10/23 | Definition of seeded extractors. Leftover-hash lemma: Statement and proof. | [4]: 6 [1]: 3 [7]: 1.3 |

Lecture 4, 10/10/23 | Computational security: Asymptotic security, negliglible and polynomial functions, PPT algorithms. One-Way Functions and Impagliazzo's worlds. | [1]: 1, 3, 3 [2]: 3, 7 [7]: 2.1 |

Lecture 5, 13/10/23 | Computational indistinguishability and hybrid arguments. Definition of Pseudo-Random Generators (PRGs). Definition of one-time computational security for Secret Key Encryption (SKE) and construction from any PRG. | [1]: 3, 5 [2]: 3, 7 [7]: 2.2, 2.3 |

Lecture 6, 17/10/23 | Definition of hard-core predicates. Goldreich-Levin theorem (statement). Proof that One-Way Permutations (OWPs) imply PRGs with one-bit stretch. | [1]: 3 [2]: 3, 7 [7]: 2.4 |

Lecture 7, 20/10/23 | Proof that one-bit stretch is sufficient to obtain arbitrary polynomial stretch. | [1]: 5, 7 [2]: 4, 7 [7]: 2.3 |

Lecture 8, 24/10/23 | Definition of Pseudorandom Functions (PRFs). Definition of chosen-plaintext attack (CPA) secure SKE and construction from any PRF family. | [1]: 5 [2]: 3, 7 [7]: 3.1 |

Lecture 9, 27/10/23 | Constructing PRFs from PRGs: The GGM construction. Modes of operation: ECB, CBC and CTR. Proof that CTR mode using a PRF yields a CPA secure SKE for variable length messages. | [1]: 5 [2]: 3, 4 [7]: 3.1, 3.5 |

Lecture 10, 31/10/23 | Message authentication codes in the computational setting: Unforgeability against chosen-message attacks. Proof that every PRF yields a fixed-input length MAC. | [1]: 5, 7 [2]: 4, 7 [7]: 3.2 |

Lecture 11, 03/11/23 | Domain extension for PRFs via almost-universal hash functions. Constructions of almost universal hash functions. CBC-MAC and Encrypted CBC-MAC. | [1]: 7 [2]: 4 [7]: 3.3 |

Lecture 12, 07/11/23 | Definition of chosen-ciphertext attack (CCA) secure SKE. Authenticated encryption and its relation to CCA security. Combining confidentiality and message integrity: Encrypt-then-MAC and proof of CCA security. | [1]: 5 [2]: 3, 4 [7]: 3.4 |

Lecture 13, 10/11/23 | Pseudorandom permutations (PRPs) and Feistel networks. | [1]: 5 [2]: 7 [7]: 3.5 |

Lecture 14, 14/11/23 | Exercises. | -- |

Lecture 15, 17/11/23 | More exercises. | -- |

Lecture 16, 21/11/23 | Collision-resistant hash functions. The Merkle-Damgaard construction. Constructing secure compression functions: The Davies-Mayer construction and its security in the ideal cipher model. | [1]: 4, 7 [2]: 4, 5 [7]: 3.6, 4.5 |

Lecture 17, 24/11/23 | Brush-up on number theory: Modular arithmetic, Euclidean algorithm, prime numbers. Integers factorization. Lagrange's theorem. Cyclic groups. | [1]: 4, B, C [2]: 5, 6, 8, B [7]: 4.1, 4.2 |

Lecture 18, 28/11/23 | The Discrete Logarithm (DL) problem. Diffie-Hellman key exchange. Computational Diffie-Hellman (CDH) and Decisional Diffie-Hellman (DDH) assumptions. Hardness of DDH. Simple number-theoretic constructions: OWPs from DL, PRGs and PRFs from DDH (Naor-Reingold). | [1]: B, C [2]: 8, B [7]: 4.3, 4.4 |

Lecture 19, 01/12/23 | Public-Key Encryption (PKE): Syntax and CPA security. RSA as a public-key encryption (with mentions to PKCS #1 v1.5 and PKCS #2 v2.0). | [1]: 6 [2]: 8, 11, 13 [7]: 5.1 |

Lecture 20, 05/12/23 | PKE from Tradpdoor Permutations (TPDs). RSA as a trapdoor permutation and the RSA assumption. Elgamal PKE and its CPA security from the DDH assumption. | [1]: B, 6 [2]: 11, 13 [7]: 5.2 |

Lecture 21, 12/12/23 | Signature schemes. The random oracle model (ROM). Constructing signatures from TPDs (Full-Domain Hash). Identification (ID) schemes. | [1]: 4, 8, 13 [2]: 5, 12 [3]: 6, 7 [7]: 6.2 |

Lecture 22, 15/12/23 | Passive security and canonical ID schemes. The Fiat-Shamir transform. | [1] 13 [2]: 12 [3]: 8 [7]: 6.2 |

Lecture 23, 19/12/24 | Excercises. | - |

Lecture 24, 22/12/24 | Definition of Honest Verifier Zero Knowledge (HVZK) and Special Soundness (SS) for canonical ID schemes. Proof that HVZK plus SS imply passive security. Canonical ID schemes from Discrete Log. | [1] 13 [2]: 12 [3]: 8 [7]: 6.2 |