Consider a client who wishes to outsource database storage to a cloud service. As her privacy and the service’s liability are key concerns (e.g., for medical data), she ought to first encrypt her data under a key unknown to the server. However, standard encryption schemes hide all information about the data and would not allow the service to provide any useful search functionality to the client. To address this, we propose a new framework of “efficiently searchable encryption’’ that balances two seemingly-contradictory goals: (1) allowing efficient search (nearly the same efficiency as for unencrypted data), and (2) meeting strong and rigorous security models. My talk will specifically focus on applying our framework to support range queries over encrypted data using order-preserving encryption (OPE), a concept introduced in the database community (Agrawal et al., SIGMOD ‘04). We propose the first rigorous security model that an OPE scheme should achieve. We then show how to construct a highly practical OPE scheme achieving it by using a sampling algorithm for the hypergeometric distribution. We then explain why, curiously, we still do not obtain a good understanding of the data privacy our ``secure’’ OPE scheme provides, and present some additional security models and results to address this. In the end, we get an essentially complete characterization of the data privacy our scheme provides. We conclude by discussing some future directions.
Speaker Biography
Adam O’Neill received his Ph.D. in Computer Science from the Georgia Institute of Technology in 2010 (with Alexandra Boldyreva). Since then, he has held postdoctoral research appointments at the University of Texas at Austin (with Brent Waters) and at Boston University (with Ran Canetti and Leonid Reyzin), where he is currently employed. His research is in cryptography, with a focus on resolving the tension between theory and practice.