Data Privacy and Security (Fall 2023)
Syllabus
The course is meant to cover an overview of modern techniques aimed at protecting data privacy and security in digital applications. Below is a tentative list of topics.Brush-up on Cryptography:
- Confidential communication, secret-key and public-key encryption.
- Authentic communication, cryptographic hashing, message authentication codes and digital signatures.
- Key exchange protocols and TLS.
- Cryptographic applications (authentication protocols, passwords, ...).
- Proofs of storage and proofs of retrievability.
- Verifiable computation.
- Privacy-preserving statistical databases.
- The Laplace mechanism and the exponential mechanism.
- Lower bounds.
- The Bitcoin protocol.
- Ethereum Smart contracts.
- Altcoins (Algorand, Cardano, ZCash, Spacemint).
- Two-party and multi-party computation.
- Yao's garbled circuits.
- MPC with honest majority.
Logistics
Important: The lectures are offered exclusively in-person (with no registration taking place).
Lecture time: Tuesday (15:00-17:00) and Thursday (12:00-15:00).Location: Room A2, Via Ariosto 25, 00185 Rome, Italy.
Twitter: @SapienzaCrypto.
Grading
Project (30%), oral exam (70%).Exams
The exam dates are as follows. Please, reserve a slot via INFOSTUD on time.Exam 1. Date: 09/01/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
Exam 2. Date: 06/02/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
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: 18/03/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
Exam 4. Date: 04/06/24. Time: 02:45pm. Room: Aula G29, Viale Regina Elena 295, Building G.
Exam 5. Date: 02/07/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
Exam 6. Date: 09/09/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
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: 14/10/24. Time: 09:00am. Room: Aula G29, Viale Regina Elena 295, Building G.
Course Slides
- Course info [pdf].
- Chapter 1: Secret-key cryptography [pdf].
- Chapter 2: Public-key cryptography [pdf].
- Chapter 3: Applications [pdf].
- Chapter 4: Big data and cloud cryptography [pdf].
- Chapter 5: Differential privacy [pdf].
- Chapter 6: Bitcoin [pdf].
- Chapter 7: Alternative currencies [pdf].
- Chapter 8: Secure Multiparty Computation [pdf].
References
While we will not follow a single book; the following sources are suggested as reference. However, only the material included in the slides will be part of the oral exam.- [1] Daniele Venturi. Crittografia nel Paese delle Meraviglie, Springer, Collana di Informatica, 2012.
- [2] Jonathan Katz, Yehuda Lindell. Introduction to Modern Cryptography, CRC Press, Second Edition, 2014.
- [3] Dan Boneh, Matthew Franklin. Identity-Based Encryption from the Weil Pairing, SIAM J. of Computing, Vol. 32, No. 3, 2003.
- [4] Jonathan Katz, Ji Sun Shin. Parallel and Concurrent Security of the HB and HB+ Protocols, EUROCRYPT 2006.
- [5] Hugo Krawczyk. SIGMA: The "SIGn-and-MAc" Approach to Authenticated Diffie-Hellman and its Use in the IKE Protocols, CRYPTO 2003.
- [6] Ari Juels, Thomas Ristenpart. Honey Encryption: Security Beyond the Brute-Force Bound, EUROCRYPT 2014.
- [7] Dan Boneh, Amit Sahai, Brent Waters. Functional Encryption: Definitions and Challenges, Theory of Cryptography Conference 2011.
- [8] Vipul Goyal, Omkant Pandey, Amit Sahai, Brent Waters. Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data, CCS 2006.
- [9] Shai Halevi. Homomorphic Encryption, Chapter 5 of Tutorials on the Foundations of Cryptography, Yehuda Lindell Ed., Springer, 2017.
- [10] Bryan Parno, Mariana Raykova, Vinod Vaikuntanathan. How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption, Theory of Cryptography Conference 2012.
- [11] Hovav Shacham, Brent Water. Compact Proofs of Retrievability, Journal of Cryptology 26(3): 442-483 (2013).
- [12] Salil Vadhan. The Complexity of Differential Privacy, Chapter 7 of Tutorials on the Foundations of Cryptography, Yehuda Lindell Ed., Springer, 2017.
- [13] Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, Bitcoin white paper.
- [14] Meni Rosenfeld. Analysis of Bitcoin Pooled Mining Reward Systems, CoRR abs/1112.4980, 2011.
- [15] Ittay Eyal, Emin Gun Sirer. Majority Is Not Enough: Bitcoin Mining Is Vulnerable, Financial Cryptography 2014.
- [16] Dongning Guo and Ling Ren. Bitcoin's Latency--Security Analysis Made Simple., ACM Advances in Financial Cryptography 2022.
- [17] Joseph Poon, Thaddeus Dryja. The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments, Lightning Network white paper, 2016.
- [18] Aggelos Kiayias, Alexander Russell, Bernardo David, Roman Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol, CRYPTO 2017.
- [19] Silvio Micali. Byzantine Agreement Made Simple, Innovations in Theoretical Computer Science 2017.
- [20] Jing Chen, Silvio Micali. Algorand, technical paper, 2017.
- [21] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, Krzysztof Pietrzak. Proofs of Space, CRYPTO 2015.
- [22] Sunoo Park, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel Alwen, Krzysztof Pietrzak. SpaceMint: A Cryptocurrency Based on Proofs of Space, Financial Cryptography 2018.
- [23] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin, IEEE Symposium on Security and Privacy, 2014.
- [24] Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols, Springer, 2010.
- [25] Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Lukasz Mazurek. Secure Multiparty Computations on Bitcoin, IEEE Symposium on Security and Privacy 2014.
- [26] Giuseppe Ateniese, Bernardo Magri, Daniele Venturi, Ewerton Andrade. Redactable Blockchain -- or -- Rewriting History in Bitcoin and Friends, IEEE European Symposium on Security and Privacy, 2017.
Students' Projects
As part of the exam, students are required to solve a small project and present the solution during the exam. The list of available projects is shown below; proposals for further projects are always welcome. In order to pick a project, it suffices to write me an email.List of Projects (By Topic)
The following is a good reference for solving some of the projects below using Python:Al Sweigart, Hacking Secret Ciphers with Python, Creative Commons, 2013.
- Secret-Key Cryptography:
- Inside Rijndael. The goal of this project is to gain a better understanding of the arithmetic in Rijndael's finite field (underlying the AES blockcipher). Write a program (using your favourite programming language) able to perform the basic operations in Rijndael's finite field, using the extended Euclidean algorithm for computing the multiplicative inverse of a polynomial. Next, use your program to re-generate the AES S-Boxes (for both encryption and decryption).
Ancient Ciphers. The goal of this project is to learn how to implement and break some of the blockciphers commonly used in the past. Write a program (using your favourite programming language) implementing encryption/decryption, as well as efficient attacks, on the following blockciphers: The Caesar Cipher, the Transposition Cipher, the Affine Cipher, and the Vigenere Cipher.
- Public-Key Cryptography:
Primality Testing. The goal of this project is to better understand the task of primality testing. Write a program (using your favourite programming language) implementing the following primality testing algorithms: The Fermat's Test and the Miller-Rabin Test. Compare the performances of the two tests.Inside RSA. The goal of this project is to better understand the number theory behind the RSA cryptosystem. Write programs (using your favourite programming language) for the following tasks: (i) Computing the gcd; (ii) Computing the modular multiplicative inverse (when it exists); (iii) Encryption/Decryption with Textbook RSA; (iv) Signature with Full-Domain Hash.
- Differential Privacy:
- Experiments with Differential Privacy. This project can be chosen by an arbitrary number of students, Implement some of the differentially private mechanisms studied in class (using any programming language of your choice), and apply it to solve a toy use case which is relevant for data science.
- Blockchain:
- Ethereumlab. Learn how to implement a secure smart contract. This project can be chosen by an arbitrary number of students, with the idea that each student should implement a different smart contract for a toy application of his/her choice. Reference: Remix.
- Secure Computation:
- SCAPI. Learn how to implement secure multiparty computation protocols (in java). This project can be chosen by an arbitrary number of students, with the idea that each student should implement a protocol for a different application of his/her choice. Reference: SCAPI: The Secure Computation Application Programming Interface.
- Bonus Topics:
- Steganography. The goal of this project is to get the basics about steganography and steganalysis. Write programs (using your favourite programming language) for the following tasks: (i) Encrypt/decrypt using the LSB algorithm; (ii) Encrypt/decrypt using JSteg; (iii) Steganalysis of JSteg; (iv) Steganalysis of LSB.
Announcements
25/09/2023: The course will start on September 26th, 2023.
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
Class/Date Topics Covered Readings Lecture 1, 26/09/23 Course info. The problem of message confidentiality. Symmetric encryption and perfect secrecy. One-time pad. Computational security and AES overview. [1]
[2]Lecture 2, 28/09/23 Modes of operation: ECB, CBC, CFB, OFB, and CTR. Semantic security and CPA security. [1]
[2]Lecture 3, 03/10/23 The problem of message authenticity. Message authentication codes and unforgeability. CBC-MAC. [1]
[2]Lecture 4, 05/10/23 Cryptographic hashing. Collision resistance and the Merkle-Damgaard construction. Hash-based MACs and HMAC. [1]
[2]Lecture 5, 10/10/23 SHA-3 and the sponge construction. Combining encryption and authentication. Authenticated encryption and CCA security. Encrypt-and-MAC, MAC-then-Encrypt and Encrypt-then-MAC. [1]
[2]Lecture 6, 12/10/23 One-way functions and Impagliazzo's worlds. Pseudorandom generators and application to secret-key encryption. [1]
[2]Lecture 7, 17/10/23 Pseudorandom functions and application to CPA secure encryption. The GGM tree. Pseudorandom permutations and Feistel networks. [1]
[2]Lecture 8, 19/10/23 Basic number theory: congruences modulo primes and composite numbers, Fermat's little theorem, primality testing, integer factorization and discrete logarithm. Public-key encryption and CPA/CCA security. [1]
[2]Lecture 9, 24/10/23 Textbook RSA encryption and its insecurity. The RSA assumption. RSA with padding, PKCS v#1.5. ElGamal public-key encryption. Diffie-Hellman assumptions (CDH and DDH). [1]
[2]Lecture 10, 26/10/23 Elliptic curve cryptography. Digital signatures. Signing with RSA and full-domain hash. [1]
[2]Lecture 11, 31/10/23 Public-key infrastructures. Web of trust. Identity-based encryption. IBE from pairings. [1]
[3]Lecture 12, 02/11/23 The problem of secure identification. The challenge-response paradigm. Identification schemes from symmetric and asymmetric cryptographic primitives. The HB family of protocols and the LPN assumption. [4] Lecture 13, 07/11/23 Key agreement protocols and the Diffie-Hellman key exchange. Passwords in cryptography and characterization of passwords entropy. Bloom filters. Password-based encryption and honey encryption. Encrypted Key Exchange (EKE) and possible instantiations. [1]
[2]
[5]
[6]Lecture 14, 09/11/23 TLS: History, RSA and DH modes of TLS 1.2, survey of attacks, and mentions to TLS 1.3. [7]
[8]Lecture 15, 14/11/23 Cryptography and big data: Functional Encryption (FE) and Attribute-Based Encryption (ABE). Outsourcing of computation in the cloud. Fully Homomorphic Encryption (FHE). Hardness of Learning with Errors. [9] Lecture 16, 16/11/23 The GSW FHE scheme. Bootstrapping and circular security. [10]
[11]Lecture 17, 21/11/23 Verifiable Computation (VC). VC with public delegatability and verifiability from ABE for formulas. [9] Lecture 18, 23/11/23 Constructing ABE from LWE. Cloud storage: Provable Data Possession and Proofs of Retrievability. [10]
[11]Lecture 19, 28/11/23 Differential privacy: Motivation, definition, and properties. Randomized responses and the Laplace mechanism. Approximate differential privacy and the Gaussian mechanism. [12] Lecture 20, 30/11/23 The exponential mechanism. Lower bounds on differentially private mechanisms. [12] Lecture 21, 05/12/23 Introduction to cryptocurrencies. Bitcoin: History and design principles. [13] Lecture 22, 07/12/23 Mining pools and attacks. Selfish mining. Eventual consensus and security of Bitcoin. [14]
[15]
[16]Lecture 23, 12/12/24 Smart contracts and applications. Payment channels. [17]
[18]Lecture 24, 19/12/24 Proof-of-stake blockchains. Ouroboros. Algorand. [19]
[20]