Title: Towards Practical Differential Privacy for SQL Queries,
Abstract: Differential privacy promises to enable general data analytics while
protecting individual privacy, but existing differential privacy mechanisms do
not support the wide variety of features and databases used in real-world
SQL-based analytics systems.
This paper presents the first practical approach for differential privacy of
SQL queries. Using 8.1 million real-world queries, we conduct an empirical
study to determine the requirements for practical differential privacy, and
discuss limitations of previous approaches in light of these requirements. To
meet these requirements we propose elastic sensitivity, a novel method for
approximating the local sensitivity of queries with general equijoins. We prove
that elastic sensitivity is an upper bound on local sensitivity and can
therefore be used to enforce differential privacy using any local
sensitivity-based mechanism.
We build FLEX, a practical end-to-end system to enforce differential privacy
for SQL queries using elastic sensitivity. We demonstrate that FLEX is
compatible with any existing database, can enforce differential privacy for
real-world SQL queries, and incurs negligible (0.03%) performance overhead.