Teaching

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: You may also find useful the following lecture notes from a past edition of the course (although not reviewed by myself):

Exams

Exam 1. Date: 11/01/24. Aula 1 (RM018). Time: 09:00-12:00. Scores [pdf].
Exam 2. Date: 07/02/24. Aula 1 (RM018). Time: 09:00-12: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: 08/04/24. Aula: 2L (Via del Castro Laurenziano 7a). Time: 09:30-12:30. Scores [pdf].
Exam 4. Date: 05/06/24. Aula TBA. Time: TBA. Scores [pdf].
Exam 5. Date: 05/07/24. Aula TBA. Time: TBA. Scores [pdf].
Exam 6. Date: 10/09/24. Aula TBA. Time: TBA. 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
© 2010 Daniele Venturi
Design: COSIC Webteam | Content: Daniele Venturi
Thanks for visiting :-)