Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy -- Poisson, Skellam, and Compound-Poisson Regimes

This paper establishes the first universality-breaking frontier in shuffle privacy by characterizing the asymptotic behavior of concentrated local randomizers that fail classical Gaussian limits, proving convergence to explicit Poisson, Skellam, and compound-Poisson shift experiments and providing a complete three-regime picture of shuffle privacy limits.

The Gist

Imagine you are trying to count how many people in a massive crowd are wearing red hats, but you want to do it without knowing who specifically is wearing one. This is the world of Differential Privacy.

To protect privacy, everyone in the crowd flips a coin. If it's heads, they tell the truth. If it's tails, they lie and say the opposite. Then, a "Shuffler" (a magical, anonymous mixer) collects all these answers, scrambles them so no one knows who said what, and publishes the final count.

Part I of this research series (published just before this one) showed that if the crowd is huge and the coin is slightly biased (but not too much), the final count behaves like a smooth, predictable bell curve (Gaussian distribution). It's like measuring the average height of a crowd: the noise averages out, and you get a nice, smooth result.

This paper (Part II) asks: What happens if we push the privacy settings to the absolute limit?

What if we make the coin so biased toward lying that people almost always tell the truth, but we do it in a way that the "noise" doesn't average out smoothly anymore? Instead of a smooth hill, the data starts to look like a series of sudden, sharp jumps.

Here is the breakdown of the paper's discoveries using simple analogies:

1. The Three Regimes of Privacy

The authors map out three distinct "worlds" of privacy, depending on how much privacy we demand and how big the crowd is.

• The "Smooth" World (Sub-critical):

  • The Analogy: Imagine a gentle rain. You can't see individual drops, just a steady mist.
  • The Math: The privacy is strong, but the "noise" is small and frequent. The result is a Gaussian (Bell Curve) distribution. This is the standard, safe zone covered in Part I.

• The "Critical" World (The Focus of This Paper):

  • The Analogy: Imagine a dry desert where rain is rare. When it does rain, it's a sudden, heavy downpour that creates a massive puddle instantly. You don't get a mist; you get distinct, giant splashes.
  • The Math: This happens when the privacy setting is tuned exactly to the edge of the crowd size. The "noise" isn't small anymore; it's rare but huge.
  • The Discovery: In this zone, the math stops being a bell curve and becomes Poisson (counting rare events) or Skellam (the difference between two rare events).
  • Why it matters: In the "Smooth" world, you can theoretically get perfect privacy if you wait long enough. In this "Critical" world, there is a hard floor. No matter how much you tweak the settings, there is always a tiny, non-zero chance that an attacker can guess the truth just because of a "lucky" rare event. It's like a "ghost" in the machine that never fully disappears.

• The "Broken" World (Super-critical):

  • The Analogy: The rain is so heavy that the river floods and washes away the banks.
  • The Math: The privacy setting is too weak. The "noise" is so loud that the signal is completely drowned out. The attacker can easily distinguish the truth. Privacy has collapsed.

2. The "Rare Jump" Phenomenon

In the "Critical" world, the paper explains that the data doesn't drift; it jumps.

• Poisson Shift: Imagine you are counting errors. In the smooth world, errors are tiny and frequent. In the critical world, errors are like earthquakes. They happen rarely, but when they do, they move the entire statistic by a huge amount. The math describing this is the Poisson distribution (which counts how many earthquakes happen in a year).
• Skellam Shift: Now imagine two teams of people flipping coins. If you look at the difference between Team A's errors and Team B's errors, and both are rare but huge, the math becomes the Skellam distribution. It's like counting the difference between two rare earthquakes.

3. The "Floor" of Privacy

One of the most surprising findings is the $\delta$-floor (the privacy floor).

• The Old View: In the smooth world, if you ask for enough privacy, the risk of leaking a secret can be made effectively zero.
• The New Reality: In this critical "rare jump" world, there is a minimum risk that you cannot erase. Even with infinite computing power, there is a tiny probability (like 1 in a million) that the "rare jump" reveals the secret.
• The Metaphor: In the smooth world, you can build a wall so high that no one can climb it. In the critical world, the wall has a hole at the bottom. No matter how high you build the rest of the wall, that hole remains. This paper calculates exactly how big that hole is.

4. Why This Matters for Real Life

This isn't just abstract math; it tells engineers how to build privacy tools.

• Don't push too hard: If you try to maximize privacy by making the local randomizer extremely biased (to get the "best" protection), you might accidentally push the system into this "Critical" zone.
• The Trap: You might think you are getting more privacy, but you are actually hitting a wall where the math changes, and a tiny, unavoidable leak appears.
• The Guide: This paper provides a map. It tells engineers: "If you tune your settings to $X$, you get a smooth bell curve. If you tune it to $Y$, you hit the 'Critical' zone with rare jumps and a privacy floor. If you go to $Z$, privacy breaks completely."

Summary

This paper is the warning label for the edge of privacy technology. It says: "The rules change when you get too close to the limit. The smooth, predictable world of averages turns into a world of rare, massive jumps. And in that world, there is a tiny, permanent crack in the armor that you can never fully seal."

It replaces the idea of "perfectly smooth privacy" with a more realistic, jagged picture where rare events dictate the rules.

Technical Summary

This is a detailed technical summary of "Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy—Poisson, Skellam, and Compound-Poisson Regimes" by Alex Shvets (March 2026).

1. Problem Statement and Context

The paper addresses the asymptotic behavior of the Shuffle Model for Differential Privacy (DP) when the local privacy parameter $\epsilon_0$ scales with the population size $n$.

• Background: Part I of this series established that when the local randomizer is fixed and has full support bounded away from zero, the shuffle mechanism converges to a Gaussian limit (satisfying Local Asymptotic Normality - LAN and Gaussian Differential Privacy - GDP).
• The Gap: In practice, local privacy $\epsilon_0(n)$ often grows with $n$ (e.g., to reduce estimator variance). In this regime, the "small increment" assumption of the Central Limit Theorem (CLT) fails. Rare local outcomes can cause macroscopic jumps ($\Theta(1)$) in the log-likelihood ratio at the population scale.
• Objective: The paper characterizes the critical frontier where classical Gaussian approximations break down. It aims to derive sharp non-Gaussian limit theories (Poisson, Skellam, Compound-Poisson) for the shuffle mechanism under specific scaling regimes where the local error probability is of order $O(1/n)$.

2. Methodology

The authors employ a rigorous framework based on Statistical Experiment Theory (Le Cam theory) and Probability Limit Theorems.

• Le Cam Distance: The primary metric for convergence is the Le Cam distance ($\Delta$) between binary experiments. The paper proves convergence in total variation (TV) distance between the finite-$n$ shuffle transcript laws and their limiting distributions, which implies convergence of the Le Cam distance.
• Scaling Regimes: The analysis focuses on the critical scaling where the parameter $a_n = e^{\epsilon_0(n)}/n$ converges to a constant $c^2 \in (0, \infty)$.
  • Sub-critical: $a_n \to 0$ (Gaussian regime, covered in Part I).
  • Critical: $a_n \to c^2$ (Non-Gaussian regime, the focus of this paper).
  • Super-critical: $a_n \to \infty$ (Privacy collapses).
• Approximation Techniques:
  • Poisson Approximation: Using explicit coupling bounds (Chen-Stein/Le Cam type) to approximate Binomial counts of rare events with Poisson distributions.
  • Skellam Distribution: Modeling the difference of two independent Poisson variables for proportional compositions.
  • Compound Poisson: Extending to general finite alphabets where multiple rare error types occur.
  • Hybrid Decomposition: For "two-dominant" regimes, decomposing the statistic into a Gaussian component (dominant fluctuations) and a Compound-Poisson component (rare jumps).

3. Key Contributions and Results

The paper establishes a three-regime picture of shuffle privacy, with the critical regime being the novel contribution.

A. Canonical Neighboring Pair: Poisson-Shift Limit (Section 3)

• Scenario: Binary Randomized Response (RR) with a dataset of all zeros vs. one "one" ($k=0$ vs. $k=1$).
• Scaling: $e^{\epsilon_0(n)} \sim c^2 n$.
• Result: The shuffle transcript converges in TV distance to a Poisson-shift experiment.
  • Null hypothesis $P_\infty \sim \text{Poi}(\lambda)$ where $\lambda = c^{-2}$.
  • Alternative hypothesis $Q_\infty \sim 1 + \text{Poi}(\lambda)$.
• Privacy Curve: The limiting privacy curve is an explicit series involving Poisson tails.
• Key Insight (The $\delta$-floor): Unlike the Gaussian regime where $\delta(\epsilon) \to 0$ as $\epsilon \to \infty$, the Poisson limit exhibits a support-mismatch floor. Since $Q_\infty$ has no mass at 0 while $P_\infty$ does, the two-sided privacy curve is bounded below by $e^{-\lambda} = e^{-1/c^2}$ for all $\epsilon$. This represents a fundamental limit on privacy amplification in this regime.

B. Proportional Compositions: Skellam-Shift Limit (Section 4)

• Scenario: Binary RR where the fraction of ones $\pi = k/n$ converges to a constant $\pi \in (0, 1)$.
• Result: The centered histogram converges to a Skellam-shift experiment.
  • $P_\infty \sim \text{Skellam}(\lambda_0, \lambda_1)$ where $\lambda_0 = (1-\pi)c^{-2}$ and $\lambda_1 = \pi c^{-2}$.
  • $Q_\infty \sim 1 + \text{Skellam}(\lambda_0, \lambda_1)$.
• Privacy Curve: The limiting curve is derived explicitly using the Skellam probability mass function (involving modified Bessel functions).
• Key Insight: For interior compositions ($\pi \in (0, 1)$), the support of the Skellam distribution is the entire integers $\mathbb{Z}$. Consequently, there is no support-mismatch floor; the privacy curve decays to zero as $\epsilon \to \infty$, unlike the boundary case. The Skellam family interpolates continuously between the two Poisson-shift families at the boundaries $\pi=0$ and $\pi=1$.

C. General Alphabets: Multivariate Compound-Poisson Limit (Section 5)

• Scenario: General finite output alphabets with "sparse-error" critical regimes (dominant outputs have probability $1-O(1/n)$, others$O(1/n)$).
• Result: The centered histogram converges to a Multivariate Compound-Poisson shift.
  • The limit is a vector of independent Poisson variables representing counts of specific rare errors.
  • The shift depends on the composition $\pi$.
• Hybrid Regime (Two-Dominant Outputs): If the dominant mass is split between two outputs (not collapsing to one), the limit is a Hybrid Gaussian/Compound-Poisson distribution.
  • The dominant block fluctuates on the $\sqrt{n}$ scale (Gaussian).
  • The rare errors form a Compound-Poisson jump field.
  • The paper proves that while the full experiment does not converge in TV (due to the continuous Gaussian part), the privacy curves still converge, and the Gaussian component acts as a common factor that does not affect the privacy profile (via conditional smoothing arguments).

D. Phase Diagram and Super-Critical Regime (Section 6)

• Sub-critical ($a_n \to 0$): Gaussian/GDP limits (Part I).
• Critical ($a_n \to c^2$): Poisson/Skellam/Compound-Poisson limits (This paper).
• Super-critical ($a_n \to \infty$): Privacy collapses. The total variation distance between neighboring datasets approaches 1, meaning they are asymptotically distinguishable regardless of the privacy budget.

4. Significance and Implications

1. Breaking Universality: The paper demonstrates that the "Gaussian universality" of the shuffle model is fragile. Once the local privacy parameter scales such that the expected number of errors is $O(1)$, the limit theory fundamentally changes from Gaussian to Poisson-type processes.
2. Privacy Floor: It identifies a hard limit on privacy amplification in the critical regime for boundary compositions. Even with infinite $\epsilon$, a non-zero $\delta$ remains due to the probability of zero errors in the limit. This challenges the intuition that increasing $\epsilon$ always drives $\delta$ to zero.
3. Design Guidelines: The results provide a phase diagram for protocol designers:
   • To achieve Gaussian-like behavior, keep $e^{\epsilon_0} \ll n$.
   • To operate near the critical boundary ($e^{\epsilon_0} \approx n$), one must use Poisson/Skellam calibration, not Gaussian.
   • If $e^{\epsilon_0} \gg n$, privacy is lost entirely.
4. Comparison with Existing Bounds: The paper shows that existing amplification bounds (e.g., Balle et al., Feldman et al.) fail in this regime.
   • Balle et al.'s "blanket" decomposition relies on many small contributions, which does not hold when the number of errors is $O(1)$.
   • Feldman et al.'s $n^{-1/2}$ amplification template misses the Poisson floor.
5. Le Cam Theory Application: By framing the problem in terms of Le Cam distance and explicit TV rates ($O(1/n)$), the paper provides a rigorous foundation for comparing statistical experiments, going beyond simple asymptotic distributions.

5. Conclusion

"Universal Shuffle Asymptotics, Part II" completes the picture of shuffle privacy limits by characterizing the critical non-Gaussian frontier. It establishes that when local privacy scales such that the expected number of errors is constant, the shuffle mechanism converges to Poisson, Skellam, or Compound-Poisson shift experiments. This reveals a fundamental "floor" in privacy for certain compositions and provides the necessary mathematical tools to analyze and design privacy protocols in this high-privacy, high-variance regime.