{"ID":2839338,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.15051","arxiv_id":"2511.15051","title":"Mutual Information Bounds in the Shuffle Model","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 $\\varepsilon_0$-differentially private mechanism before shuffling ($Y_i=\\mathcal{R}(X_i)$). Let $\\boldsymbol{Z} = (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 \\emph{basic configuration}, where the target user's message follows $Y_1 \\sim P$ and the remaining users' messages are i.i.d.\\ samples from $Q$, i.e., $Y_2,\\dots,Y_n \\sim Q$. We derive asymptotic expressions for the mutual information quantities $I(Y_1;\\boldsymbol{Z})$ and $I(K;\\boldsymbol{Z})$ as $n \\to \\infty$, 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 $\\varepsilon_0$-DP mechanism, the overall leakage satisfies $I(K; \\boldsymbol{Z}) \\le 2\\varepsilon_0$ and $I(X_1; \\boldsymbol{Z}\\mid (X_i)_{i=2}^n) \\le (e^{\\varepsilon_0}-1)/(2n) + O(n^{-3/2})$. These results bridge shuffle differential privacy and mutual-information-based privacy.","short_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=...","url_abs":"https://arxiv.org/abs/2511.15051","url_pdf":"https://arxiv.org/pdf/2511.15051v1","authors":"[\"Pengcheng Su\",\"Haibo Cheng\",\"Ping Wang\"]","published":"2025-11-19T02:44:59Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.CR\"]","methods":"[]","has_code":false}