論文の概要: Bayesian Advantage of Re-Identification Attack in the Shuffle Model

• arxiv url: http://arxiv.org/abs/2511.03213v1
• Date: Wed, 05 Nov 2025 06:03:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 18:19:32.350191
• Title: Bayesian Advantage of Re-Identification Attack in the Shuffle Model
• Title（参考訳）: シャッフルモデルにおける再同定攻撃のベイズ的アドバンテージ
• Authors: Pengcheng Su, Haibo Cheng, Ping Wang,
• Abstract要約: ランダムなメッセージ置換によってデータを匿名化するシャッフルモデルは、暗号や差分プライバシーにおいて広く採用されている。 本研究は,シャッフルモデルに基づくユーザのメッセージの再識別におけるベイズ的優位性に関する最初の体系的研究である。
• 参考スコア（独自算出の注目度）: 7.289625261239043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The shuffle model, which anonymizes data by randomly permuting user messages, has been widely adopted in both cryptography and differential privacy. In this work, we present the first systematic study of the Bayesian advantage in re-identifying a user's message under the shuffle model. We begin with a basic setting: one sample is drawn from a distribution $P$, and $n - 1$ samples are drawn from a distribution $Q$, after which all $n$ samples are randomly shuffled. We define $\beta_n(P, Q)$ as the success probability of a Bayes-optimal adversary in identifying the sample from $P$, and define the additive and multiplicative Bayesian advantages as $\mathsf{Adv}_n^{+}(P, Q) = \beta_n(P,Q) - \frac{1}{n}$ and $\mathsf{Adv}_n^{\times}(P, Q) = n \cdot \beta_n(P,Q)$, respectively. We derive exact analytical expressions and asymptotic characterizations of $\beta_n(P, Q)$, along with evaluations in several representative scenarios. Furthermore, we establish (nearly) tight mutual bounds between the additive Bayesian advantage and the total variation distance. Finally, we extend our analysis beyond the basic setting and present, for the first time, an upper bound on the success probability of Bayesian attacks in shuffle differential privacy. Specifically, when the outputs of $n$ users--each processed through an $\varepsilon$-differentially private local randomizer--are shuffled, the probability that an attacker successfully re-identifies any target user's message is at most $e^{\varepsilon}/n$.
• Abstract（参考訳）: ユーザメッセージをランダムに置換することでデータを匿名化するシャッフルモデルは、暗号化と差分プライバシーの両方で広く採用されている。 本研究は,シャッフルモデルに基づくユーザのメッセージの再識別におけるベイズ的優位性に関する最初の体系的研究である。 1つのサンプルが$P$から引き出され、$n - 1$サンプルが$Q$から引き出され、その後、すべての$n$サンプルがランダムにシャッフルされます。 P からサンプルを識別するベイズ最適逆数(英語版)の確率として $\beta_n(P, Q)$ を定義し、加法的および乗法的ベイズ的利点を $\mathsf{Adv}_n^{+}(P, Q) = \beta_n(P, Q) - \frac{1}{n}$ と $\mathsf{Adv}_n^{\times}(P, Q) = n \cdot \beta_n(P, Q)$ と定義する。 我々は、いくつかの代表的なシナリオでの評価とともに、$\beta_n(P, Q)$の正確な解析式と漸近的特徴付けを導出する。 さらに,加法ベイズ効果と全変動距離との間に(ほぼ)密接な相互境界を確立する。 最後に、我々は分析を基本的な設定を超えて拡張し、初めて、シャッフル差分プライバシーにおけるベイズ攻撃の成功確率に上限を付ける。 具体的には、$n$ユーザ--$\varepsilon$-differentially private local randomizer--がシャッフルされると、攻撃者がターゲットユーザーのメッセージを再識別する確率は、最大$e^{\varepsilon}/n$である。

関連論文リスト

• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。 また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
  論文  参考訳（メタデータ） (2025-09-19T17:41:15Z)
• Near-optimal algorithms for private estimation and sequential testing of collision probability [1.62060928868899]
  我々は、$(alpha, beta)$-local differential privacy を満たすアルゴリズムを記述し、最大$epsilon$の誤差で衝突確率を推定する。 また、衝突確率を$epsilon$で分離した衝突確率値を区別できる逐次テストアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-18T17:12:15Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Discrete Distribution Estimation under User-level Local Differential Privacy [37.65849910114053]
  ユーザレベルの局所差分プライバシー(LDP)に基づく離散分布推定について検討する。 ユーザレベルの$varepsilon$-LDPでは、各ユーザは$mge1$サンプルを持ち、すべての$m$サンプルのプライバシを同時に保存する必要がある。
  論文  参考訳（メタデータ） (2022-11-07T18:29:32Z)
• Bayesian Learning via Q-Exponential Process [10.551294837978363]
  正規化は最適化、統計、機械学習における最も基本的なトピックの1つである。 本研究では、$q$-指数分布(密度比で)$exp( frac12|u|q)$を、関数の正規化に対応する$Q$-指数(Q-EP)プロセスというプロセスに一般化する。
  論文  参考訳（メタデータ） (2022-10-14T17:37:14Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• User-Level Private Learning via Correlated Sampling [49.453751858361265]
  我々は、各ユーザが$m$のサンプルを持ち、プライバシ保護が各ユーザのデータレベルで実施される設定について検討する。 この設定では、より少ない数のユーザーで学習できることが示されます。
  論文  参考訳（メタデータ） (2021-10-21T15:33:53Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。