University of Toledo
Query privacy in secure DBMS is an important feature, although rarely formally considered outside the theoretical community. Because of the high overheads of guaranteeing privacy in complex queries, almost all previous papers addressing practical applications consider limited queries (e.g., just keyword search), or provide a weak guarantee of privacy. In this paper, the authors address a major open problem in private DB: efficient sub-linear search for arbitrary Boolean queries. They consider scalable DBMS with provable security for all parties, including protection of the data from both server (who stores encrypted data) and client (who searches it), as well as protection of the query, and access control for the query.