Defense against Poisoning Attacks under Shuffle-DP DOI: 10.1145/3786638 Journal: PACMMOD Volume: 4 1 (SIGMOD) 24 2 CCS: Security and privacy Database and storage security CCS: Information systems Data management systems
Siyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang, Quanqing Xu, Chuanhui Yang, Zhan Qin, Kui Ren, Wei Dong · 2026
Read Defense against Poisoning Attacks under Shuffle-DP DOI: 10.1145/3786638 Journal: PACMMOD Volume: 4 1 (SIGMOD) 24 2 CCS: Security and privacy Database and storage security CCS: Information systems Data management systems by Siyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang, Quanqing Xu, Chuanhui Yang, Zhan Qin, Kui Ren, Wei Dong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00625.txt.
Introduction
Siyi Wang and 8 co-authors defend the private study of data against users who poison the data. The shuffle model of differential privacy, where reports are shuffled before study, strikes a balance of privacy and use. Its protocols, however, assume every user behaves honestly. Hostile users can poison reports, harming privacy promises and answer accuracy; earlier shields covered only frequency checks.
The authors present the first general defense framework for union-kind queries, turning any shuffle protocol into one that stands up to poisoning. With no attack, its error matches the first one's as data grows. With a constant number of attackers, the error grows only slowly, by a log factor. They show it on summation, frequency counting, and range counting. Tests confirm answers stay strong and message cost stays low under attack, giving the shuffle model a defense as broad as itself.
Catalog record
| CREATOR | Siyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang, Quanqing Xu, Chuanhui Yang, Zhan Qin, Kui Ren, Wei Dong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00625
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Defense against Poisoning Attacks under Shuffle-DP DOI: 10.1145/3786638 Journal: PACMMOD Volume: 4 1 (SIGMOD) 24 2 CCS: Security and privacy Database and storage security CCS: Information systems Data management systems Siyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang, Quanqing Xu, Chuanhui Yang, Zhan Qin, Kui Ren, Wei Dong Abstract . Differential Privacy (DP) has become the gold standard for protecting individual privacy in data analytics, and the shuffle-DP model has attracted significant attention from both academia and industry due to its favorable balance between privacy and utility. However, existing shuffle-DP protocols rely on a strong assumption: all users behave honestly. In real-world scenarios, adversarial users can exploit this vulnerability through poisoning attacks, compromising both privacy guarantees and the utility of analytical results. While defending against poisoning attacks in the shuffle-DP model has recently gained interest, existing solutions are limited to frequency estimation tasks. To address this issue, we propose the first general defense framework for all union-preserving queries, capable of transforming any shuffle-DP protocol into a version resilient to poisoning attacks. Beyond robust defense against poisoning attacks, our framework achieves high utility of analytical results. Compared to the original shuffle-DP protocol, it retains asymptotically equivalent error in attack-free settings and incurs only a polylogarithmic increase in error when a constant number of attackers are present. We demonstrate the generality of our framework on several common queries, including summation, frequency estimation, and range counting. Experimental results confirm that our approach effectively defends against poisoning attacks while maintaining strong utility and communication efficiency. † † cc-license: by 1. Introduction A key challenge in data analytics is to obtain meaningful insights while preserving privacy. Differential privacy (DP) ( 23 ) , the gold standard for private data analysis, achieves this by adding noise to query results, preventing inference of individual data. Traditional DP model assumes a trusted curator who collects data and privatizes results before release, known as central-DP . However, real-world scenarios often lack a universally trusted curator, leading to the adoption of local-DP ( 40 ) , where users privatize data locally before sharing it. Although local-DP offers stronger privacy guarantees, it incurs higher errors. For instance, in bit counting, central-DP achieves an error of O(1/\varepsilon) by adding Laplace noise of scale 1/\varepsilon ( 23 ) , where \varepsilon is a privacy budget to control the privacy loss (see Section 2 for more details). In contrast, the optimal error under local-DP has been proven to be O(\sqrt{n}/\varepsilon) ( 5 ; 10 ) . To balance privacy and utility, shuffle-DP ( 8 ; 14 ; 2 ; 25 ) was introduced, leveraging a trusted shuffler to anonymize user messages before analysis. The process consists of three steps: (1) Each user privatizes its own data using a randomizer \mathcal{R}(\cdot) . (2) A trusted shuffler \mathcal{S} collects all users’ responses, randomly permutes them, and passes them to a potentially untrusted analyzer \mathcal{A} . (3) The analyzer conducts further analysis. By introducing additional randomness through shuffling, shuffle-DP reduces the required noise per user, thus improving utility. In bit counting, each user adds only O(1/n\varepsilon) extra noise ( 28 ) , which leads to a total error of O(1/\varepsilon) and matches the central-DP error. However, unlike central-DP which places all trust in the analyzer, shuffle-DP only requires a trusted shuffler, which can be easily implemented via anonymous communication channels (e.g., mix networks ( 11 ; 19 ) , onion routing ( 52 ; 20 ) ) or trusted nodes/hardware ( 53 ; 8 ) ). Due to its strong privacy-utility trade-off, shuffle-DP has been widely studied in fundamental problems such as sum aggregation ( 28 ; 3 ; 30 ) , frequency estimation ( 47 ; 29 ; 27 ; 16 ) , distinct counting ( 13 ) , as well as in advanced problems such as triangle counting ( 36 ) . 1.1. Poisoning Attack However, traditional shuffle-DP protocols rely on a strong, often implicit trust assumption: while the analyzer may be adversarial, all users are honest and faithfully follow the protocol. This setting does not always align with real-world scenarios. In practice, some users themselves might act maliciously, aiming to disrupt the shuffle-DP protocol. The adversarial behavior is known as poisoning attack ( 4 ; 15 ) . More precisely, a poisoning attacker corrupts some users in the protocol and acts maliciously with two primary objectives: (1) to break privacy, and (2) to destroy the utility of analytical results. For the privacy breaking, since the final result aggregates contributions from all users, the attacker can compromise the privacy mechanism by circumventing the required noise. For example, if half of the users are corrupted and withhold noise, the effective privacy protection is reduced by half. Mitigating such privacy issues has been extensively studied, known as robust shuffle-DP ( 1 ) . Existing approaches ( 1 ) suggest that honest participants introduce additional noise to counteract the noise omitted by corrupted users. Specifically, in the above example, each honest user adjusts the noise scale by doubling it to account for the lack of noise contributed by the remaining half, the corrupted users. For the utility destroying, since shuffle-DP allows each user to send additional noise, attackers can manipulate the aggregation results by sending an excessive number of messages. In the bit counting protocol ( 28 ) , each attacker can inject up to O(n) noisy bits without being detected by the analyzer in the worst case, significantly compromising the utility of the final result (see Section 2.4 for more details). Astute readers may find that such an attack is a unique challenge in shuffle-DP. Under local-DP, each message is linked to a real user identity, allowing the analyzer to verify whether messages are reasonable. However, under shuffle-DP, since messages are anonymous, attackers can impersonate honest users and send excessive noise messages, but the analyzer cannot distinguish these poisoned messages from honest ones. Problem Protocol Detection Recovery #Messages/user #Bits/message Error w/o attacker w/ attacker Bit counting GKMPS ( 28 ) \times \times 1+O(\log n/n) 2 O(1) \infty CSUZZ ( 14 ) ✓ \times 1 1 O(\log n) \infty Ours + GKMPS ✓ ✓ O(\log n) O(\log n) O(1) O(\log^{3}n) Summation GKMPS ( 28 ) \times \times 1+O(\log^{3}n\cdot U/n) O(\log n) O(U) \infty BBGN(IKOS) ( 3 ) \times \times O(1) O(\log n) O(U) \infty BBGN(recursive) ( 3 ) ✓ \times O(\log\log n) O(\log n) O(U\sqrt{\log n}\cdot\log\log n) \infty Ours + GKMPS ✓ ✓ O(\log^{2}n\cdot U) O(\log n) O(U) O(U\log^{3}n) Ours + BBGN(IKOS) ✓ ✓ O(\log n\cdot\log\log n) O(\log n) O(U) O(U\log^{3}n) Frequency estimation GKMPS ( 29 ; 28 ) \times \times 1+O(\log n\cdot U/n) O(\log n) O(\log n) \infty GGKPV ( 27 ) \times \times O(\log n) O(\log^{2}n) O(\log n) \infty LWY ( 47 ) \times \times O(1) O(\log n) O(\log n) \infty CZ ( 16 ) ✓ ✓ 2 U O(\log n) O(\log n) Ours + LWY ✓ ✓ O(\log n) O(\log n) O(\log n) O(\log^{3}n) Table 1 . Comparison between our results and prior works for bit counting, summation, and frequency estimation under shuffle-DP, assuming \varepsilon=\beta=\Theta(1) and \log n=\Theta(\log(1/\delta))=\Theta(\log U) . We use \ell_{\infty} error for frequency estimation. Such an issue has gained significant attention recently. Some protocols ( 3 ; 16 ; 27 ) control