Mutual Information Bounds in the Shuffle Model

2025/11/19 by Su, Pengcheng, Cheng, Haibo, Wang, Ping
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2511.15051

Abstract

The shuffle model enhances privacy by anonymizing users' reports through random permutation. This paper presents the first systematic study of the single-message shuffle model from an information-theoretic perspective. We analyze two regimes: the shuffle-only setting, where each user directly submits its message (Y_i=X_i), and the shuffle-DP setting, where each user first applies a local ε₀-differentially private mechanism before shuffling (Y_i=R(X_i)). Let \boldsymbolZ = (Y_σ(i))_i denote the shuffled sequence produced by a uniformly random permutation σ, and let K = σ^-1(1) represent the position of user 1's message after shuffling. For the shuffle-only setting, we focus on a tractable yet expressive basic configuration, where the target user's message follows Y₁ ∼ P and the remaining users' messages are i.i.d. samples from Q, i.e., Y₂,…,Y_n ∼ Q. We derive asymptotic expressions for the mutual information quantities I(Y₁;\boldsymbolZ) and I(K;\boldsymbolZ) as n → ∞, and demonstrate how this analytical framework naturally extends to settings with heterogeneous user distributions. For the shuffle-DP setting, we establish information-theoretic upper bounds on total information leakage. When each user applies an ε₀-DP mechanism, the overall leakage satisfies I(K; \boldsymbolZ) ≤ 2ε₀ and I(X₁; \boldsymbolZ| (X_i)_i=2ⁿ) ≤ (e^ε₀-1)/(2n) + O(n^-3/2). These results bridge shuffle differential privacy and mutual-information-based privacy.

Citations

• Bayesian Advantage of Re-Identification Attack in the Shuffle Model
• Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling
• On Local Mutual-Information Privacy
• Analyzing the Shuffle Model through the Lens of Quantitative Information Flow
• Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy
• Information-Theoretic Approaches to Differential Privacy
• Differential Privacy in the Shuffle Model: A Survey of Separations
• Differentially Private Histograms in the Shuffle Model from Fake Users
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic Privacy
• The Privacy Blanket of the Shuffle Model
• On the Complexity of Anonymous Communication Through Public Networks
• Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
• Collecting Telemetry Data Privately
• Atom: Horizontally Scaling Strong Anonymity
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Privacy Against Statistical Inference

Related

• Tight Accounting in the Shuffle Model of Differential Privacy
• Analyzing the Shuffle Model through the Lens of Quantitative Information Flow
• The Privacy Blanket of the Shuffle Model
• Enhanced Privacy Bound for Shuffle Model with Personalized Privacy
• Walking to Hide: Privacy Amplification via Random Message Exchanges in Network