CS848: Topics in Encryption in Databases, Machine Learning and Distributed Systems
- Instructor: Florian Kerschbaum (office hours by appointment)
- Lectures: Tuesday 3:00pm - 5:20pm (DC2568)
- Schedule (requires authentication)
This course is about how to operate computer programs, such as databases, machine learning algorithms and distributed systems on encrypted data.
We will study the properties of cryptographic algorithms and protocols and how they can be used in these systems.
This is not only an exercise in cryptography, but also needs to consider the systems aspects in order to balance performance, security and functionality.
The goal is to study practical systems that run over encrypted data and leak as little information as possible.
Cryptographic techniques will include multi-party computation protocols, homomorphic, functional, searchable and property-preserving encryption schemes.
We will also look at inferences from the result of the computation and consider techniques such as differential privacy.
The systems we study include database management systems, machine learning algorithms and blockchains.
Students should be familiar with basic crypto (public/secret key encryption, hash functions, etc.). No additional "advanced" math or crypto knowledge is required to take the course.
The instructor will give an introduction to the cryptographic techniques used in the reading assignments in the first two lectures.
Students should also be familiar with undergrad CS topics such as database systems, data mining, neural networks, etc.
The course is currently listed in the database area. It may be possible to count it as an algorithms course under some conditions, if desired.
Suggested Reading List
Encrypted Databases and Search over Encrypted Data
Attacks on Searchable and Order-Preserving Encryption
- Raluca A. Popa, Catherine M. S. Redfield, Nickolai Zeldovich, Hari Balakrishnan: CryptDB: protecting confidentiality with encrypted query processing
- Reza Curtmola, Juan A. Garay, Seny Kamara, Rafail Ostrovsky: Searchable symmetric encryption: improved definitions and efficient constructions
- David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, Michael Steiner: Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation
- Benjamin Fuller, Mayank Varia, Arkady Yerukhimovich, Emily Shen, Ariel Hamlin, Vijay Gadepally, Richard Shay, John Darby Mitchell, Robert K. Cunningham: SoK: Cryptographically Protected Database Search
- Florian Kerschbaum: Frequency-Hiding Order-Preserving Encryption
- Kevin Lewi, David J. Wu: Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds
- Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel N. Kho, Jennie Rogers: SMCQL: Secure Query Processing for Private Data Networks
- Ioannis Demertzis, Stavros Papadopoulos, Odysseas Papapetrou, Antonios Deligiannakis, Minos N. Garofalakis: Practical Private Range Search Revisited
- Florian Hahn, Florian Kerschbaum: Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage
Attacks on Machine Learning
- Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, Thomas Ristenpart: Leakage-Abuse Attacks against Order-Revealing Encryption
- F. Betül Durak, Thomas M. DuBuisson, David Cash: What Else is Revealed by Order-Revealing Encryption?
- Georgios Kellaris, George Kollios, Kobbi Nissim, Adam O'Neill: Generic Attacks on Secure Outsourced Databases
- Yupeng Zhang, Jonathan Katz, Charalampos Papamanthou: All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption
- Liang Wang, Paul Grubbs, Jiahui Lu, Vincent Bindschaedler, David Cash, Thomas Ristenpart: Side-Channel Attacks on Shared Search Indexes
Encrypted Machine Learning
- Nicolas Papernot, Patrick D. McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, Ananthram Swami: The Limitations of Deep Learning in Adversarial Settings
- Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, Thomas Ristenpart: Privacy in Pharmacogenetics: An End-to-End Case Study of Personalized Warfarin Dosing
- Reza Shokri, Marco Stronati, Congzheng Song, Vitaly Shmatikov: Membership Inference Attacks Against Machine Learning Models
Privacy on the Blockchain
- Raphael Bost, Raluca Ada Popa, Stephen Tu, Shafi Goldwasser: Machine Learning Classification over Encrypted Data
- Yehuda Lindell, Benny Pinkas: Secure Multiparty Computation for Privacy-Preserving Data Mining
- Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin E. Lauter, Michael Naehrig, John Wernsing: CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy
- Nicolas Papernot, Patrick D. McDaniel, Xi Wu, Somesh Jha, Ananthram Swami: Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks
- Nicholas Carlini, David A. Wagner: Towards Evaluating the Robustness of Neural Networks
- Martin Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, Li Zhang: Deep Learning with Differential Privacy
General Encrypted Computations
- Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza: Zerocash: Decentralized Anonymous Payments from Bitcoin
- Ethan Cecchetti, Fan Zhang, Yan Ji, Ahmed E. Kosba, Ari Juels, Elaine Shi: Solidus: Confidential Distributed Ledger Transactions via PVORM
- Ahmed E. Kosba, Andrew Miller, Elaine Shi, Zikai Wen, Charalampos Papamanthou: Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts
- Guy Zyskind, Oz Nathan, Alex Pentland: Enigma: Decentralized Computation Platform with Guaranteed Privacy
- Jia Liu, Saqib A. Kakvi, Bogdan Warinschi: Extractable Witness Encryption and Timed-Release Encryption from Bitcoin
- Aseem Rastogi, Piotr Mardziel, Michael Hicks, Matthew A. Hammer: Knowledge inference for optimizing secure multi-party computation
- Andrew Miller, Michael Hicks, Jonathan Katz, Elaine Shi: Authenticated data structures, generically
- S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis: Secure two-party computation in sublinear (amortized) time
- Daniel Demmler, Thomas Schneider, Michael Zohner: ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation
- David W. Archer, Dan Bogdanov, Benny Pinkas, Pille Pullonen: Maturity and Performance of Programmable Secure Computation
- Ivan Damgard, Kasper Damgard, Kurt Nielsen, Peter Sebastian Nordholt, Tomas Toft: Confidential Benchmarking based on Multiparty Computation
- Dan Bogdanov, Liina Kamm, Baldur Kubo, Reimo Rebane, Ville Sokk, Riivo Talviste: Students and Taxes: a Privacy-Preserving Study Using Secure Computation
- Ulfar Erlingsson, Vasyl Pihur, Aleksandra Korolova: RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response