Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Improving Utility and Security of the Shuffler-based Differential Privacy

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

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

Pith's one-line read A hash-then-randomize mechanism makes shuffled differential privacy practical on huge domains, and an encrypted-shuffle protocol resists collusion and data poisoning.

desk verdict SOLH is a solid, incremental contribution, but PEOS's main security theorem currently depends on a false binomial identity and an unsubstantiated AHE construction. read the letter →

arxiv 1908.11515 v3 pith:HUW4CVET submitted 2019-08-30 cs.CR cs.DBcs.DScs.LG

Tianhao Wang , Bolin Ding , Min Xu , Zhicong Huang , Cheng Hong , Jingren Zhou , Ninghui Li , Somesh Jha This is my paper · ORCID
classification cs.CRcs.DBcs.DScs.LG
keywords differentialprivacylocalshufflemodelamplificationhashinghistogramestimationencryptedoblivioussecretsharing
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 aims to improve the shuffled-model version of local differential privacy, in which an intermediate server permutes users' locally randomized reports before an analyzer sees them, so that users' privacy is amplified to a centralized differential-privacy guarantee. Its main algorithmic claim is SOLH, a hash-then-randomize mechanism: each user hashes a value into a small domain of size $d'$ and applies randomized response, and shuffling converts an $\epsilon_l$-LDP report into an $(\epsilon_c,\delta)$-DP aggregate with $\epsilon_c = \sqrt{14 \ln(2/\delta)(e^{\epsilon_l}+d'-1)/(n-1)}$. Because $d'$ is tuned from the target privacy level rather than from the original domain size, the estimation error stops growing with the number of categories, which matters for datasets with tens or hundreds of thousands of possible values. The paper also proposes PEOS, an encrypted oblivious shuffle with secret-shared fake reports, to protect against server-user collusion, server-shuffler collusion up to half the shufflers, and data-poisoning by shufflers. If these claims hold, private histogram collection in the shuffle model becomes markedly more accurate on large domains and more robust against realistic attacks.

What carries the argument

Two mechanisms carry the argument. The first is the privacy-blanket decomposition: the distribution of each user's LDP report is split into a value-dependent part and a uniformly random part, so the remaining $n-1$ users' reports contribute Binomial noise that masks the victim's report; SOLH realizes this for large domains by hashing the value to a domain of size $d'$ before randomization, making the random part $1/d'$ independent of the input. The proof of Theorem 3 works by conditioning on the set of users who reported truthfully, removing those reports, and bounding the ratio of two Binomial random variables. The second mechanism is PEOS's Encrypted Oblivious Shuffle, which combines additive secret sharing across $r$ shufflers with additively homomorphic encryption of one share per report and secret-shared uniformly random fake reports; the requirement that the encryption's plaintext space be $\mathbb{Z}_{2^\ell}$ is what makes decrypted fake reports indistinguishable from real reports. The parameter choice in Equation (5) is what turns the privacy bound into a concrete utility guarantee, and Corollaries 8-9 give the corresponding privacy rates with $n_r$ fake reports.

What would settle it

Implement the asserted full-decryption variant of DGK with plaintext space $\mathbb{Z}_{2^\ell}$ and test whether $\mathrm{Dec}(\mathrm{Enc}(a) \oplus \mathrm{Enc}(b)) = a + b \bmod 2^\ell$ for every pair of $\ell$-bit values; if any pair fails, the server can distinguish injected fake reports from user reports, so the $\epsilon_s$ guarantee of PEOS in Corollaries 8-9 does not hold.

Watch

Extended reading notes

Core claim

The paper's central discovery is that privacy amplification by shuffling, previously established for generalized randomized response, can be carried over to local hashing without losing the amplification, and that the resulting mechanism's variance can be optimized independently of the original domain $d$. Theorem 3 states that an $\epsilon_l$-LDP SOLH report becomes $(\epsilon_c,\delta)$-DP after shuffling with the bound above, and Proposition 6 plus Equation (5) set the hash output size to $d' = \lfloor(\epsilon_c^2(n-1)/(42\ln(2/\delta)) + 2/3)\rfloor$ to minimize mean squared error. On the security side, the paper introduces PEOS, which combines additive secret sharing across $r$ shufflers, an Encrypted Oblivious Shuffle that keeps one share under additively homomorphic encryption, and uniformly random fake reports generated jointly by the shufflers. The claimed guarantees are that PEOS remains $(\epsilon_c,\delta)$-DP against the server, that it provides an explicit $\epsilon_s$-DP bound when all other users collude with the server, and that it resists server collusion with up to $\lfloor r/2\rfloor$ shufflers, while a malicious shuffler cannot bias the fake reports it injects. The evaluation reports accuracy gains of orders of magnitude over earlier shuffled-GRR and unary-encoding methods on real datasets, at communication costs that remain practical for a million users.

Load-bearing premise

The entire PEOS security analysis depends on the existence of an additively homomorphic encryption scheme whose plaintext space is the integers modulo $2^\ell$, so that decrypted fake reports look exactly like real reports; the paper points to a full-decryption variant of DGK but does not construct or prove it, and if that instantiation fails, the server can detect the fake reports and the claimed collusion-resistance guarantee collapses.

Editorial extensions

If this is right

  • For domains with tens of thousands of values, SOLH's error no longer scales with the domain size, so shuffle-model frequency estimation becomes practical where GRR-based shuffle mechanisms cannot amplify.
  • Per-user communication for SOLH is a short hash seed plus one value from a small output domain, unlike unary-encoding methods whose per-user cost grows linearly with the domain.
  • With PEOS, even when the server colludes with every other user, the secret-shared uniform fake reports still provide a quantifiable privacy guarantee.
  • PEOS prevents a malicious shuffler from steering the aggregate by inserting biased fake reports, because any one shuffler's shares are masked by the other shufflers' random shares.
  • If the server corrupts no more than half the shufflers, it cannot link users to reports; if it corrupts more than half, the guarantee degrades to the original $\epsilon_l$-LDP setting.

Reading between the lines

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

  • The AHE plaintext-space requirement is the hinge: if the claimed full-decryption DGK variant cannot be built with plaintext space $\mathbb{Z}_{2^\ell}$, then the server can decrypt and recognize the injected fake reports, and the $\epsilon_s$ guarantee in Corollaries 8-9 would not hold; this is an inference about a missing construction, not a claim the paper makes.
  • The same encrypted-shuffle with fake reports could be attached to any LDP mechanism whose report domain is an additive group, not only GRR and SOLH; the paper does not explore this generalization.
  • Because SOLH's hash domain is chosen independently of the original domain, the mechanism should combine naturally with non-interactive heavy-hitter or succinct-histogram pipelines over enormous domains, as the paper's TreeHist case study begins to demonstrate.
  • The utility analysis assumes small average frequencies; for highly skewed distributions the variance formulas may need revisiting, so the practical crossover between GRR and SOLH could depend on the data's skew.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 studies the shuffle model of local differential privacy for histogram estimation. It proposes SOLH, a local-hashing mechanism that combines random hash functions with GRR and whose hash output domain size is tuned to minimize variance for a fixed amplified privacy budget, and PEOS, a protocol that injects uniformly random fake reports and uses encrypted oblivious shuffling to resist collusion between the server and users or shufflers. The paper also analyzes several adversaries, compares SOLH with prior mechanisms, and reports experiments on real datasets plus a performance benchmark of PEOS.

Significance. If the results hold, the paper would make two notable contributions: a utility-optimal local-hashing mechanism for the shuffle model with communication cost independent of the domain size, and a cryptographically enriched protocol that withstands collusion attacks and data poisoning. The strength of the SOLH part is that it is derived analytically: the variance expressions in Propositions 4-6 are based on the published variance formulas, and the optimal value of d' is obtained by minimizing a closed-form expression via calculus rather than by fitting to data. The experimental evaluation on IPUMS, Kosarak, and AOL is useful and supports the qualitative advantage of SOLH over GRR-based shuffling. However, the PEOS privacy analysis contains a false probabilistic identity, and the crucial AHE instantiation is asserted without proof, so the paper's security claims for PEOS are currently not supported.

major comments (3)
  1. [Section VI.B, Corollary 8 (Eq. (7))] The proof of Corollary 8 asserts the equality Bin(n-1, 1/(e^{epsilon_l}+d'-1)) + Bin(n_r, 1/d') = Bin(n-1+n_r, ((n-1)/(e^{epsilon_l}+d'-1)+n_r/d')/(n-1+n_r)). This identity is false in general: the sum of two independent binomial variables with different success probabilities is a Poisson-binomial distribution, not a binomial, and the variances of the two sides do not match. Because the proof explicitly uses this equality, the expressions for epsilon_c and epsilon_s in Eq. (7) are not established. The utility analysis in Section VI.C subsequently tunes d' using this epsilon_c, so the advertised PEOS privacy-utility tradeoff is not derived from the stated assumptions. Corollary 9 inherits the same problem. A correct proof, for example using Poisson-binomial concentration bounds, must be supplied, or the claimed guarantees must be revised.
  2. [Section VI.A.3 and Corollary 7] The security claim for EOS/PEOS depends on an additively homomorphic encryption scheme with plaintext space Z_{2^l}, and the paper states that this 'can be instantiated to be the full-decryption variant of DGK using Pohlig-Hellman algorithm.' No construction, plaintext-space mapping, or security proof for this instantiation is given. This is load-bearing: the server must not be able to distinguish encrypted fake reports from real reports, and that indistinguishability relies on the claimed plaintext group being exactly Z_{2^l}. Corollary 7 is only a proof sketch and does not address this instantiation. As written, the collusion-resistance guarantee of PEOS is unsupported even apart from the Corollary 8 issue.
  3. [Section VI.C] The optimization of d' for PEOS directly depends on the unproven epsilon_c formula from Corollary 8. The text sets e^{epsilon_l}+d'-1 = (n-1)/(14 ln(2/delta)/epsilon_c^2 - n_r/d'), an equation that is only valid if Eq. (7) holds. Since the binomial identity underlying Eq. (7) is false, the derived optimal d' and the resulting variance comparison for PEOS are not supported. This analysis must be redone after the privacy proof is corrected.
minor comments (3)
  1. [Section VI.C] The displayed optimal d' formula uses n-1-n_r in the numerator immediately after defining b = n-1. Since the preceding line contains b+n_r, the numerator should be n-1+n_r; please correct this apparent sign error.
  2. [Appendix, proof of Theorem 3] The appendix proof is presented at a sketch level with statements such as 'we can show' and 'the rest of the proof follows'; please expand the Chernoff-based tail bound and the handling of overlapping reports so the main theorem can be verified without referring to an external proof.
  3. [Section VI.D] The sentence 'we can choose to use either GRR or SOLH by comparing Theorem 3 and Theorem 4' appears to refer to Proposition 4 rather than a Theorem 4; please fix the cross-reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SOLH and PEOS derivations are parameter-free applications of external [9] and [54] lemmas; the main correctness concerns are mathematical gaps, not circular re-use of conclusions.

full rationale

The paper's central algorithmic claim, Theorem 3, is proved in the appendix by reducing the privacy ratio to a ratio of Binomial random variables and then invoking the external 'Binomial mechanism' result from Balle et al. [9] (CRYPTO 2019), which has no author overlap with this paper. Theorem 1 is cited as a parameter-free lemma, not as a conclusion whose input already contains the claimed amplification. The utility analysis in Propositions 4-6 reuses variance formulas from Wang et al. [54]; although [54] shares some authors, those formulas are prior published, parameter-free statements about GRR/OLH variance that do not themselves assert shuffle-model privacy or the optimal d' formula. The choice d' = (m+2)/3 in Eq. (5) is obtained by differentiating the variance expression with respect to d', so it is a calculus minimization, not a fitted parameter renamed as a prediction. PEOS Corollaries 8 and 9 apply the same binomial-mechanism lemma to the n-1 non-victim user reports plus n_r uniform fake reports; the resulting epsilon_c is a closed-form expression from the stated assumptions, not an empirical fit. The review concern about the Binomial-sum identity in Corollary 8's proof is a correctness/rigor issue, and the asserted DGK full-decryption instantiation is a missing cryptographic construction; neither involves the paper defining its input in terms of its output or smuggling its conclusion through a self-citation chain. Accordingly, no circular step is exhibited, and the honest finding is score 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The derivations depend on established DP mechanisms, universal hashing, and standard cryptographic assumptions. The only free parameters are the algorithmic choices d' and nr, both derived from the stated privacy levels rather than fit to the experimental data. No new physical or mathematical entities are postulated.

free parameters (2)
  • d' (SOLH hash output domain size) = floor((m+2)/3), where m = epsilon_c^2(n-1)/(14 ln(2/delta))
    Chosen analytically to minimize variance in Proposition 6 and equation (5); not fitted to data.
  • nr (number of fake reports in PEOS) = not fixed; chosen by numerical search given desired epsilon_1, epsilon_2, epsilon_3 (Section VI.D)
    Free protocol parameter controlling the privacy levels in Corollaries 8 and 9; not fitted to data.
assumptions (5)
  • standard math Binomial mechanism privacy bound of Balle et al. [9, Theorem 3.1]: Bin(n,p) noise provides (sqrt(14 ln(2/delta)/(np)), delta)-DP.
    Used as Theorem 1 and as the engine for Theorems 2 and 3 and Corollaries 8 and 9.
  • standard math Variance formulas for GRR, RAPPOR, and local hashing from Wang et al. [54].
    Imported to compute utility in Propositions 4-6; [54] shares authors with this paper but is a published, independently checkable result.
  • domain assumption The hash family used by SOLH is universal: for a fixed value, H(v) is uniform over [d'], and for distinct v and v', Pr[H(v)=H(v')] <= 1/d'.
    Theorem 3's binomial argument needs each random report to match the victim's value with probability 1/d' independently; the implementation uses xxhash with a 32-bit seed, which is not proven universal.
  • domain assumption Cryptographic primitives (AHE, secret sharing, secure channels) are semantically secure; adversaries are computationally bounded and semi-honest in the privacy proofs.
    Stated in Section II.C and V.B; used for Corollary 7 and Algorithm 1.
  • domain assumption In PEOS, the server cannot corrupt more than floor(r/2) shufflers.
    Used in Section VI.B to claim the server cannot gain useful information; if more shufflers collude, privacy degrades to local differential privacy.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving Utility and Security of the Shuffler-based Differential Privacy." pith.science (2026). https://pith.science/paper/HUW4CVET

@misc{pith2026190811515,
  author       = {Pith},
  title        = {Pith review of: Improving Utility and Security of the Shuffler-based Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HUW4CVET}},
  note         = {Machine review of arXiv:1908.11515}
}
read the original abstract

When collecting information, local differential privacy (LDP) alleviates privacy concerns of users because their private information is randomized before being sent it to the central aggregator. LDP imposes large amount of noise as each user executes the randomization independently. To address this issue, recent work introduced an intermediate server with the assumption that this intermediate server does not collude with the aggregator. Under this assumption, less noise can be added to achieve the same privacy guarantee as LDP, thus improving utility for the data collection task. This paper investigates this multiple-party setting of LDP. We analyze the system model and identify potential adversaries. We then make two improvements: a new algorithm that achieves a better privacy-utility tradeoff; and a novel protocol that provides better protection against various attacks. Finally, we perform experiments to compare different methods and demonstrate the benefits of using our proposed method.

Figures

Figures reproduced from arXiv: 1908.11515 by the authors.

Figure 1
Figure 1. Overview of parties and interactions. Users communi [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Overview of EOS with r = 3 shufflers and n = 3 values a, b, c. Each shuffler receives n shares; and one shuffler’s shares are encrypted by additive homomorphic encryption. During hiding, one shuffler sends its shares to the other two shufflers, who then shuffle the aggregated shares with an agreed permutation. To reshare, each of the shufflers splits its shares and send them to the other shufflers. and sends them to… view at source ↗
Figure 3
Figure 3. Results of MSE varying c on the IPUMS dataset. Base always outputs 1/d for each estimation. Lap stands for Laplace mechanism for DP. B. Frequency Estimation Comparison We first show the utility performance of SOLH. We mainly compare it against other methods in the shuffler model, in￾cluding SH, AUE, RAP, and RAPR. For comparison, we also evaluate several kinds of baselines, including LDP methods OLH and Had, centra… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Comparison on the succinct histogram problem. The [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the Power of Multiple Anonymous Messages

    cs.CR 2019-08 accept novelty 8.0 of 10

    Single-message shuffled-model frequency estimation has optimal error about min(n^{1/4}, sqrt(B)); multi-message protocols achieve polylogarithmic error with polylogarithmic communication.

Reference graph

Works this paper leans on

56 extracted references · 50 canonical work pages · cited by 1 Pith paper

  1. [1]

    Apple differential privacy team, learning with privacy at scale,

    “Apple differential privacy team, learning with privacy at scale,” available at https://machinelearning.apple.com/docs/ learning-with-privacy-at-scale/appledifferentialprivacysystem.pdf

    work page

  2. [2]

    Frequent itemset mining dataset repository,

    “Frequent itemset mining dataset repository,” available at http://fimi.ua. ac.be/data/

    work page

  3. [3]

    Web search query log downloads,

    “Web search query log downloads,” available at http://www. radiounderground.net/aol-data/

    work page

  4. [4]

    Protecting the confidentiality of america’s statistics: Adopting modern disclosure avoidance methods at the census bu- reau,

    J. M. Abowd, “Protecting the confidentiality of america’s statistics: Adopting modern disclosure avoidance methods at the census bu- reau,” https://www.census.gov/newsroom/blogs/research-matters/2018/ 08/protecting the confi.html, 2018

    work page 2018

  5. [5]

    Hadamard response: Estimating distributions privately, efficiently, and with little communication,

    J. Acharya, Z. Sun, and H. Zhang, “Hadamard response: Estimating distributions privately, efficiently, and with little communication,” in AISTATS, 2019

    work page 2019

  6. [6]

    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 Advances in Neural Information Processing Systems, 2019, pp. 13 635–13 646

    work page 2019

  7. [7]

    Geo-indistinguishability: Differential privacy for location-based sys- tems,

    M. Andr ´es, N. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based sys- tems,” in 20th ACM Conference on Computer and Communications Security. ACM, 2013, pp. 901–914

    work page 2013

  8. [8]

    Free Fourier Multipliers associated with the firstSegment

    V . Balcer and A. Cheu, “Separating local & shuffled differential privacy via histograms,” arXiv preprint arXiv:1909.06879 , 2019

    work page Pith review arXiv 1909

Show all 56 references
  1. [9]

    The privacy blanket of the shuffle model,

    B. Balle, J. Bell, A. Gascon, and K. Nissim, “The privacy blanket of the shuffle model,” in CRYPTO, 2019

    2019

  2. [10]

    Private summation in the multi-message shuffle model,

    ——, “Private summation in the multi-message shuffle model,” arXiv preprint arXiv:2002.00817, 2020

    2002 arXiv

  3. [11]

    Practical locally private heavy hitters,

    R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta, “Practical locally private heavy hitters,” arXiv preprint arXiv:1707.04982 , 2017

    2017 arXiv

  4. [12]

    Practical locally private heavy hitters,

    R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta, “Practical locally private heavy hitters,” in NIPS, 2017

    2017

  5. [13]

    Local, private, efficient protocols for succinct histograms,

    R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing . ACM, 2015, pp. 127–135

    2015

  6. [14]

    Local, private, efficient protocols for succinct histograms,

    R. Bassily and A. D. Smith, “Local, private, efficient protocols for succinct histograms,” in STOC, 2015. 13

    2015

  7. [15]

    Pro- tection against reconstruction and its applications in private federated learning,

    A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers, “Pro- tection against reconstruction and its applications in private federated learning,” arXiv preprint arXiv:1812.00984 , 2018

    2018 arXiv

  8. [16]

    The guard’s dilemma: Efficient code-reuse attacks against intel sgx,

    A. Biondo, M. Conti, L. Davi, T. Frassetto, and A.-R. Sadeghi, “The guard’s dilemma: Efficient code-reuse attacks against intel sgx,” in 27th USENIX Security Symposium , 2018

    2018

  9. [17]

    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 SOSP. ACM, 2017

    2017

  10. [18]

    Sharemind: A framework for fast privacy-preserving computations,

    D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” in European Symposium on Research in Computer Security . Springer, 2008, pp. 192–206

    2008

  11. [19]

    Securely sampling biased coins with applications to differential privacy,

    J. Champion, J. Ullman et al. , “Securely sampling biased coins with applications to differential privacy,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security . ACM, 2019, pp. 603–614

    2019

  12. [20]

    Foundations of differentially oblivious algorithms,

    T. H. Chan, K.-M. Chung, B. M. Maggs, and E. Shi, “Foundations of differentially oblivious algorithms,” in SODA. SIAM, 2019

    2019

  13. [21]

    Dis- tributed differential privacy via shuffling,

    A. Cheu, A. D. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Dis- tributed differential privacy via shuffling,” in EUROCRYPT, 2019

    2019

  14. [22]

    Cryptϵ: Crypto-assisted differential privacy on untrusted servers,

    A. R. Chowdhury, C. Wang, X. He, A. Machanavajjhala, and S. Jha, “Cryptϵ: Crypto-assisted differential privacy on untrusted servers,” SIGMOD, 2020

    2020

  15. [23]

    Efficient and secure com- parison for on-line auctions,

    I. Damg ˚ard, M. Geisler, and M. Krøigaard, “Efficient and secure com- parison for on-line auctions,” inAustralasian Conference on Information Security and Privacy . Springer, 2007, pp. 416–430

    2007

  16. [24]

    Homomorphic encryption and secure comparison,

    I. Damgard, M. Geisler, and M. Kroigard, “Homomorphic encryption and secure comparison,” Int. J. Appl. Cryptol. , vol. 1, no. 1, pp. 22–31, Feb. 2008

    2008

  17. [25]

    Collecting telemetry data privately,

    B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” inAdvances in Neural Information Processing Systems, 2017, pp. 3574–3583

    2017

  18. [26]

    One-sided differential privacy,

    S. Doudalis, I. Kotsogiannis, S. Haney, A. Machanavajjhala, and S. Mehrotra, “One-sided differential privacy,” arXiv preprint arXiv:1712.05888, 2017

    2017 arXiv

  19. [27]

    Local privacy and statistical minimax rates,

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

    2013

  20. [28]

    Differential privacy,

    C. Dwork, “Differential privacy,” in ICALP, 2006, pp. 1–12

    2006

  21. [29]

    Our data, ourselves: Privacy via distributed noise generation,

    C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in EUROCRYPT, ser. Lecture Notes in Computer Science, S. Vaudenay, Ed., vol. 4004. Springer, 2006, pp. 486–503

    2006

  22. [30]

    Privex: Private collection of traffic statistics for anonymous communication networks,

    T. Elahi, G. Danezis, and I. Goldberg, “Privex: Private collection of traffic statistics for anonymous communication networks,” in Pro- ceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 1068–1079

    2014

  23. [31]

    Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation,

    ´U. Erlingsson, V . Feldman, I. Mironov, A. Raghunathan, S. Song, K. Talwar, and A. Thakurta, “Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation,” arXiv preprint arXiv:2001.03618, 2020

    2001 arXiv

  24. [32]

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

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

    2019

  25. [33]

    Rappor: Randomized ag- gregatable privacy-preserving ordinal response,

    ´U. Erlingsson, V . Pihur, and A. Korolova, “Rappor: Randomized ag- gregatable privacy-preserving ordinal response,” in CCS. ACM, 2014, pp. 1054–1067

    2014

  26. [34]

    Unlynx: a decentralized system for privacy- conscious data sharing,

    D. Froelicher, P. Egger, J. S. Sousa, J. L. Raisaro, Z. Huang, C. Mouchet, B. Ford, and J.-P. Hubaux, “Unlynx: a decentralized system for privacy- conscious data sharing,” Proceedings on Privacy Enhancing Technolo- gies, vol. 2017, no. 4, pp. 232–250, 2017

    2017

  27. [35]

    On the power of multiple anonymous messages,

    B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker, “On the power of multiple anonymous messages,” arXiv preprint arXiv:1908.11358, 2019

    1908 arXiv

  28. [36]

    Pri- vate aggregation from fewer anonymous messages,

    B. Ghazi, P. Manurangsi, R. Pagh, and A. Velingker, “Pri- vate aggregation from fewer anonymous messages,” arXiv preprint arXiv:1909.11073, 2019

    1909 arXiv

  29. [37]

    Scalable and differentially private distributed aggregation in the shuffled model,

    B. Ghazi, R. Pagh, and A. Velingker, “Scalable and differentially private distributed aggregation in the shuffled model,” arXiv preprint arXiv:1906.08320, 2019

    1906 arXiv

  30. [38]

    Supporting both range queries and frequency estimation with local differential privacy,

    X. Gu, M. Li, Y . Cao, and L. Xiong, “Supporting both range queries and frequency estimation with local differential privacy,” in 2019 IEEE Conference on Communications and Network Security (CNS) . IEEE, 2019, pp. 124–132

    2019

  31. [39]

    Providing input-discriminative protection for local differential privacy,

    X. Gu, M. Li, L. Xiong, and Y . Cao, “Providing input-discriminative protection for local differential privacy,” in ICDE, 2020

    2020

  32. [40]

    Secure and utility-aware data collection with condensed local differential privacy,

    M. E. Gursoy, A. Tamersoy, S. Truex, W. Wei, and L. Liu, “Secure and utility-aware data collection with condensed local differential privacy,” arXiv preprint arXiv:1905.06361 , 2019

    1905 arXiv

  33. [41]

    Composing differential privacy and secure computation: A case study on scaling private record linkage,

    X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . ACM, 2017, pp. 1389–1406

    2017

  34. [42]

    Round-efficient oblivious database manipulation,

    S. Laur, J. Willemson, and B. Zhang, “Round-efficient oblivious database manipulation,” in International Conference on Information Security. Springer, 2011, pp. 262–277

    2011

  35. [43]

    The limits of two-party differential privacy,

    A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan, “The limits of two-party differential privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . IEEE, 2010, pp. 81–90

    2010

  36. [44]

    Federated learning: Collaborative ma- chine learning without centralized training data,

    B. McMahan and D. Ramage, “Federated learning: Collaborative ma- chine learning without centralized training data,”Google Research Blog, vol. 3, 2017

    2017

  37. [45]

    Efficient private statistics with succinct sketches,

    L. Melis, G. Danezis, and E. De Cristofaro, “Efficient private statistics with succinct sketches,” arXiv preprint arXiv:1508.06110 , 2015

    2015 arXiv

  38. [46]

    Computational differential privacy,

    I. Mironov, O. Pandey, O. Reingold, and S. Vadhan, “Computational differential privacy,” in Annual International Cryptology Conference . Springer, 2009, pp. 126–142

    2009

  39. [47]

    Utility-optimized local differential pri- vacy mechanisms for distribution estimation,

    T. Murakami and Y . Kawamoto, “Utility-optimized local differential pri- vacy mechanisms for distribution estimation,” in 28th USENIX Security Symposium, 2019

    2019

  40. [48]

    Public-key cryptosystems based on composite degree residuosity classes,

    P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in International Conference on the Theory and Applications of Cryptographic Techniques . Springer, 1999, pp. 223– 238

    1999

  41. [49]

    An improved algorithm for computing logarithms overgf(p)and its cryptographic significance (corresp.),

    S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms overgf(p)and its cryptographic significance (corresp.),” IEEE Transactions on Information Theory , 1978

    1978

  42. [50]

    Hybrid private record linkage: Separating differentially private synopses from matching records,

    F.-Y . Rao, J. Cao, E. Bertino, and M. Kantarcioglu, “Hybrid private record linkage: Separating differentially private synopses from matching records,” ACM Transactions on Privacy and Security (TOPS) , vol. 22, no. 3, p. 15, 2019

    2019

  43. [51]

    Honeycrisp: large-scale differentially private aggregation without a trusted core,

    E. Roth, D. Noble, B. H. Falk, and A. Haeberlen, “Honeycrisp: large-scale differentially private aggregation without a trusted core,” in Proceedings of the 27th ACM Symposium on Operating Systems Principles. ACM, 2019, pp. 196–210

    2019

  44. [52]

    Integrated public use microdata series: Version 9.0 [database],

    S. Ruggles, S. Flood, R. Goeken, J. Grover, E. Meyer, J. Pacas, and M. Sobek, “Integrated public use microdata series: Version 9.0 [database],” 2019

    2019

  45. [53]

    Local private ordinal data distribution estimation,

    S. Wang, Y . Nie, P. Wang, H. Xu, W. Yang, and L. Huang, “Local private ordinal data distribution estimation,” in INFOCOM 2017-IEEE Conference on Computer Communications, IEEE . IEEE, 2017, pp. 1–9

    2017

  46. [54]

    Locally differentially private pro- tocols for frequency estimation,

    T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private pro- tocols for frequency estimation,” in 26th USENIX Security Symposium , 2017

    2017

  47. [55]

    Answering multi-dimensional analytical queries under local differential privacy,

    T. Wang, B. Ding, J. Zhou, C. Hong, Z. Huang, N. Li, and S. Jha, “Answering multi-dimensional analytical queries under local differential privacy,” in SIGMOD, 2019

    2019

  48. [56]

    Randomized response: A survey technique for eliminat- ing evasive answer bias,

    S. L. Warner, “Randomized response: A survey technique for eliminat- ing evasive answer bias,” Journal of the American Statistical Associa- tion, vol. 60, no. 309, pp. 63–69, 1965. APPENDIX Proof: Denote A as the algorithm of SOLH in the shuffler model. Let A(D) = [ SOLH(vπ(1))...

    1965

Pith tools

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