Accessing Data while Preserving Privacy
Adan O'Neill - Georgetown University
Wednesday, March 30, 2016, 1:00-2:00 pm 
Abstract
We initiate the rigorous study of the privacy-efficiency tradeoffs for secure outsourced database systems. Such systems, such as CryptDB (Popa et al., SOSP '11), try to mitigate the high cost of full-fledged cryptographic solutions by relaxing the security guarantees they provide. We introduce abstract models that capture the basic properties of these systems and the information they leak. These models allow performing a generic and implementation-independent investigation of the aforementioned tradeoffs.
For "optimally efficient'' outsourced database systems, we show generic reconstruction attacks in weak adversarial models, in which the server learns the secret attributes of every record stored in the database. This points to inherent limitations of such systems. However, we go on to present a new model of differentially private' outsourced database systems, where differential privacy is preserved even against an attacker that controls the data and the queries made to it. We show how to build on differentially private sanitizers (Blum et al., STOC '08) to achieve this. This shows that by slightly relaxing efficiency, one can achieve meaningful notions of privacy here.
Joint work with George Kellaris, George Kollios, and Kobbi Nissim.
This talk is organized by Jonathan Katz