# Data Poisoning Attacks to Locally Differentially Private Range Query Protocols

arXiv: https://arxiv.org/abs/2503.03454 · HTML: https://mlsanity.com/paper/2503.03454/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Membership inference attacks, one of 12 directions in LLM safety and security.
- Builds on 22 of its 73 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Placed in

- LLM safety and security / [Membership inference attacks](https://mlsanity.com/safety/membership-inference-attacks/)

## Builds on (most cited first, 22 of 22)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Manipulation Attacks in Local Differential Privacy](https://mlsanity.com/paper/1909.09630/) (2019)
- [Data Poisoning Attacks to Local Differential Privacy Protocols](https://mlsanity.com/paper/1911.02046/) (2019)
- [Estimating Numerical Distributions under Local Differential Privacy](https://mlsanity.com/paper/1912.01051/) (2019)
- [LDPTrace: Locally Differentially Private Trajectory Synthesis](https://mlsanity.com/paper/2302.06180/) (2023)
- [Answering Range Queries Under Local Differential Privacy](https://mlsanity.com/paper/1812.10942/) (2018)
- [Locally Differentially Private Frequency Estimation with Consistency](https://mlsanity.com/paper/1905.08320/) (2019)
- [AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy](https://mlsanity.com/paper/2110.07505/) (2021)
- [Poisoning Attacks to Local Differential Privacy Protocols for Key-Value Data](https://mlsanity.com/paper/2111.11534/) (2021)
- [Fine-grained Poisoning Attack to Local Differential Privacy Protocols for Mean and Variance Estimation](https://mlsanity.com/paper/2205.11782/) (2022)
- [Real-World Trajectory Sharing with Local Differential Privacy](https://mlsanity.com/paper/2108.02084/) (2021)
- [Trajectory Data Collection with Local Differential Privacy](https://mlsanity.com/paper/2307.09339/) (2023)
- [On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks](https://mlsanity.com/paper/2403.19510/) (2024)
- [Real-Time Trajectory Synthesis with Local Differential Privacy](https://mlsanity.com/paper/2404.11450/) (2024)
- [Data Poisoning Attacks to Locally Differentially Private Frequent Itemset Mining Protocols](https://mlsanity.com/paper/2406.19466/) (2024)
- [Frequency-based Randomization for Guaranteeing Differential Privacy in Spatial Trajectories](https://mlsanity.com/paper/2207.03722/) (2022)
- [Answering Multi-Dimensional Range Queries under Local Differential Privacy](https://mlsanity.com/paper/2009.06538/) (2020)
- [LDPRecover: Recovering Frequencies from Poisoning Attacks against Local Differential Privacy](https://mlsanity.com/paper/2403.09351/) (2024)
- [Tourist route optimization in the context of Covid-19 pandemic](https://mlsanity.com/paper/2104.07663/) (2021)
- [PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy](https://mlsanity.com/paper/2407.13532/) (2024)

## Built on by (most cited first, 1 of 1)

- [Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2506.09803/) (2025)

## Abstract (arXiv)

Local Differential Privacy (LDP) has been widely adopted to protect user privacy in decentralized data collection. However, recent studies have revealed that LDP protocols are vulnerable to data poisoning attacks, where malicious users manipulate their reported data to distort aggregated results. In this work, we present the first study on data poisoning attacks targeting LDP range query protocols, focusing on both tree-based and grid-based approaches. We identify three key challenges in executing such attacks, including crafting consistent and effective fake data, maintaining data consistency across levels or grids, and preventing server detection. To address the first two challenges, we propose novel attack methods that are provably optimal, including a tree-based attack and a grid-based attack, designed to manipulate range query results with high effectiveness. Our key finding is that the common post-processing procedure, Norm-Sub, in LDP range query protocols can help the attacker massively amplify their attack effectiveness. In addition, we study a potential countermeasure, but also propose an adaptive attack capable of evading this defense to address the third challenge. We evaluate our methods through theoretical analysis and extensive experiments on synthetic and real-world datasets. Our results show that the proposed attacks can significantly amplify estimations for arbitrary range queries by manipulating a small fraction of users, providing 5-10x more influence than a normal user to the estimation.