REVIEW 4 minor 1 cited by
On the Power of Multiple Anonymous Messages
T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The optimal error for private frequency estimation in the single-message shuffled model is $\widetilde{\Theta}(\min(n^{1/4}, \sqrt{B}))$, and multi-message protocols achieve $\widetilde{O}(1)$ error, giving the first separation between…
desk verdict Near-tight single-message lower bounds and first single-vs-multi-message separations for frequency estimation and selection in the shuffled model; the proofs are long but internally coherent and worth serious referee time. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object for the single-message lower bound is a structural lemma (Lemma 3.15) stating that any accurate local randomizer must have total variation distance close to 1 between the distribution of its output on a fixed input $v$ and its output on a uniformly random input; the proof uses binomial anti-concentration and the data-processing inequality. This feeds a mutual-information bound for an $\alpha$-accurate, $(\varepsilon_L,\delta_L)$-locally private randomizer of the form $I(V;R(X)) \le \widetilde{O}(\gamma^2 \alpha^2 n e^{\varepsilon_L}(1+\varepsilon_L) + \gamma \alpha^2 n + \gamma^2)$, which Fano's inequality converts into the $\widetilde{\Omega}(n^{1/4})$ error bound. A reduction from the shuffled model to the local model lifts the local-model lower bound to the single-message shuffled model. On the multi-message side, the machinery is a multi-message Hadamard response, in which each user sends a logarithmic number of indices from its Hadamard codeword together with blanket noise, and a public-coin Count Min sketch with binomial noise that achieves polylogarithmic query time.
What would settle it
Run any candidate single-message shuffled protocol with $n=B^2$ users, constant $\varepsilon$, and $\delta=n^{-2}$, and measure the maximum frequency-estimation error; Theorem 1.1 predicts error $\widetilde{\Omega}(n^{1/4})$, so an error of $o(n^{1/4})$ refutes the characterization. For a more local test of Lemma 3.15, fix $v$, compare the distribution of $R(v)$ with $R(U)$ under the protocol's local randomizer, and check whether an accurate protocol can exist with total variation distance between these two distributions bounded away from 1.
Extended reading notes
Core claim
The paper's central claim is a near-complete characterization: for $(\varepsilon,\delta)$-differentially private frequency estimation in the single-message shuffled model, the optimal error is $\widetilde{\Theta}(\min(n^{1/4}, \sqrt{B}))$, up to polylogarithmic factors. The lower bound is proved through a new local-model lower bound that works in the low-privacy regime $\varepsilon_L \approx \ln n$ and with $\delta_L>0$, going beyond the pure-privacy, small-$\varepsilon_L$ techniques of previous work. The matching upper bound comes from applying privacy amplification by shuffling to RAPPOR and to $B$-ary randomized response. In the multi-message model the paper gives protocols with polylogarithmic error and communication for frequency estimation, and a lower bound of $\Omega(B)$ users for selection in the single-message model, which together with an existing $\tilde{O}(\sqrt{B})$-user multi-message protocol gives the first separation between the two message regimes.
Load-bearing premise
The single-message lower bound rests on the claim that an accurate local randomizer must make its output on a fixed input nearly statistically disjoint from its output on a uniform input; if an accurate protocol could keep those distributions close while still recovering frequencies by correlating messages across users, the mutual-information bound and the $n^{1/4}$ error lower bound would fail.
Editorial extensions
If this is right
- Single-message shuffled protocols for frequency estimation are near-optimal: the known amplification-by-shuffling upper bounds from RAPPOR and $B$-ary randomized response cannot be improved without leaving the single-message regime.
- Multi-message protocols achieve exponentially smaller error than any single-message protocol, with polylogarithmic per-user communication, for frequency estimation and, by known reductions, for heavy hitters.
- For selection, any single-message protocol needs $\Omega(B)$ users, while a multi-message protocol uses only $\tilde{O}(\sqrt{B})$ users, giving the first separation for this problem.
- The multi-message frequency oracle transfers to range counting, $M$-estimation of the median, quantiles, and simulation of sparse non-adaptive statistical query algorithms with improved sample and communication costs.
Reading between the lines
- The structural total-variation lemma likely applies beyond frequency estimation: any single-message shuffled protocol for a family of counting queries whose local randomizer is accurate should force near-disjoint output distributions, which would extend the $n^{1/4}$-type barrier to distribution testing and clustering tasks that call a frequency oracle as a subroutine.
- The nearly tight lower bound suggests a clean separation between what anonymity can hide with one message versus several: multi-message protocols effectively emulate a curator with polylog overhead, so further gains for single-message protocols would need to exploit correlations across users' messages rather than the structure of the local randomizer alone.
- A natural testable extension is to check whether the same mutual-information machinery yields tight bounds for real-valued summation in the single-message shuffled model when the domain is continuous; the paper's techniques are stated for finite domains and would require new discretization arguments.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies frequency estimation and selection in the shuffled model of differential privacy. For single-message protocols it proves a nearly tight lower bound on the error of frequency estimation, namely \tilde{\Omega}(\min(n^{1/4},\sqrt{B})) up to polylogarithmic factors, together with a nearly tight \Omega(B) lower bound on the number of users required for selection. It then constructs multi-message protocols for frequency estimation with polylogarithmic error and polylogarithmic per-user communication, in both private-coin and public-coin settings, and applies them to heavy hitters, range counting, median/quantile estimation, and simulation of sparse non-adaptive statistical query algorithms. The combination of these results gives the first separations between single-message and multi-message protocols in the shuffled model for frequency estimation and for selection.
Significance. If the results hold, they essentially settle the single-message frequency-estimation error up to polylog factors and provide a clean separation between single-message and multi-message shuffled-model protocols. The main contribution is the lower-bound technology: a low-privacy, approximate-DP local-model bound built on a structural total-variation lemma for accurate randomizers (Lemma 3.15) and a mutual-information analysis (Lemma 3.14), plus the multi-message constructions based on Hadamard response and a differentially private Count-Min sketch. The proofs are detailed and structured, with supporting lemmas and appendices; I found no circular parameter fitting or post-hoc exclusion of cases. The dependency chain from Lemma 3.5 through Lemma 3.14 and Lemma 3.15 to Theorem 3.1 is coherent, and the anti-concentration argument in Lemma 3.15 is nontrivial and potentially of independent interest. The matching upper and lower bounds in each parameter regime give additional confidence in the central claim.
minor comments (4)
- [Section 3.2, proof of Lemma 3.8] In the proof of Lemma 3.8, the sentence stating that the distribution of R(V) is P_v is confusing: P_v was defined as the conditional distribution of R(v), whereas the marginal distribution of R(V) is the mixture P-bar = (1/B) \sum_{v} P_v. Please correct this notation.
- [Section 1.2 / Remark 3.4] There are a few typographical slips in the informal discussion, for example \alpha! 1/\sqrt{n} should presumably be \alpha \ll 1/\sqrt{n}, and a later expression appears to contain a garbled operator. These do not affect the formal statements but should be cleaned up.
- [Table 1] In the row for communication per user, the entry "any" in the single-message lower-bound column is ambiguous. Consider clarifying that the lower bound holds regardless of the message length or total communication.
- [Theorem 4.3 / Lemma 4.4] Lemma 4.4 states privacy parameters (k\varepsilon, \delta \exp(k\varepsilon)/\varepsilon) while Theorem 4.3 states (\varepsilon,\delta). The rescaling of \varepsilon and \delta that converts the lemma into the theorem is not made explicit in the text; please spell it out for readability.
Circularity Check
No significant circularity; the lower bound proof is self-contained given external reductions and inequalities, and the multi-message protocols are independently constructed and analyzed.
full rationale
The paper's central claim is the single-message lower bound of Theta-tilde(min(n^{1/4}, sqrt(B))) for frequency estimation. That lower bound is obtained by first applying the external reduction of Cheu et al. (Lemma 3.5, restated from [CSU'19]) to pass from the shuffled model to a local randomizer with privacy parameter epsilon + ln n, and then proving a new local-model lower bound (Theorem 3.3) using mutual-information arguments. The key lemmas in that proof, Lemma 3.14 and Lemma 3.15, are derived within the paper from the privacy and accuracy assumptions on the randomizer; they are not assumed as inputs or fitted to the target error. Lemma 3.15 uses an anti-concentration/data-processing argument, and Lemma 3.14 uses the resulting total-variation bound together with the local privacy guarantee. These steps do not reduce to the conclusion by construction. The upper bound in Theorem 1.1 is explicitly attributed to external privacy-amplification results [EFM'19, BBGN19c] combined with RAPPOR and B-ary randomized response; it is not derived from the lower bound. The multi-message protocols (Theorems 4.1, 4.2, 4.3, 4.7) have their own self-contained privacy proofs (Lemmas 4.4 and 4.10) and accuracy analyses (Lemmas 4.5 and 4.8). The selection lower bound similarly relies on the external level-1 Fourier inequality and on the same external reduction to the local model, with the local selection bound proved from privacy and accuracy. No load-bearing self-citation is used; the cited works by the authors' own group in the related-work section are not inputs to the proofs. The only place where the paper notes that a stronger mutual-information bound would contradict the upper bounds is a consistency/tightness observation, not a circular derivation, because the upper bounds come from independent external constructions. The paper is self-contained against external benchmarks and no parameter is fitted and then renamed as a prediction. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (6)
- standard math Fano's inequality (Lemma 3.6)
- standard math Data processing inequality for total variation distance (Lemma 3.21)
- standard math Level-1 Fourier inequality for Boolean functions (Theorem 3.26, O'Donnell)
- standard math Binomial anti-concentration bound from Roos (2006), Eq. (15)
- domain assumption Cheu et al. Lemma 3.5: single-message shuffled (eps,delta)-DP implies (eps+ln n, delta)-local DP
- domain assumption Privacy amplification by shuffling (Balle et al., Theorem A.1)
Cite this review
Pith. "Pith review of On the Power of Multiple Anonymous Messages." pith.science (2026). https://pith.science/paper/4JJFQ3EL
@misc{pith2026190811358,
author = {Pith},
title = {Pith review of: On the Power of Multiple Anonymous Messages},
year = {2026},
howpublished = {\url{https://pith.science/paper/4JJFQ3EL}},
note = {Machine review of arXiv:1908.11358}
}
abstract
An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables non-interactive, differentially private protocols with error much smaller than what is possible in the local model, while relying on weaker trust assumptions than in the central model. In this paper, we study basic counting problems in the shuffled model and establish separations between the error that can be achieved in the single-message shuffled model and in the shuffled model with multiple messages per user. For the problem of frequency estimation for $n$ users and a domain of size $B$, we obtain: - A nearly tight lower bound of $\tilde{\Omega}( \min(\sqrt[4]{n}, \sqrt{B}))$ on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are essentially optimal for single-message protocols. A key ingredient in the proof is a lower bound on the error of locally-private frequency estimation in the low-privacy (aka high $\epsilon$) regime. - Protocols in the multi-message shuffled model with $poly(\log{B}, \log{n})$ bits of communication per user and $poly\log{B}$ error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms. For the related selection problem on a domain of size $B$, we prove: - A nearly tight lower bound of $\Omega(B)$ on the number of users in the single-message shuffled model. This significantly improves on the $\Omega(B^{1/17})$ lower bound obtained by Cheu et al. (Eurocrypt 2019), and when combined with their $\tilde{O}(\sqrt{B})$-error multi-message protocol, implies the first separation between single-message and multi-message protocols for this problem.
Figures
Forward citations
Cited by 1 Pith paper
-
Improving Utility and Security of the Shuffler-based Differential Privacy
Local hashing with an optimized output size and a new encrypted oblivious-shuffle protocol improve utility and attack-resistance in shuffler-based differential privacy.
Reference graph
Works this paper leans on
-
[1]
Test without trust: Optimal locally private distribution testing
[ACFT19] Jayadev Acharya, Cl ´ement Canonne, Cody Freitag, and Himanshu Tyagi. Test without trust: Optimal locally private distribution testing. In AISTATS, pages 2067–2076,
-
[3]
Improved Summation from Shuffling
[BBGN19b] Borja Balle, James Bell, Adri`a Gasc´on, and Kobbi Nissim. Improved summation from shuffling.arXiv: 1909.11225,
work page Pith review arXiv 1909
-
[4]
Private summation in the multi-message shuffle model
[BBGN20] Borja Balle, James Bell, Adri `a Gasc ´on, and Kobbi Nissim. Private summation in the multi-message shuffle model. arXiv:2002.00817,
arXiv 2002
-
[5]
Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation
[EFM`20] ´Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arXiv preprint arXiv:2001.03618,
arXiv 2001
-
[7]
Scalable and differentially private distributed ag- gregation in the shuffled model
[GPV19] Badih Ghazi, Rasmus Pagh, and Ameya Velingker. Scalable and differentially private distributed ag- gregation in the shuffled model. arXiv:1906.08320,
arXiv 1906
-
[12]
Improving Utility and Security of the Shuffler-based Differential Privacy
[WXD`19] Tianhao Wang, Min Xu, Bolin Ding, Jingren Zhou, Ninghui Li, and Somesh Jha. Practical and robust privacy amplification with multi-party differential privacy. arXiv:1908.11515,
work page Pith review arXiv 1908
-
[2001]
Private aggregation from fewer anonymous messages
66 [GMPV19] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggregation from fewer anonymous messages. arXiv:1909.11073,
arXiv 1909
-
[2011]
Locally private k-means clustering
[Ste20] Uri Stemmer. Locally private k-means clustering. In Proceedings of the 2020 Symposium on Discrete Algorithms,
work page 2020
Show all 12 references
-
[2013]
Collecting and analyzing data from smart device users with local differential privacy
[NXY`16] Thong Nguyen, Xiaokui Xiao, Yin Yang, Sui Cheung Hui, Hyejin Shin, and Junbum Shin. Collecting and analyzing data from smart device users with local differential privacy. InarXiv:1606.05053,
-
[2014]
Understanding hierarchical methods for differentially private histograms
[QYL13] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. VLDB, 6(14):1954–1965,
1954
-
[2017]
Tight lower bounds for locally differentially private selection
[Ull18] Jonathan Ullman. Tight lower bounds for locally differentially private selection. In arXiv:1802.02638,
-
[2019]
Differentially private summation with multi-message shuffling
[BBGN19a] Borja Balle, James Bell, Adri `a Gasc ´on, and Kobbi Nissim. Differentially private summation with multi-message shuffling. CoRR, abs/1906.09116,
1906 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.