In this talk, we will discuss the Columbia-Bell Labs project on scalable private database (DB) querying, work in part sponsored by Intelligence Advanced Research Project Activity (IARPA). We consider complete and scalable provable security of DB Management System, including access control, protection of the data, and, importantly, hiding the SQL query from the server, all while supporting a rich query set. We are restricted by severe performance requirements (10TB, 100M record DB, performance "just a little slower than an insecure DB").

We will present our approach, discuss its benefits and tradeoffs, and highlight some issues that arose in our efforts to achieve both provable security and scale.  One of our main tools is Yao SFE, and our private DB search algorithm represents a "practical circuit" that motivates improving SFE performance.  We will also report on experimental performance.

This talk is based on works with George Argyros, Steven M. Bellovin, Seung Geol Choi, Ben Fisch, Wesley George, Angelos Keromytis, Fernando Krell, Abi Kumarasubramanian, Tal Malkin, Vasilis Pappas and Binh Vo.