Kobbi Nissim: Accessing Data while Preserving Privacy

Abstract:  We initiate a formal study of the privacy-efficiency tradeoff of secure database systems. Such systems allow storing data on a remote server and accessing it efficiently while maintaining the privacy of the stored data. While strong cryptographic tools (such as FHE, ORAM, SFE) can be used for this task, implementations of secure database systems also experiment with a combination of weaker primitives with the hope of striking a good privacy-efficiency tradeoff. We provide abstract models that capture the basic properties of secure database systems and identify their fundamental leakage channels. With these models we can provide an implementation independent investigation of their inherent security-efficiency tradeoffs and point to some inherent limitations. In particular, we provide generic reconstruction attacks where the server (or an eavesdropper on the communication line) recovers the secret attributes of records stored in the database.

We also present a new model of differentially private storage. We give a generic construction of differentially private storage that combines ORAM and differentially private sanitizers as well as more efficient constructions and lower bounds for the case where access pattern is revealed.

We have implemented some of our attacks and algorithms, and report on their efficiency.

Joint work with Georgios Kellaris, George Kollios, and Adam O'Neill