Local Differential Privacy for Belief Functions

Qiyu Li, Chunlai Zhou, Biao Qin, Zhiqiang Xu

Abstract

Traditional Local Differential Privacy (LDP) mechanisms often force users to choose between telling the truth or lying, which can lead to non-compliance or refusal to respond. This paper introduces a novel theoretical framework for LDP using Belief Functions (Dempster-Shafer Theory). By formally incorporating "don't know" or non-response states, the proposed models maintain rigorous privacy guarantees while potentially improving data utility and user participation.

Introduction

Local Differential Privacy (LDP) is the gold standard for collecting aggregate statistics while protecting individual privacy. However, the classic "randomized response" mechanism presents a human-centric flaw: users who are uncomfortable with a "truth-or-lie" protocol often refuse to respond or provide non-compliant data. This research addresses this gap by using Dempster-Shafer Theory (DST), a mathematical framework designed specifically to represent ignorance and evidence, allowing users to express uncertainty rather than forcing them to lie.

Methodology

The authors introduce two distinct flavors of LDP based on different interpretations of belief functions:

  1. $\epsilon$-SLDP (Shafer LDP): Based on Shafer’s semantics of "randomly coded messages," this generalizes Warner’s randomized response by adding a third option: answering "don't know" with a specific probability.
  2. $\epsilon$-WLDP (Walley LDP): Utilizing the "imprecise probability" perspective, this defines privacy by the worst-case ratio of likelihoods across all distributions consistent with a belief function.

Both definitions are shown to be "well-behaved," satisfying core differential privacy properties such as composition and post-processing.

Key Insights

  • Ignorance as a Valid State: Unlike standard probability where outcomes must sum to one, belief functions allow for a "third probability" of "don't know," providing a middle ground for complex statistical systems.
  • The Utility of Uncertainty: Within a fixed privacy budget ($\epsilon$), a mechanism can achieve higher estimation accuracy by allowing users to say "don't know" instead of forcing them to lie.
  • Generalizing the Classics: The framework shows that traditional 1965 Randomized Response models are special "Bayesian" cases where the probability of ignorance is set to zero.

Results and Discussion

The authors validated their theorems using simulated data for discrete distribution estimation, comparing a $2 \times 3$ (Truth, Lie, Don't Know) mechanism against the traditional $2 \times 2$ Warner model.

Privacy-utility trade-off curves for different belief function parameters.

As illustrated in Figure 2, the privacy-utility trade-off curve shifts as the probability of "don't know" increases. While the standard Warner model is mathematically optimal for a given $\epsilon$, the belief-function model is more robust to real-world non-compliance.

Convergence of MLE estimators for traditional Warner (W-RR) and the proposed belief-function models across varying sample sizes.

Experimental results (Figure 5) demonstrate that the "don't know" mechanisms remain stable and predictable even at smaller scales. While larger sample sizes reduce variance as expected, the Maximum Likelihood Estimators (MLE) for the proposed models converge effectively across sample sizes ranging from $N=10$ to $N=1000$.

Conclusion

By moving beyond standard probability theory, this work provides a formal way to handle non-responses in privacy-preserving data collection. While scaling to high-dimensional data remains a challenge, the framework offers a promising path toward more human-centric LDP. Future work will explore empirical user willingness to participate and the asymptotic behavior of these mechanisms.

Summary updated

Abstract

In this paper, we propose two new definitions of local differential privacy for belief functions. One is based on Shafer’s semantics of randomly coded messages and the other from the perspective of imprecise probabilities. We show that such basic properties as composition and post-processing also hold for our new definitions. Moreover, we provide a hypothesis testing framework for these definitions and study the effect of "don’t know" in the trade-off between privacy and utility in discrete distribution estimation.
BibTeX
@inproceedings{li2022local,
  author = {Qiyu Li and Chunlai Zhou and Biao Qin and Zhiqiang Xu},
  title = {{Local Differential Privacy for Belief Functions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21241},
}
Figure