Pith. sign in

REVIEW 3 major objections 3 minor 74 references

Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The FME protocol brings augmented shuffle differential privacy to large item domains, proving (ε,δ)-CDP, resilience to collusion and poisoning, and O(n+√(ld)) communication in a single user round.

desk verdict The FME protocol's multiple-encryption filtering is a real contribution, but the paper's main accuracy theorems condition the estimator on a selection event that is correlated with the reported counts, so the unbiasedness and variance claims are not proven as written. read the letter →

arxiv 2509.02004 v1 pith:W7HR4GQT submitted 2025-09-02 cs.CR

Takao Murakami , Yuichi Sei , Reo Eriguchi This is my paper
classification cs.CR
keywords differentialprivacyshufflemodelaugmentedprotocolfrequencyestimationkey-valuestatisticsmultipleencryptiondatapoisoningcollusionattacks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that an augmented shuffle protocol can do accurate, differentially private frequency estimation and key-value statistics even when the item domain is huge, and can do it in one round of interaction between users and the shuffler. The FME protocol filters out rare items by counting public hashes, then applies the noise-free, shuffler-side dummy-addition idea only to the surviving popular items, with multiple encryption hiding which ciphertexts were replaced by nulls. If the theorems hold, it is the first such scheme to combine computational DP, robustness to colluding users and fake-user poisoning, accuracy comparable to the small-domain LNF protocol, and total communication O(n+√(ld)) instead of O(n+d). For key-value data, the TKV-FK variant filters at the key level to keep mean estimates from inheriting a positive bias. The authors support the claim with proofs and with comparisons against twelve existing protocols.

What carries the argument

Filtering-with-Multiple-Encryption (FME): each user sends a hash encrypted under the collector's key and an input value encrypted three times, in layers for the collector, the shuffler, and the collector again. The shuffler samples users, adds dummy hashes, and reshuffles; the collector decrypts the hashes, selects a set of popular hash buckets, replaces every nonsellected triple-encrypted value with a triple-encrypted ⊥, and sends the values back; the shuffler removes its layer, drops the dummy-hash entries, adds dummy values for selected items, reshuffles, and the collector decrypts the final counts. Multiple encryption is the load-bearing device: each party sees a different, freshly shuff

What would settle it

Simulate the protocol on a sparse distribution where one item's hash count sits near the selection threshold, record the average of f̂_i over many runs conditioned on that item being selected, and compare it with the true f_i; a persistent gap beyond the theorem's variance formula would falsify the unbiasedness claim. Equivalently, compute E[c_i | i ∈ Λ] both under the theorem's independence assumption and under the actual conditional distribution induced by the filtering rule and compare the two.

Watch

Extended reading notes

Core claim

The paper's central claim is that large-domain shuffle differential privacy can be made practical without giving up the augmented-shuffle protections: the FME protocol performs frequency estimation over domains of size d with total communication O(n+√(ld)) rather than O(n+d), in one round of user interaction, while providing (ε,δ)-CDP and robustness to both collusion with users and data poisoning. On the categorical side, it filters items by counting public hashes, replaces nonsurviving values with encrypted ⊥, and then applies random sampling, dummy addition, and shuffling only to the survivors; Theorem 9 says each selected item gets an unbiased estimate with variance f_i(1−β)/(nβ) + σ₂²/(n

Load-bearing premise

The unbiasedness and variance proofs for selected items treat an item's selection event as independent of the sampled genuine-user count that feeds that selection; if that independence fails, the conditional estimates for selected items would be biased.

Editorial extensions

If this is right

  • Large-domain deployments become feasible: for d≈10⁹ items the protocol cuts estimated communication from roughly 100 Terabits to 260 Gigabits and runtime from years to about a day, with smaller gains at the million-to-billion item scales seen in practice.
  • Accuracy parity with the small-domain protocol: any item that survives filtering has the same variance as LNF, and with a small selection cap l the top-item MSE is nearly unchanged while communication grows only as √(ld).
  • Collusion is neutralized: regardless of how many users collude with the data collector, the realized ε stays at the target ε, unlike pure shuffle protocols where the actual ε can jump from about 1 to 8.
  • Poisoning is bounded: with fake users making up a fraction λ of the population, frequency estimates can be inflated by at most λ(1−f_T) plus a small term from items that filtering fails to select, independent of the privacy budget.
  • For key-value data, frequency and mean estimates for selected keys are almost unbiased, and key-level filtering is what prevents the mean bias that pair-level filtering would introduce.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same hash-to-filter, encrypt-to-measure pattern should generalize to other two-stage heavy-hitter and top-k pipelines, but any pipeline whose selection is based on the same counts being estimated would inherit the same selection-vs-count dependence and would need its own correction.
  • Inference: if the finite-sample dependence between selection and user counts produces a positive bias for just-selected keys, a debiasing adjustment based on the dummy-count distribution or a threshold correction is a natural, testable extension beyond what the paper claims.
  • Inference: the one-round multiple-encryption trick could be reused for augmented-shuffle versions of frequent itemset mining, range queries, or ranking estimation, where local-model protocols exist but robust large-domain shuffle protocols do not yet.
  • Inference: the √(ld) constant is computed from fixed ciphertext sizes; a PKE with lower ciphertext expansion, or batched encryption, would directly shrink the communication term without changing the protocol.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes FME, an augmented shuffle DP protocol for large-domain categorical and key-value data. Users send a hashed value and triple-encrypted item; the shuffler randomly samples, adds dummies, and shuffles; the data collector filters popular hashes and replaces unselected items with a special symbol under multiple encryption; a second augmented shuffle yields counts for selected items. The paper claims (ε,δ)-CDP, robustness to collusion and poisoning, unbiased estimates for selected items with variance matching the LNF protocol, and communication cost O(n + sqrt(ld)). It also presents a KV extension (TKV-FK). Proofs are in Appendices F–J, and experiments compare the proposal with twelve existing protocols.

Significance. If the claims hold, the paper makes a substantial practical contribution: it removes the O(d) per-item dummy cost of the LNF protocol while preserving augmented-shuffle robustness, and it uses multiple encryption in a novel way to keep the user round count at one. The communication-cost analysis and hash-range optimization are useful, the PKE-based CDP reduction in Appendix H is a genuine proof contribution, and the authors provide code. However, the accuracy theorems for selected items contain a conditioning error that invalidates the stated unbiasedness, variance, MSE, and the poisoning bounds derived from them. The central claim that FME achieves LNF-level accuracy for selected items is therefore not established as written.

major comments (3)
  1. [§VI-C, Theorem 9 and Appendix G-D] The proof sets E[c_i|Λ] = nβf_i + μ2 and V[c_i|Λ] = nβf_i(1−β)+σ2^2, treating the number S of sampled genuine users with item i as independent of the selection event Λ. But Λ is determined by the hash count cH_h(i), which includes S whenever β<1 (Algorithm 1, lines 4–12). Since the event h(i)∈ΛH is increasing in S, E[S|Λ] > nβf_i for the selected item, so E[f_i|Λ] ≠ f_i: the estimator is positively biased. For the same reason, V[S|Λ] is not nβf_i(1−β), so Eq. (12) is not the conditional variance, and Eq. (13) omits the squared conditional bias (1−η_i)b_i^2. This is not a proof gap that can be patched by notation: the paper's headline claim that selected items enjoy the LNF variance and unbiasedness fails as stated. A debiased estimator or an explicit bound on the selection bias, with re-derived variance/MSE formulas, is needed.
  2. [§VII-B, Theorem 12 and Appendix J-C] The same selection-bias problem invalidates the KV accuracy theorem. After padding-and-sampling, each user with key i contributes a Bernoulli(1/κ) indicator to both the hash count used for filtering and to the final numerator in (14). Even when β=1, the hash count determining Λ includes these same Bernoulli variables, so the proof's E[c_i,1+c_i,−1|Λ] = nβΦ_i/κ + 2μ2 (Appendix J-C, Eq. (42)) is false. Consequently Eq. (17) overstates the frequency of selected keys, and the variance bounds (18) and (20) are not conditional variances. The paper does not acknowledge or correct this bias. Since the KV estimator is a ratio estimator built on the same biased numerator, a separate correction is needed for Φ and Ψ.
  3. [§VI-C and §VII-B, Theorems 7 and 11] The poisoning bounds inherit the selection-bias flaw. The proofs of Theorem 7 and Theorem 11 use E[f_i] = (1−η_i)f_i and E[Φ_i] = (1−η_i)Φ_i, which follow from conditional unbiasedness of the selected-item estimates. Since the conditional expectations are biased, the equalities do not hold, and the maximum-gain formulas (10), (15), and (16) are not proven. The debiasing correction applied to Theorems 9 and 12 will therefore also change the robustness guarantees; these statements must be reproved together with the accuracy theorems.
minor comments (3)
  1. [Appendix H-B] In the reduction for the data collector's view, after receiving the challenge ciphertexts cb under pks, the simulated view should contain Epkd[cb], since the real view contains the triple ciphertext. The reduction as written sends cb directly. This is fixable because pkd is public, but it should be stated explicitly.
  2. [Section VII-A] The padding-and-sampling step is only defined when |x_i| ≤ κ, which is also the condition in Theorem 12. The Amazon experiments set κ=3, while the dataset has users with more than three KV pairs on average; please state how users with |x_i| > κ are handled and whether the theorem's condition is satisfied in the experiments.
  3. [Theorems 12 and 11] The paper repeatedly uses Taylor expansions of the form E[X/Y] ≈ E[X]/E[Y] and V[X/Y] ≈ V[X]/E[Y]. Since these approximations underlie statements marked '≈' and '≲', a uniform remainder bound or a more precise asymptotic statement would help the reader know when the formulas are quantitatively reliable.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the FME protocol's guarantees are derived from prior LNF results, PKE security, and protocol definitions, not from its own target claims.

full rationale

The FME protocol's central claims are derived by composing the authors' prior LNF protocol [18] with hashing, filtering, and multiple encryption. The privacy proof (Theorem 6, Appendix G) reduces the hash-output mechanism to the LNF/CH analysis and the input-output mechanism to the LNF protocol applied to selected items; these are reductions to a prior published result with stated assumptions (binary input mechanism DP), not reductions to the theorem being proved. The accuracy theorems (Theorems 9 and 12) compute the mean and variance of the estimator from the protocol's own definitions (sampling with probability β, dummy mean μ2) rather than from any fitted parameter; the formulas follow from the estimator f_i = (c_i − μ2)/(nβ) and are not predictions forced by data. The communication bound in Theorem 8 follows by counting ciphertext sizes and the FilterItems rule. There is substantial self-citation to [18] (same authors), but it is not circular: [18] is a separately published result with its own proofs, and the present paper's technical additions (one-round multiple encryption, hash-based filtering, TKV-FK) are not inputs to [18]'s theorems. The possible selection-bias flaw in Theorems 9/12—conditioning on the filtering event Λ while treating the item count as independent—is a correctness and statistical-validity concern, not a circularity in which a prediction is equivalent to its inputs. No step in the claimed derivation reduces by construction to the target result.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The protocol introduces no new physical or mathematical entities. It relies on standard PKE security, the LNF-style dummy distributions, and a sparse-data assumption. The free parameters α, l, β, and b are chosen by heuristics, not fitted to data, but they are load-bearing for the claimed accuracy.

free parameters (4)
  • significance level α = 0.05
    Chosen conventionally; controls the false-positive rate in filtering. Not fitted to data.
  • maximum selected hashes l = max(n^2/d, 50)
    Heuristic to ensure at least 50 popular items are selected while keeping communication low. Not fitted to data but load-bearing for the practical accuracy claim.
  • sampling probability β = 1 (recommended)
    Set to 1 in experiments and recommended in Appendix E-A. The theoretical theorems allow β<1, but the unbiasedness proof fails in that regime.
  • hash range b = minimizer of upper bound in Theorem 8
    Chosen to minimize the theoretical communication upper bound, using ciphertext sizes and dummy means. Not fitted to data, but depends on the free parameters.
assumptions (7)
  • standard math The underlying PKE scheme is IND-CPA secure.
    Assumed in the CDP reduction (Appendix H).
  • domain assumption The shuffler and the data collector are semi-honest and do not collude.
    Stated in Section IV-A; the DP proof breaks if the servers deviate.
  • domain assumption The shuffler does not disclose dummies after the protocol.
    Assumed in Theorem 6; Appendix E-F discusses adding noise if this is violated.
  • standard math The binary input mechanisms MD1,β and MD2,1 provide the stated (ε/2, δ/2)-DP.
    Imported from the prior LNF analysis [18]; not rederived here.
  • domain assumption The frequency distribution is sparse, so l selected hashes cover all items of interest.
    Stated in Section VI-D and needed for the small-l setting; if the data are not sparse, the protocol outputs 0 for most items and becomes inaccurate.
  • domain assumption Each user has at most one KV pair per key and values are in [-1,1].
    Standard for KV DP; used for padding-and-sampling and the TKV-FK transformation.
  • standard math In the KV mean analysis, Taylor expansions E[X/Y]≈E[X]/E[Y] and V[X/Y]≈V[X]/E[Y] are valid.
    Used in Theorems 11 and 12; only an approximation, not a bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data." pith.science (2026). https://pith.science/paper/W7HR4GQT

@misc{pith2026250902004,
  author       = {Pith},
  title        = {Pith review of: Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W7HR4GQT}},
  note         = {Machine review of arXiv:2509.02004}
}
read the original abstract

Shuffle DP (Differential Privacy) protocols provide high accuracy and privacy by introducing a shuffler who randomly shuffles data in a distributed system. However, most shuffle DP protocols are vulnerable to two attacks: collusion attacks by the data collector and users and data poisoning attacks. A recent study addresses this issue by introducing an augmented shuffle DP protocol, where users do not add noise and the shuffler performs random sampling and dummy data addition. However, it focuses on frequency estimation over categorical data with a small domain and cannot be applied to a large domain due to prohibitively high communication and computational costs. In this paper, we fill this gap by introducing a novel augmented shuffle DP protocol called the FME (Filtering-with-Multiple-Encryption) protocol. Our FME protocol uses a hash function to filter out unpopular items and then accurately calculates frequencies for popular items. To perform this within one round of interaction between users and the shuffler, our protocol carefully communicates within a system using multiple encryption. We also apply our FME protocol to more advanced KV (Key-Value) statistics estimation with an additional technique to reduce bias. For both categorical and KV data, we prove that our protocol provides computational DP, high robustness to the above two attacks, accuracy, and efficiency. We show the effectiveness of our proposals through comparisons with twelve existing protocols.

Figures

Figures reproduced from arXiv: 2509.02004 by the authors.

Figure 1
Figure 1. Overview of the LNF protocol (n = 6, d = 3). In this example, the shuffler discards input data of u2 and adds (z1, z2, z3) = (1, 0, 2) dummies. for each item i ∈ [d] from yπ(1), . . . , yπ(˜n) . In the example of [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Two-round protocol using a hash function [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Overview of our FME protocol. It reduces the number of rounds [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Example of filtering items. In this example, [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Example of filtering at a (a) KV pair level or (b) key level. The [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: MSE vs. ε (δ = 10−12). Foursquare AOL 0.0 0.2 0.4 0.6 0.8 1.0 0.1 1 10 n 0.0 0.2 0.4 0.6 0.8 1.0 0.1 1 10 n          Proposal 㻌㻌䚷䚷䚷 GRR RAPPOR/OUE/OLH LWY22㻙Large BC20 CM22 _:_Q 0.0 0.2 0.4 0.6 0.8 1.0 0.1 1 10 n 0.0 0.2 0.4 0.6 0.8…
Figure 10
Figure 10. Figure 10: ε in DP and the lower bound on the attacker’s error probability p ∗ (= pI = pII ) obtained from (22) (δ = 10−12). 0.0 0.2 0.4 0.6 0.8 1.0 10−8 10−7 10−6 10−5 10−4 1 (x ) 10−7 10−5 10−3 10−1 10−8 10−7 10−6 0 100 200 300 400 500 10−8 10−7 10−6 10−5 10−4 10−3 l 12345 P…
Figure 14
Figure 14. Figure 14: MSE of our proposal and the CH/GH/UH protocol in the Foursquare [PITH_FULL_IMAGE:figures/full_fig_p018_14.png]
Figure 17
Figure 17. Figure 17: MSE of our proposals with additional noise in the Foursquare and [PITH_FULL_IMAGE:figures/full_fig_p018_17.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

74 extracted references · 74 canonical work pages

  1. [1]

    Dwork and A

    C. Dwork and A. Roth, The Algorithmic Foundations of Differential Privacy. Now Publishers, 2014

    work page 2014

  2. [2]

    RAPPOR: Randomized aggregatable privacy-preserving ordinal response,

    U. Erlingsson, V . Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,” in Proc. CCS’14 , 2014, pp. 1054–1067

    work page 2014

  3. [3]

    Collecting telemetry data privately,

    B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in Proc. NIPS’17, 2017, pp. 3574–3583

    work page 2017

  4. [4]

    A. G. Thakurta, A. H. Vyrros, U. S. Vaishampayan, G. Kapoor, J. Freudiger, V . R. Sridhar, and D. Davidson, learning New Words, US Patent 9,594,741, Mar. 14 2017

    work page 2017

  5. [5]

    Differential privacy for government agencies—are we there yet?

    J. Drechsler, “Differential privacy for government agencies—are we there yet?” Journal of the American Statistical Association , vol. 118, no. 541, pp. 761–773, 2023

    work page 2023

  6. [6]

    95% of data breaches tied to human error in 2024,

    J. Coker, “95% of data breaches tied to human error in 2024,” https: //www.infosecurity-magazine.com/news/data-breaches-human-error/, 2024

    work page 2024

  7. [7]

    What can we learn privately?

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, and S. Raskhodnikova, “What can we learn privately?” in Proc. FOCS’08, 2008, pp. 531–540

    work page 2008

  8. [8]

    Locally differentially private frequency estimation with consistency,

    T. Wang, M. Lopuhaa-Zwakenberg, Z. Li, B. Skoric, and N. Li, “Locally differentially private frequency estimation with consistency,” in Proc. NDSS’20, 2020, pp. 1–16

    work page 2020

Show all 74 references
  1. [9]

    Revisiting EM-based esti- mation for locally differentially private protocols,

    Y . Ye, T. Wang, M. Zhang, and D. Feng, “Revisiting EM-based esti- mation for locally differentially private protocols,” in Proc. NDSS’25 , 2025, pp. 1–18

    2025

  2. [10]

    PROCHLO: Strong privacy for analytics in the crowd,

    A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “PROCHLO: Strong privacy for analytics in the crowd,” in Proc. SOSP’17, 2017, pp. 441–459

    2017

  3. [11]

    Amplification by shuffling: from local to central differential privacy via anonymity,

    U. Erlingsson, V . Feldman, I. Mironov, A. Raghunathan, and K. Talwar, “Amplification by shuffling: from local to central differential privacy via anonymity,” in Proc. SODA’19, 2019, pp. 2468–2479

    2019

  4. [12]

    Distributed differential privacy via shuffling,

    A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in Proc. EUROCRYPT’19, 2019, pp. 375–403

    2019

  5. [13]

    The privacy blanket of the shuffle model,

    B. Balle, J. Bell, A. Gascon, and K. Nissim, “The privacy blanket of the shuffle model,” in Proc. CRYPTO’19, 2019, pp. 638–667

    2019

  6. [14]

    On the r ´enyi differential privacy of the shuffle model,

    A. M. Girgis, D. Data, S. Diggavi, A. T. Suresh, and P. Kairouz, “On the r ´enyi differential privacy of the shuffle model,” in Proc. CCS’21 , 2021, pp. 2321–2341

    2021

  7. [15]

    Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling,

    V . Feldman, A. McMillan, and K. Talwar, “Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling,” in Proc. FOCS’21, 2021, pp. 954–964

    2021

  8. [16]

    Stronger privacy amplification by shuffling for r ´enyi and approx- imate differential privacy,

    ——, “Stronger privacy amplification by shuffling for r ´enyi and approx- imate differential privacy,” in Proc. SODA’23, 2023, pp. 4966–4981

    2023

  9. [17]

    Improving utility and security of the shuffler-based differential privacy,

    T. Wang, B. Ding, M. Xu, Z. Huang, C. Hong, J. Zhou, N. Li, and S. Jha, “Improving utility and security of the shuffler-based differential privacy,” Proceedings of the VLDB Endowment , vol. 13, no. 13, pp. 3545–3558, 2020

    2020

  10. [18]

    Augmented shuffle protocols for accurate and robust frequency estimation under differential privacy,

    T. Murakami, Y . Sei, and R. Eriguchi, “Augmented shuffle protocols for accurate and robust frequency estimation under differential privacy,” in Proc. S&P’25, 2025, pp. 3892–3911

    2025

  11. [19]

    Data poisoning attacks to local differential privacy protocols,

    X. Cao, J. Jia, and N. Z. Gong, “Data poisoning attacks to local differential privacy protocols,” in Proc. USENIX Security’21 , 2021, pp. 947–964

    2021

  12. [20]

    Poisoning attacks to local differential privacy protocols for key-value data,

    Y . Wu, X. Cao, J. Jia, and N. Z. Gong, “Poisoning attacks to local differential privacy protocols for key-value data,” in Proc. USENIX Security’22, 2022, pp. 519–536

    2022

  13. [21]

    PrivKV: Key-value data collection with local differential privacy,

    Q. Ye, H. Hu, X. Meng, and H. Zheng, “PrivKV: Key-value data collection with local differential privacy,” in Proc. S&P’19, 2019, pp. 317–331

    2019

  14. [22]

    PrivKVM*: Revisiting key-value statistics estimation with local differential privacy,

    Q. Ye, H. Hu, X. Meng, H. Zheng, K. Huang, and C. Fang, “PrivKVM*: Revisiting key-value statistics estimation with local differential privacy,” IEEE Trans. Dependable and Secure Computing , vol. 20, no. 1, pp. 17– 35, 2023

    2023

  15. [23]

    PCKV: Locally differentially private correlated key-value data collection with optimized utility,

    X. Gu, M. Li, Y . Cheng, L. Xiong, and Y . Cao, “PCKV: Locally differentially private correlated key-value data collection with optimized utility,” in Proc. USENIX Security’20 , 2020, pp. 967–984

    2020

  16. [24]

    Differentially private triangle and 4-cycle counting in the shuffle model,

    J. Imola, T. Murakami, and K. Chaudhuri, “Differentially private triangle and 4-cycle counting in the shuffle model,” in Proc. CCS’22, 2022, pp. 1505–1518

    2022

  17. [25]

    Schneier, Applied Cryptography: Protocols, Algorithms and Source Code in C

    B. Schneier, Applied Cryptography: Protocols, Algorithms and Source Code in C . Wiley, 2015

    2015

  18. [26]

    Computational differential privacy,

    I. Mironov, O. Pandey, O. Reingold, and S. Vadhan, “Computational differential privacy,” in Proc. CRYPTO’09, 2009, pp. 126–142

    2009

  19. [27]

    Efficient noise generation protocols for differentially private multiparty computation,

    R. Eriguchi, A. Ichikawa, N. Kunihiro, and K. Nuida, “Efficient noise generation protocols for differentially private multiparty computation,” IEEE Trans. Dependable and Secure Computing , vol. 20, no. 06, pp. 4486–4501, 2023

    2023

  20. [28]

    Provable security for the onion routing and mix network packet format sphinx,

    P. Scherer, C. Weis, and T. Strufe, “Provable security for the onion routing and mix network packet format sphinx,” PoPETs, vol. 2024, no. 4, pp. 755–783, 2024

    2024

  21. [29]

    On the k-independence required by linear probing and minwise independence,

    M. Patrascu and M. Thorup, “On the k-independence required by linear probing and minwise independence,” ACM Trans. Algorithms , vol. 12, no. 1, pp. 1–27, 2015

    2015

  22. [30]

    Amazon statistics: Key numbers and fun facts,

    “Amazon statistics: Key numbers and fun facts,” https://amzscout.net/ blog/amazon-statistics/, 2024

    2024

  23. [31]

    Amazon - ratings (beauty products),

    “Amazon - ratings (beauty products),” https://www.kaggle.com/datasets/ skillsmuggler/amazon-ratings, 2018

    2018

  24. [32]

    https://doi.org/10.5281/zenodo.17032669, 2025

    2025 doi

  25. [33]

    Frequency estimation in the shuffle model with almost a single message,

    Q. Luo, Y . Wang, and K. Yi, “Frequency estimation in the shuffle model with almost a single message,” in Proc. CCS’22, 2022, pp. 2219–2232

    2022

  26. [34]

    Separating local & shuffled differential privacy via histograms,

    V . Balcer and A. Cheu, “Separating local & shuffled differential privacy via histograms,” in Proc. ITC’20, 2020, pp. 1–14

    2020

  27. [35]

    Differentially private histograms in the shuffle model from fake users,

    A. Cheu and M. Zhilyaev, “Differentially private histograms in the shuffle model from fake users,” in Proc. S&P’22, 2022, pp. 440–457

    2022

  28. [36]

    On the round complexity of the shuffle model,

    A. Beimel, I. Haitner, K. Nissim, and U. Stemmer, “On the round complexity of the shuffle model,” in Proc. TCC’20, 2020, pp. 683–712

    2020

  29. [37]

    R ´enyi differential privacy of the subsampled shuffle model in distributed learning,

    A. Girgis, D. Data, and S. Diggavi, “R ´enyi differential privacy of the subsampled shuffle model in distributed learning,” in Proc. NeurIPS’21, 2021, pp. 29 181–29 192

    2021

  30. [38]

    Manipulation attacks in local differential privacy,

    A. Cheu, A. Smith, and J. Ullman, “Manipulation attacks in local differential privacy,” in Proc. S&P’21, 2021, pp. 883–900

    2021

  31. [39]

    Fine-grained poisoning attack to local differential privacy protocols for mean and variance estimation,

    X. Li, N. Li, W. Sun, N. Z. Gong, and H. Li, “Fine-grained poisoning attack to local differential privacy protocols for mean and variance estimation,” in Proc. USENIX Security’23 , 2023, pp. 1739–1756

    2023

  32. [40]

    Data poisoning attacks to locally differentially private frequent itemset mining protocols,

    W. Tong, H. Chen, J. Niu, and S. Zhong, “Data poisoning attacks to locally differentially private frequent itemset mining protocols,” in Proc. CCS’24, 2024, pp. 3555–3569

    2024

  33. [41]

    LDPGuard: Defenses against data poisoning attacks to local differential privacy protocols,

    K. Huang, G. Ouyang, Q. Ye, H. Hu, B. Zheng, X. Zhao, R. Zhang, and X. Zhou, “LDPGuard: Defenses against data poisoning attacks to local differential privacy protocols,” IEEE Trans. Knowledge and Data Engineering, vol. 36, no. 7, pp. 3195–3209, 2024

    2024

  34. [42]

    Efficient defenses against output poisoning attacks on local differential privacy,

    S. Song, L. Xu, and L. Zhu, “Efficient defenses against output poisoning attacks on local differential privacy,” IEEE Trans. Information Forensics and Security, vol. 18, pp. 5506–5521, 2023

    2023

  35. [43]

    Preventing manipulation attack in local differential privacy using verifiable randomization mechanism,

    F. Kato, Y . Cao, and M. Yoshikawa, “Preventing manipulation attack in local differential privacy using verifiable randomization mechanism,” in Proc. DBSec’24, 2021, pp. 43–60. 14

    2021

  36. [44]

    Local differential privacy protocol for making key–value data robust against poisoning attacks,

    H. Horigome, H. Kikuchi, and C.-M. Yu, “Local differential privacy protocol for making key–value data robust against poisoning attacks,” in Proc. MDAI’23, 2023, pp. 241–252

    2023

  37. [45]

    LDPRecover: Recovering frequencies from poisoning attacks against local differential privacy,

    X. Sun, Q. Ye, H. Hu, J. Duan, T. Wo, J. Xu, and R. Yang, “LDPRecover: Recovering frequencies from poisoning attacks against local differential privacy,” in Proc. ICDE’24, 2024

    2024

  38. [46]

    Chosen-ciphertext security of multiple encryp- tion,

    Y . Dodis and J. Katz, “Chosen-ciphertext security of multiple encryp- tion,” in Proc. TCC’05, 2005, pp. 188–209

    2005

  39. [47]

    The security of multiple encryption in the ideal cipher model,

    Y . Dai, J. Lee, B. Mennink, and J. Steinberger, “The security of multiple encryption in the ideal cipher model,” in Proc. CRYPTO’14, 2014, pp. 20–38

    2014

  40. [48]

    An efficient publicly verifiable mix-net for long inputs,

    J. Furukawa and K. Sako, “An efficient publicly verifiable mix-net for long inputs,” in Proc. FC’06, 2006, pp. 111–125

    2006

  41. [49]

    Adams and A.-K

    D. Adams and A.-K. Maier, Big Seven Study: 7 Open Source Crypto- Messengers to be Compared . Books on Demand, 2016

    2016

  42. [50]

    Distributed, private, sparse histograms in the two- server model,

    J. Bell, A. Gascon, B. Ghazi, R. Kumar, P. Manurangsi, M. Raykova, and P. Schoppmann, “Distributed, private, sparse histograms in the two- server model,” in Proc. CCS’22, 2022, pp. 307–321

    2022

  43. [51]

    Locally differentially private protocols for frequency estimation,

    T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in Proc. USENIX Security’17, 2017, pp. 729–745

    2017

  44. [52]

    N. Li, M. Lyu, and D. Su, Differential Privacy: From Theory to Practice. Morgan & Claypool Publishers, 2016

    2016

  45. [53]

    Local privacy and statistical minimax rates,

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in Proc. FOCS’13, 2013, pp. 429–438

    2013

  46. [54]

    Discrete distribution estima- tion under local privacy,

    P. Kairouz, K. Bonawitz, and D. Ramage, “Discrete distribution estima- tion under local privacy,” in Proc. ICML’16, 2016, pp. 2436–2444

    2016

  47. [55]

    A rigorous and customizable frame- work for privacy,

    D. Kifer and A. Machanavajjhala, “A rigorous and customizable frame- work for privacy,” in Proc. PODS’12, 2012, pp. 77–88

    2012

  48. [56]

    Trafficking fraudulent accounts: The role of the underground market in twitter spam and abuse,

    K. Thomas, D. McCoy, C. Grier, A. Kolcz, and V . Paxson, “Trafficking fraudulent accounts: The role of the underground market in twitter spam and abuse,” in Proc. USENIX Security’13 , 2013, pp. 195–210

    2013

  49. [57]

    An algorithmic framework for differentially private data analysis on trusted processors,

    J. Allen, B. Ding, J. Kulkarni, H. Nori, O. Ohrimenko, and S. Yekhanin, “An algorithmic framework for differentially private data analysis on trusted processors,” in Proc. NeurIPS’19, 2019, pp. 13 657–13 664

    2019

  50. [58]

    Camel: Communication-efficient and maliciously secure federated learning in the shuffle model of differential privacy,

    S. Xu, Y . Zheng, and Z. Hua, “Camel: Communication-efficient and maliciously secure federated learning in the shuffle model of differential privacy,” in Proc. CCS’24, 2024, pp. 243–257

    2024

  51. [59]

    Distributed private data analysis: Simultaneously solving how and what,

    A. Beimel, K. Nissim, and E. Omri, “Distributed private data analysis: Simultaneously solving how and what,” in Proc. CRYPTO’08, 2008, pp. 451–468

    2008

  52. [60]

    Heavy hitter estimation over set-valued data with local differential privacy,

    Z. Qin, Y . Yang, T. Yu, I. Khalil, X. Xiao, and K. Ren, “Heavy hitter estimation over set-valued data with local differential privacy,” in Proc. CCS’16, 2016, pp. 192–203

    2016

  53. [61]

    Bouncy castle – open-source cryptographic APIs,

    “Bouncy castle – open-source cryptographic APIs,” https://www. bouncycastle.org/, 2025

    2025

  54. [62]

    Mining interesting locations and travel sequences from GPS trajectories,

    Y . Zheng, L. Zhang, X. Xie, and W.-Y . Ma, “Mining interesting locations and travel sequences from GPS trajectories,” in Proc. WWW’09, 2009, pp. 791–800

    2009

  55. [63]

    Participatory cultural mapping based on collective behavior data in location based social network,

    D. Yang, D. Zhang, and B. Qu, “Participatory cultural mapping based on collective behavior data in location based social network,” ACM Trans. Intelligent Systems and Technology, vol. 7, no. 3, pp. 30:1–30:23, 2016

    2016

  56. [64]

    A picture of search,

    G. Pass, A. Chowdhury, and C. Torgeson, “A picture of search,” in Proc. InfoScale’06, 2006, pp. 1–7

    2006

  57. [65]

    Women’s e-commerce clothing reviews,

    “Women’s e-commerce clothing reviews,” https://www.kaggle.com/ datasets/nicapotato/womens-ecommerce-clothing-reviews, 2018

    2018

  58. [66]

    Key-value data collec- tion and statistical analysis with local differential privacy,

    H. Zhu, X. Tang, L. T. Yang, C. Fu, and S. Peng, “Key-value data collec- tion and statistical analysis with local differential privacy,” Information Sciences, vol. 640, pp. 1–18, 2023

    2023

  59. [67]

    Poisoning attacks to local differential privacy for ranking estimation,

    P. Zhan, P. Tang, Y . Li, P. Wei, and S. Guo, “Poisoning attacks to local differential privacy for ranking estimation,” CoRR, vol. abs/2506.24033, 2025

    2025

  60. [68]

    Data poisoning attacks to locally differentially private range query protocols,

    T.-W. Liao, C.-H. Lin, Y .-L. Tsai, T. Murakami, C.-M. Yu, J. Sakuma, C.-Y . Huang, and H. Kikuchi, “Data poisoning attacks to locally differentially private range query protocols,”CoRR, vol. abs/2503.03454, 2025

    2025 arXiv

  61. [69]

    The composition theorem for differential privacy,

    P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in Proc. ICML’15, 2015, pp. 1376–1385

    2015

  62. [70]

    Universally utility- maximizing privacy mechanisms,

    A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility- maximizing privacy mechanisms,” SIAM Journal on Computing, vol. 41, no. 6, pp. 1673–1693, 2012

    2012

  63. [71]

    Katz and Y

    J. Katz and Y . Lindell, Introduction to Modern Cryptography. Chapman and Hall/CRC, 2014. TABLE I BASIC NOTATIONS . Symbol Description n Number of users. d Number of items. ui i-th user. xi Input value of user ui. X Space of input data. fi Frequency of item i in categorical da...

    2014

  64. [72]

    Y came from D

    states that the entire protocol provides (ε, δ− ( δ 2 )2)-DP (or (0, δ′)-DP with an extremely large δ′), which is almost equivalent to (ε, δ)-DP. Thus, the basic composition theorem is almost tight in our case. APPENDIX D ε IN DP AND PRIVACY GUARANTEES Below, we show the relat...

  65. [73]

    Expected Squared Error

    (27) By (26) and (27), we have V[ ˆfi|Λ] = fi(1−β) nβ + σ2 2 n2β2 . Expected Squared Error. Item i is not selected in the filtering step (i.e., i /∈ Λ) with probability ηi, and ˆfi = 0 in this case. Thus, the expected squared error is written as E[( ˆfi − fi)2] = (1 − ηi) V[ ˆ...

  66. [74]

    For j ∈ Ui, let qj,i ∈ [0, 1] be the probability that user uj adds ˜ci,1 by one

    (45) Below, we calculate V[˜ci,1|Λ]. For j ∈ Ui, let qj,i ∈ [0, 1] be the probability that user uj adds ˜ci,1 by one. Then, we have qj,i = β κ · 1+ψj,i 2 (46) Ψi = 1 |Ui| P uj ∈Ui ψj,i = 1 nΦi P uj ∈Ui ψj,i. (47) Since dummy values of variance σ2 2 are added to ⟨i, 1⟩, V[˜ci,1...

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.