Local Differential Privacy Meets Computational Social Choice - Resilience under Voter Deletion

Liangde Tao, Lin Chen, Lei Xu, Weidong ShiIJCAI 2022 · DOI

TL;DR

This paper introduces a novel metric, PoLDP, to quantify how local differential privacy (LDP) mechanisms can enhance the resilience of voting systems against manipulation through voter deletion. The authors demonstrate that LDP generally increases the cost of manipulation, making voting systems more robust, and provide guidance on choosing LDP parameters for optimal protection.

What Problem Does This Paper Address?

In computational social choice, a significant concern is the vulnerability of voting systems to manipulation. A common attack involves an adversary learning voters' true preferences (e.g., through pre-election polls) and then strategically deleting voters to influence the election outcome. This is particularly problematic for simple, widely used rules like plurality. This paper addresses the question of whether adopting local differential privacy (LDP) mechanisms, which obscure individual voter preferences in polls, can significantly mitigate these manipulation attacks and make voting systems more secure.

Methods

The core contribution is the introduction of the PoLDP (Power of LDP) metric, defined as the ratio of the expected manipulation cost under an LDP mechanism to the manipulation cost without LDP. A PoLDP greater than 1 indicates that LDP enhances resilience.

The authors model the voting system with $n$ voters and $m$ candidates. They consider an attacker who wants to make a specific candidate win by deleting voters. The key difference introduced by LDP is that the attacker only observes reported preferences from polls, not the true preferences.

To quantify manipulation costs, they employ integer linear programming (ILP) to find the minimal number of voters to delete for a desired winning probability. They then define the expected manipulation cost under LDP by averaging over all possible "realizations" of reported preferences generated by the LDP mechanism.

A crucial concept is the APoLDP (Asymptotic PoLDP), which represents the PoLDP for a large number of voters ($n \to \infty$). This asymptotic analysis simplifies the problem and allows for more generalizable results. They derive theorems relating APoLDP to the LDP privacy parameter ($\epsilon$) and the voting system's structure.

Two fundamental LDP mechanisms are analyzed:

  • Randomized Response: A classic LDP technique where a voter's response is randomized.
  • Laplace Mechanism: Another common LDP mechanism that adds Laplace noise to the reported value.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulated experiments.

Key Insights and Ideas

  • LDP as a Shield: LDP mechanisms fundamentally increase the attacker's uncertainty about true voter preferences, making manipulation significantly harder and more costly.
  • PoLDP as a Quantifier: The PoLDP metric provides a clear, quantitative way to measure the resilience improvement offered by LDP. A higher PoLDP means greater robustness.
  • Asymptotic Analysis is Key: The APoLDP simplifies analysis for large populations, revealing general trends in how LDP affects manipulation costs.
  • Privacy vs. Security Trade-off (Subtle): While LDP enhances privacy, the paper shows that for voter deletion attacks, there's a "security threshold" for the privacy parameter $\epsilon$. Beyond this threshold, increasing privacy (decreasing $\epsilon$) doesn't necessarily provide more resilience against this specific attack, suggesting that overly strong privacy might be redundant for this threat model.
  • Laplace vs. Randomized Response: Experimental results suggest that the Laplace mechanism generally offers better resilience (higher PoLDP) than randomized response for the tested scenarios.

Key Results

  • General Resilience Improvement: The paper demonstrates that LDP mechanisms, specifically randomized response and Laplace, generally enhance the resilience of voting systems against voter deletion attacks.
  • APoLDP Characterization: For two-candidate elections, closed-form expressions for APoLDP are derived for both randomized response and Laplace mechanisms, showing their dependence on the privacy parameter $\epsilon$.
  • Multi-candidate Complexity: For multiple candidates, deriving closed-form APoLDP is complex, but the paper analyzes its maximal value and the range of $\epsilon$ that achieves it.
  • Experimental Validation: Numerical experiments on simulated voting systems confirm that LDP mechanisms increase manipulation costs, with Laplace generally outperforming randomized response. The experiments also show that PoLDP is relatively stable across different winning probability requirements.

Limitations and Future Work

  • Specific Attack Model: The study focuses exclusively on the "voter deletion" attack. Other manipulation strategies (e.g., bribery, strategic nomination) are not considered.
  • Assumptions: The analysis relies on assumptions common in computational social choice, such as voters having fixed true preferences and the attacker knowing the distribution of true preferences (though not individual ones under LDP).
  • Real-world Data: While experiments use simulated data, the paper could benefit from evaluation on real-world voting datasets.
  • Future Work: The authors suggest exploring other LDP mechanisms, different attack models, and more complex voting rules. Investigating the practical implementation challenges of LDP in large-scale voting systems is also a promising direction.

Summary updated

BibTeX
@inproceedings{tao2022local,
  author = {Liangde Tao and Lin Chen and Lei Xu and Weidong Shi},
  title = {{Local Differential Privacy Meets Computational Social Choice - Resilience under Voter Deletion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/547},
}
Figure