Growing Alphabets Do Not Automatically Amplify Shuffle Privacy: Obstruction, Estimation Bounds, and Optimal Mechanism Design

Alex Shvets · 2026

Read Growing Alphabets Do Not Automatically Amplify Shuffle Privacy: Obstruction, Estimation Bounds, and Optimal Mechanism Design by Alex Shvets (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-2603-18080.txt.

Introduction

Shvets studies shuffle privacy experiments as alphabets grow, for d-ary channels with local privacy. The pairwise likelihood-ratio law governs the whole shuffled histogram experiment. Alphabet growth helps privacy only when the worst pairwise law collapses to a point mass. He proves a sharp endpoint rule for pairwise chi-squared cost and builds saturating families. Symmetrization cuts the design space to permutation-equivariant channels, where augmented GRR is best at low budgets.

Catalog record

CREATORAlex Shvets
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85406
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18080

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Growing Alphabets Do Not Automatically Amplify Shuffle Privacy: Obstruction, Estimation Bounds, and Optimal Mechanism Design Alex Shvets Abstract . We study one-step neighboring shuffle experiments for ε 0 \varepsilon_{0} -locally differentially private channels W d : [ d ] → Δ ⁡ ( 𝒴 ) W_{d}:[d]\to\Delta(\mathcal{Y}) along growing alphabets d → ∞ d\to\infty , and the design of local randomizers for frequency estimation under a canonical pairwise χ 2 \chi^{2} -budget. On the privacy side, we prove an exact compression theorem: the canonical shuffled histogram experiment depends only on the pushforward law of the pairwise likelihood ratio w a ​ b , d ​ ( y ) = W d ​ ( y ∣ b ) / W d ​ ( y ∣ a ) w_{ab,d}(y)=W_{d}(y\mid b)/W_{d}(y\mid a) under the null row. We establish a universal extremal bound χ 2 ( W d ( ⋅ ∣ b ) ∥ W d ( ⋅ ∣ a ) ) ≤ ( e ε 0 − 1 ) 2 / e ε 0 \chi^{2}(W_{d}(\cdot\mid b)\,\|\,W_{d}(\cdot\mid a))\leq(e^{\varepsilon_{0}}-1)^{2}/e^{\varepsilon_{0}} , sharp iff the likelihood ratio is two-point. We construct explicit obstruction families on every even alphabet for which the exact shuffled privacy curve is identical to binary randomized response for all d d , and prove a sharp diluting/persistent dichotomy governed by the pairwise χ 2 \chi^{2} divergence. On the estimation side, we prove a universal lower bound: for every channel W W with arbitrary finite output alphabet 𝒴 \mathcal{Y} and every estimator, the minimax frequency-estimation risk is at least of order ( d − 1 ) / ( n ​ χ ∗ ​ ( W ) ) (d-1)/(n\chi_{\ast}(W)) in the regime n ​ χ ∗ ​ ( W ) ≳ d 2 n\chi_{\ast}(W)\gtrsim d^{2} , where χ ∗ ​ ( W ) \chi_{\ast}(W) is the worst-case pairwise χ 2 \chi^{2} . A symmetrization theorem shows that permutation-equivariant channels are without loss of generality for the uniform-point Fisher criterion. On the design side, we optimize the local randomizer for frequency estimation under a canonical pairwise χ 2 \chi^{2} -budget alone, without a simultaneous uniform ε 0 \varepsilon_{0} -LDP cap. We show that calibrated GRR is not universally optimal. The optimal mechanism within the natural-orbit class of GRR blocks with null refinements is an augmented GRR channel: a fraction p p of users applies an aggressive GRR with λ ∗ = d − 1 \lambda_{\ast}=\sqrt{d-1} , while the remaining fraction sends a common null symbol. This thinning principle—concentrate the local signal on a random informative subset of messages—is specific to the shuffle model and has no counterpart in local differential privacy. In the low-budget regime 0 < C ≤ C ∗ ​ ( d ) 0<C\leq C_{\ast}(d) , we then prove that augmented GRR is optimal among all permutation-equivariant channels with arbitrary finite output alphabet, up to conditionally identical output refinements, for the projected unbiased inverse-estimator risk. We further prove that GRR is the unique matched-budget optimizer within the entire subset-selection family. 2020 Mathematics Subject Classification 62B15, 68P27, 60F05 1. Introduction Let n\geq 1 users hold private inputs x_{1},\dots,x_{n} . In the shuffle model each user applies a local randomizer and a trusted shuffler releases the multiset of local messages, equivalently the released histogram. This model, initiated by the Encode–Shuffle–Analyze architecture of Bittau et al. [ 3 ] , sits between local and central differential privacy and yields privacy amplification by anonymity [ 4 , 5 , 1 , 6 , 7 , 15 ] . For fixed finite output alphabets the asymptotic structure of neighboring shuffle experiments is now rather well understood. Part I of the trilogy [ 12 ] develops a sharp Gaussian/LAN/GDP theory in the full-support regime; Part II [ 13 ] identifies critical Poisson, Skellam, and compound-Poisson limits when the local randomizer itself becomes increasingly concentrated; Part III [ 14 ] describes the finite-alphabet dominant-block quotient geometry and its hybrid Gaussian–compound-Poisson limit. The present paper addresses a different question, left open in the trilogy and particularly pointed in the discussion of Part III: what happens when the output alphabet grows? A first guess is that more output symbols should automatically help privacy. This is indeed what happens for d -ary generalized randomized response (GRR): if one input changes from a to b , then only the two output coordinates a and b carry nontrivial pairwise likelihood-ratio values, while the remaining d-2 coordinates are pairwise neutral. Consequently the pairwise \chi^{2} divergence is of order d^{-1} , and the corresponding shuffled privacy collapses as d\to\infty . This d -dependent improvement for k -ary randomized response was first established theoretically by Feldman, McMillan, and Talwar [ 6 , Corollary 4.2] , who proved a blanket privacy bound of order e^{\varepsilon_{0}}/\!\sqrt{kn} for k -RR. Our Proposition 7.1 gives the exact experiment-level counterpart. The main message of the present paper is twofold. First, the improvement of GRR is mechanism-specific, not universal. There exist explicit \varepsilon_{0} -LDP channels on d symbols for which the pairwise \chi^{2} divergence stays constant as d\to\infty , and for which the exact shuffled privacy curve of a worst-case neighboring pair is identical to the binary randomized-response privacy curve for every d . Thus growing alphabets do not automatically amplify shuffle privacy. Second, the shuffle model has its own optimal mechanism geometry, fundamentally different from local DP. The locally optimal mechanism (GRR at matched budget) is not shuffle-optimal; the shuffle-optimal mechanism concentrates an aggressive local signal on a random fraction of users. In the low-budget regime this thinned augmented-GRR construction is, in fact, optimal among all permutation-equivariant channels for the projected unbiased inverse-estimator risk, up to conditionally identical output refinements. The correct invariant is not the raw alphabet size d , nor the ambient rank of the channel matrix, nor the number of output coordinates on which rows differ. It is the pushforward law of the pairwise likelihood ratio w_{ab,d}(y):=\frac{W_{d}(y\mid b)}{W_{d}(y\mid a)} under the null row W_{d}(\cdot\mid a) . This law lives on the fixed compact interval [e^{-\varepsilon_{0}},e^{\varepsilon_{0}}] and completely determines the canonical one-step neighboring shuffle experiment. We now summarize the main results, organized into three groups: privacy structure, estimation bounds, and mechanism design. I. Privacy structure (A) Exact likelihood-ratio quotient compression (Theorem 3.2 ). For the canonical neighboring pair in which one input changes from a to b , the full histogram experiment is exactly equivalent to the multinomial experiment on the likelihood-ratio level sets of w_{ab,d} . The proof is exact and finite- n . (B) Universal extremal \chi^{2} bound (Theorem 4.2 ). For every \varepsilon_{0} -LDP channel and every pair a\neq b , \chi^{2}\!\bigl(W_{d}(\cdot\mid b)\,\|\,W_{d}(\cdot\mid a)\bigr)\leq\frac{(e^{\varepsilon_{0}}-1)^{2}}{e^{\varepsilon_{0}}}. The bound is sharp, and equality holds precisely for endpoint two-point likelihood-ratio laws. (C) Explicit obstruction family (Theorem 5.2 ). For every even d we construct a full-support cyclic half-block channel W_{d} for which, along an opposite pair of inputs, the likelihood-ratio law is the same fixed two-point law for all d . Hence the exact shuffled privacy curve is exactly the binary randomized-response curve for all d . (D) Sharp geometric dichotomy (Theorem 6.2 ). A channel family \{W_{d}\} is diluting iff its worst-case pairwise likelihood-ratio law collapses to \delta_{1} , equivalently iff its worst-case pairwise \chi^{2} divergence tends to zero. It is persistent iff

Read the complete text