Data analytics is a core part of modern decision making, especially in public policy. However, there exists a tension between data privacy and otherwise socially beneficial analytics when data sources contain personal information. We design Synq, a system that supports analytics over encrypted data while accounting for the usability considerations institutions may have when conducting studies that affect public policy. We specifically use an application-centric approach and model Synq’s design requirements from a large-scale series of studies conducted on the opioid epidemic in Massachusetts. We systematize the design considerations of the public policy context and demonstrate how the combination of design considerations that Synq addresses is novel through a survey of the literature. We then present our protocol which combines structured encryption, somewhat homomorphic encryption, and oblivious pseudorandom functions to support a complex query language that includes filtering (retrieving rows by attribute/value pairs), linking (merging rows from different tables that represent the same individual) and aggregate functions (sum, count, average, variance, regression). We formally express the security of our protocol and show that Synq is efficient in practice while satisfying usability considerations that are critical to deployment in the setting of public policy studies.

Adversaries in cryptography have traditionally been modeled as either semi-honest or malicious. Over the years, however, several works have investigated the design of cryptographic protocols against rational adversaries. The most well-known example are covert adversaries in secure computation (Aumann & Lindell, TCC '07) which are adversaries that wish to deviate from the protocol but without being detected. Protocols secure against such covert adversaries guarantee that deviations are detected with probability at least - which is known as the deterrence factor.

Structured encryption (STE) schemes allow a client to store sensitive data on a semi-trusted remote server and query the data. STE schemes strike a balance between privacy and efficiency by leaking some information to the server. In particular, many STE schemes leak the volume pattern i.e., response lengths, and the query equality pattern i.e., if any queries are repeated. Recently discovered leakage-abuse attacks demonstrate that leaking the volume pattern can be unsafe; that is, the server can reconstruct parts of the database from this leakage. To address this leakage, Kamara and Moataz proposed a novel multi-map encryption scheme, AVLH, that hides query volumes by padding responses with parts of other responses (Eurocrypt 2019). AVLH was shown to be more storage-efficient than the naive approach to pad responses with dummy values to reach the maximum response length. Subsequently, Patel et al. provided an even more efficient volume-hiding multimap scheme, dprfMM (CCS 2019). Despite these advances, the costs of fully suppressing query volumes are still unclear. In this paper, we provide the first lower bounds on STE schemes for multi-maps that leak at most the query equality pattern. Surprisingly, we find that in many cases, such STE schemes cannot be more storage-efficient than naively padding to the maximum length.

New privacy laws like the European Union's General Data Protection Regulation (GDPR) require database administrators (DBAs) to identify all information related to an individual on request, e.g. , to return or delete it. This requires time-consuming manual labor today, particularly for legacy schemas and applications. In this paper, we investigate what it takes to provide mostly-automated tools that assist DBAs in GDPR-compliant data extraction for legacy databases. We find that a combination of techniques is needed to realize a tool that works for the databases of real-world applications, such as web applications, which may violate strict normal forms or encode data relationships in bespoke ways. Our tool, GDPRizer, relies on foreign keys, query logs that identify implied relationships, data-driven methods, and coarse-grained annotations provided by the DBA to extract an individual's data. In a case study with three popular web applications, GDPRizer achieves 100% precision and 96--100% recall. GDPRizer saves work compared to hand-written queries, and while manual verification of its outputs is required, GDPRizer simplifies privacy compliance.