論文の概要: Mutual Information Bounds in the Shuffle Model
- arxiv url: http://arxiv.org/abs/2511.15051v1
- Date: Wed, 19 Nov 2025 02:44:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-20 15:51:28.597965
- Title: Mutual Information Bounds in the Shuffle Model
- Title（参考訳）: シャッフルモデルにおける相互情報境界
- Authors: Pengcheng Su, Haibo Cheng, Ping Wang,
- Abstract要約: 本稿では,情報理論の観点から,単一メッセージシャッフルモデルに関する最初の体系的研究について述べる。
シャッフルのみの設定とシャッフルのみの設定の2つのルールを分析した。
シャッフルDP設定では,情報漏洩に関する情報理論上の上限を確立する。
- 参考スコア（独自算出の注目度）: 7.289625261239043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
- Abstract（参考訳）: シャッフルモデルは、ランダムな置換によってユーザのレポートを匿名化することで、プライバシを高める。
本稿では,情報理論の観点から,単一メッセージシャッフルモデルに関する最初の体系的研究について述べる。
シャッフルのみの設定(Y_i=X_i$)とシャッフルDPの設定(Y_i=\mathcal{R}(X_i)$)である。
$\boldsymbol{Z} = (Y_{σ(i)})_i$ は、一様ランダムな置換 $σ$ によって生成されるシャッフルシーケンスを表し、$K = σ^{-1}(1)$ はシャッフル後のユーザー1のメッセージの位置を表す。
シャッフルのみの設定では、ターゲットユーザのメッセージは$Y_1 \sim P$に従って、残りのユーザのメッセージは$Q$、すなわち$Y_2,\dots,Y_n \sim Q$のサンプルである。
我々は、相互情報量$I(Y_1;\boldsymbol{Z})$および$I(K;\boldsymbol{Z})$ as $n \to \infty$に対する漸近式を導出し、この分析フレームワークが、不均一なユーザ分布を持つ設定にどのように自然に拡張するかを実証する。
シャッフルDP設定では,情報漏洩に関する情報理論上の上限を確立する。
各ユーザが$\varepsilon_0$-DPメカニズムを適用すると、全体的なリークは$I(K; \boldsymbol{Z}) \le 2\varepsilon_0$と$I(X_1; \boldsymbol{Z}\mid (X_i)_{i=2}^n) \le (e^{\varepsilon_0}-1)/(2n) + O(n^{-3/2})$を満たす。
これらの結果は、シャッフルの差分プライバシーと相互情報に基づくプライバシーを橋渡しする。
関連論文リスト
- Bayesian Advantage of Re-Identification Attack in the Shuffle Model [7.289625261239043]
ランダムなメッセージ置換によってデータを匿名化するシャッフルモデルは、暗号や差分プライバシーにおいて広く採用されている。
本研究は,シャッフルモデルに基づくユーザのメッセージの再識別におけるベイズ的優位性に関する最初の体系的研究である。
論文 参考訳（メタデータ） (2025-11-05T06:03:56Z) - Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - User-Level Private Learning via Correlated Sampling [49.453751858361265]
我々は、各ユーザが$m$のサンプルを持ち、プライバシ保護が各ユーザのデータレベルで実施される設定について検討する。
この設定では、より少ない数のユーザーで学習できることが示されます。
論文 参考訳（メタデータ） (2021-10-21T15:33:53Z) - Locally differentially private estimation of nonlinear functionals of
discrete distributions [9.028773906859541]
離散分布の非線形関数を局所的差分プライバシーの文脈で推定する問題について検討する。
alpha$-locally differentially private (LDP) サンプルのみが公開されているが、'local' という用語は、各$z_i$が1つの個々の$x_i$を使って生成されることを意味する。
パワー和関数 $F_gamma = sum_k=1K p_kgamma$, $gamma > 0$ を $K, n の関数として推定する二次リスクの挙動を記述する。
論文 参考訳（メタデータ） (2021-07-08T16:11:10Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。