TL;DR
This paper tackles the challenge of providing privacy-preserving answers to aggregate queries on sensitive datasets. It introduces a novel technique that enforces "epsilon-differential privacy" with improved efficiency and a query relaxation mechanism, allowing more queries to be answered without compromising privacy guarantees.
What Problem Does This Paper Address?
Organizations often collect sensitive personal data (like medical records or transaction histories) and need to share it for research or analysis. However, releasing this data directly risks individual privacy. Statistical databases aim to solve this by answering aggregate queries (e.g., "how many people earn over $50k?") in a way that protects privacy. A leading approach is "output perturbation," which adds noise to query results. While effective, the state-of-the-art "epsilon-differential privacy" has two major drawbacks: it's computationally expensive to verify privacy, and it can only answer a limited number of queries before needing to shut down. This paper addresses these limitations by developing a more efficient method for enforcing epsilon-differential privacy and introducing a "query relaxation" mechanism to handle denied queries gracefully.
Methods
The core of the paper's contribution lies in two main areas:
- Efficient Epsilon-Differential Privacy Verification: The authors prove that exactly computing "L1 sensitivity" (a crucial metric for epsilon-differential privacy) is NP-hard. This implies that efficiently verifying privacy for arbitrary queries is impossible. To overcome this, they propose a 2-approximate upper bound for L1 sensitivity, enabling a fast and conservative approach to privacy verification. This means the system will always err on the side of caution, denying a query if there's any doubt about privacy.
- Query Relaxation Mechanism: When a query is denied due to privacy concerns, instead of simply returning nothing (which leads to a poor user experience and requires users to repeatedly rephrase queries), the system offers a synthetic answer. This synthetic answer is derived from the results of previously accepted queries. The paper introduces a "compound" mechanism, which intelligently combines accepted queries to construct a rectangular region similar to the denied query's region. This allows for more useful responses to denied queries. They also introduce "artificial patches" to further improve the accuracy of these synthetic answers.
Datasets
The paper uses a real dataset called CENSUS with one million tuples for evaluation. This dataset contains information on American individuals with four attributes: Age, Education, Occupation, and Income.
Key Insights and Ideas
- NP-Hardness of Exact L1 Sensitivity: The theoretical proof that exact L1 sensitivity computation is NP-hard is a significant finding, explaining why a perfect, efficient privacy checker for arbitrary queries is unlikely.
- The Power of Approximation: The development of a 2-approximate upper bound for L1 sensitivity is a practical workaround, enabling efficient and safe privacy enforcement.
- Query Relaxation as a User-Centric Solution: The query relaxation mechanism is a key innovation that significantly improves the usability of privacy-preserving databases by providing meaningful answers even for denied queries. This addresses a major practical drawback of existing methods.
- Trade-off Between Accuracy and Privacy: The paper highlights the inherent trade-off between query accuracy (via relaxation) and privacy guarantees, controlled by parameters like compound size.
Key Results
- Improved Processing Capacity: The proposed histogram approach significantly increases the number of queries that can be answered compared to existing methods, especially for uniform query workloads. For instance, with a histogram size of 10^5, the processing capacity approaches the theoretical upper bound.
- Effective Query Relaxation: Experiments show that the query relaxation mechanism produces synthetic answers with very low relaxation error (meaning the synthetic answer's region closely matches the original query's region) and small compound sizes, indicating low variance in the synthetic answers.
- Manageable Computation Overhead: While computation time increases with parameters like epsilon (ε) and histogram size (θ), the overhead remains manageable, demonstrating the practical feasibility of the approach.
Limitations and Future Work
- Limitations of Output Perturbation: The paper acknowledges that output perturbation, even with their improvements, still involves adding noise, which inherently limits the accuracy of answers. The theoretical results also suggest that for very large datasets, accurate answers might be impossible to guarantee with strong privacy.
- Future Work: The authors suggest several avenues for future research:
- Extending the techniques to support other aggregate queries beyond count queries (e.g., SUM, MIN, MAX).
- Investigating scenarios with data updates (insertions and deletions).
- Adapting the methods for different data structures beyond relational tables, such as social networks or spatial data.
Summary updated