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:
- $\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.
- $\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.
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.
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