Optimizing Query Times for Multiple Users Scenario of Differential Privacy

Wen Huang, Shijie Zhou, Yongjian Liao, Ming ZhuoIEEE Access 2019 · OpenReview

Introduction

In the field of Differential Privacy (DP), every query to a database "leaks" a small amount of information, consuming a portion of a finite privacy budget ($\epsilon$). Once this budget is exhausted, no further queries can be answered without risking the exposure of individual records. While standard DP mechanisms work well for single-user scenarios, they face significant hurdles in multi-user environments.

Multi-user Differential Privacy Architecture

The authors identify two major challenges in multi-user settings:

  1. The Long Tail Effect: As the number of users grows, the diversity of unique queries increases, leading to rapid budget exhaustion across the system.
  2. Conspiracy Attacks: Standard DP mechanisms typically add noise with a mean of zero. If several malicious users ask the same question and pool their results, the Law of Large Numbers allows them to average out the noise and pinpoint the true, private data value.

Current industry standards used by major technology firms struggle to balance high data utility with robust protection against these collaborative attacks. This paper proposes a novel approach to mitigate these risks while optimizing query capacity.

Proposed Mechanism: Non-Zero Mean Laplace Noise

The authors introduce Algorithm 1: Mechanism A, which departs from the common practice of using Laplace noise with a mean of zero. The core innovation lies in User Isolation through unique noise profiles.

Instead of a global noise profile, the system assigns each user $i$ a unique location parameter ($\mu_i$) randomly chosen from a specific interval $[a, b]$. Queries are then answered by adding noise drawn from a Laplace distribution: $Lap(\frac{k\Delta D}{\epsilon}, \mu_i)$.

Because each user's noise is centered around a different non-zero value, they cannot simply average their results to find the truth. The paper provides formal proofs that this mechanism still satisfies $\epsilon$-differential privacy. The researchers utilized KL-Divergence to measure the distortion of the original data distribution and the Central Limit Theorem to calculate the increased difficulty for malicious users attempting to break the system.

Experimental Evaluation

The researchers evaluated Mechanism A using two primary sources:

  • The Iris Dataset: A classic benchmark in machine learning, used to test how non-zero mean noise affects the accuracy of a logistic regression model.
  • Relational Database Simulation: A complex schema involving thousands of records (orders, products, customers) was used to test the mechanism against FLEX, an open-source platform for DP SQL queries.

Key Results

  • Resistance to Conspiracy: In standard mean-zero practices, a group of users can reach a 99% confidence interval of the true answer relatively easily. Mechanism A ensures that even if users work together, their estimation converges to $r + \hat{m}$ (where $\hat{m}$ is the average of their assigned means) rather than the true value $r$.
  • Utility in Machine Learning: Experiments on the Iris dataset showed that the accuracy of a logistic regression model remained stable even as the location parameter (the mean of the noise) was shifted. Accuracy primarily scaled with the privacy budget $\epsilon$, not the specific mean assigned to the user.
  • Query Optimization: The proposed mechanism allows for a "long tail" of unique queries across multiple users without the exponential budget decay seen in standard Laplace mechanisms.

Discussion and Insights

The most significant insight of this work is that breaking the zero-mean paradigm does not break the privacy guarantee, but it does break the mathematical assumptions that malicious collaborators rely on. By isolating users with different means, the total privacy budget does not need to increase linearly with the number of users, allowing the system to handle significantly more queries.

While the method maintains the shape of data distributions (crucial for statistical analysis and machine learning), the authors acknowledge that for a single user, the proposed mechanism will incur "bigger noise" (higher absolute error) compared to the standard mean-zero approach for the same level of probability. Future work will involve developing definitive guides for choosing the optimal interval $[a, b]$ for noise means based on specific data sensitivity and testing the mechanism on higher-dimensional datasets.

Summary updated

Abstract

Differential privacy is the state-of-the-art for preserving privacy and differential privacy mechanism based on Laplace distribution with mean 0 is common practice. However, privacy budget is exhausted so quick that the number of queries is not enough. In this paper, a differential privacy mechanism is proposed to optimize the number of queries for application scenario of multiple users. We isolate different users by assigning various noise distribution with non-zero mean to different users. First, in terms of privacy guarantee, the proposed mechanism is better than common practice. Second, for the utility aspect, the accuracy of proposed mechanism is analyzed from the view of data distribution's distortion and the view of noise's absolute value.
BibTeX
@inproceedings{huang2019optimizing,
  author = {Wen Huang and Shijie Zhou and Yongjian Liao and Ming Zhuo},
  title = {{Optimizing Query Times for Multiple Users Scenario of Differential Privacy}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=8FnDNnqnR0},
}
Figure