Practical and Privacy-Preserving Policy Compliance for Outsourced Data

Abstract. We consider a scenario for data outsourcing that supports performing database queries in the following three-party model: a client interested in mak-ing database queries, a data owner providing its database for client access, and a server (e.g., a cloud server) holding the (encrypted) outsourced data and helping both other parties. In this scenario, a natural problem is that of designing efficient and privacy-preserving protocols for checking compliance of a client’s queries to the data owner’s query compliance policy. We propose a cryptographic model for the study of such protocols, defined so that they can compose with an underlying database retrieval protocol (with no query compliance policy) in the same partic-ipant model. Our main result is a set of new protocols that satisfy a combination of natural correctness, privacy, and efficiency requirements. Technical contribu-tions of independent interest include the use of equality-preserving encryption to produce highly practical symmetric-cryptography protocols (i.e., two orders of magnitude faster than “Yao-like ” protocols), and the use of a query rewriting technique that maintains privacy of the compliance result.