Practical and privacy-preserving information retrieval from a database table

Abstract

We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for a client’s query-based access. We propose a cryptographic model for the study of such protocols, by expanding previous well-studied models of keyword search and private information retrieval to incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table.

Our first result is a 2-party private database retrieval protocol. This is the first protocol that preserves query and data privacy on such a practical data model. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size.

Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal ‘access pattern’ information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol’s runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL. This is the first protocol that achieves privacy of database and query content with practical performance.

Finally, we show a second private database retrieval protocol in the 3-party model for which we can show that no unintended information is leaked to an adversary corrupting both clients and third parties, at an only constant additional performance overhead cost.