論文の概要: On the Round Complexity of the Shuffle Model
- arxiv url: http://arxiv.org/abs/2009.13510v1
- Date: Mon, 28 Sep 2020 17:57:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 22:41:50.690199
- Title: On the Round Complexity of the Shuffle Model
- Title(参考訳): シャッフルモデルのラウンド複素性について
- Authors: Amos Beimel, Iftach Haitner, Kobbi Nissim, Uri Stemmer
- Abstract要約: 分散微分プライベート計算の実行可能なモデルとして、微分プライバシのシャッフルモデルが提案された。
両当事者がシャッフルの1ラウンドで秘密のメッセージを送信し、まず秘密の鍵を作らなくてもよいことを示す。
そこで本研究では,正当性の仮定を必要としないシャッフルモデルにおける微分プライベート計算について検討する。
- 参考スコア(独自算出の注目度): 25.454520433661646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The shuffle model of differential privacy was proposed as a viable model for
performing distributed differentially private computations. Informally, the
model consists of an untrusted analyzer that receives messages sent by
participating parties via a shuffle functionality, the latter potentially
disassociates messages from their senders. Prior work focused on one-round
differentially private shuffle model protocols, demonstrating that
functionalities such as addition and histograms can be performed in this model
with accuracy levels similar to that of the curator model of differential
privacy, where the computation is performed by a fully trusted party.
Focusing on the round complexity of the shuffle model, we ask in this work
what can be computed in the shuffle model of differential privacy with two
rounds. Ishai et al. [FOCS 2006] showed how to use one round of the shuffle to
establish secret keys between every two parties. Using this primitive to
simulate a general secure multi-party protocol increases its round complexity
by one. We show how two parties can use one round of the shuffle to send secret
messages without having to first establish a secret key, hence retaining round
complexity. Combining this primitive with the two-round semi-honest protocol of
Applebaun et al. [TCC 2018], we obtain that every randomized functionality can
be computed in the shuffle model with an honest majority, in merely two rounds.
This includes any differentially private computation. We then move to examine
differentially private computations in the shuffle model that (i) do not
require the assumption of an honest majority, or (ii) do not admit one-round
protocols, even with an honest majority. For that, we introduce two
computational tasks: the common-element problem and the nested-common-element
problem, for which we show separations between one-round and two-round
protocols.
- Abstract(参考訳): 分散微分プライベート計算の実行可能なモデルとして、微分プライバシのシャッフルモデルが提案された。
形式的には、モデルは信頼できないアナライザで構成されており、参加者からシャッフル機能を介してメッセージを受け取り、後者は送信者からのメッセージを解離する可能性がある。
先行研究は1ラウンドの差分プライベートシャッフルモデルプロトコルに焦点をあて、完全信頼の当事者が計算を行う差分プライバシーのキュレーターモデルと同様の精度で、加算やヒストグラムのような関数をこのモデルで実行できることを実証した。
シャッフルモデルのラウンド複雑性に着目し,2ラウンドの差分プライバシのシャッフルモデルに何が計算できるのかを本研究で問う。
Ishaiら。
FOCS 2006]は、2つのパーティ間で秘密鍵を確立するためにシャッフルの1ラウンドの使用方法を示した。
一般的なセキュアなマルチパーティプロトコルをシミュレートするためにこのプリミティブを使用すると、ラウンドの複雑さが1つ増える。
2つのパーティがシャッフルの1ラウンドを使って秘密のメッセージを送る方法を示します。
このプリミティブとApplebaunらの2ラウンド半正直なプロトコルを組み合わせる。
[TCC 2018]では、ランダム化された全ての機能は、正直な多数派を持つシャッフルモデルで、わずか2ラウンドで計算できる。
これには微分プライベートな計算が含まれる。
次にシャッフルモデルにおける微分プライベート計算について検討する。
(i)正直な多数派を仮定する必要はない。
(二)正直な多数派であっても一括のプロトコルは認めない。
そのため,1ラウンドプロトコルと2ラウンドプロトコルの分離を示す共通要素問題とネスト共通要素問題という2つの計算タスクを導入する。
関連論文リスト
- Learn What You Need in Personalized Federated Learning [53.83081622573734]
$textitLearn2pFed$は、アルゴリズムに基づくパーソナライズされたフェデレーション学習フレームワークである。
我々は、textitLearn2pFed$が、従来のパーソナライズされたフェデレーション学習方法よりも大幅に優れていることを示す。
論文 参考訳(メタデータ) (2024-01-16T12:45:15Z) - Just One Byte (per gradient): A Note on Low-Bandwidth Decentralized
Language Model Finetuning Using Shared Randomness [86.61582747039053]
分散環境での言語モデルトレーニングは、交換の通信コストによって制限される。
分散微調整を低帯域幅で行うために,共有ランダムネスを用いた最近の作業を拡張した。
論文 参考訳(メタデータ) (2023-06-16T17:59:51Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳(メタデータ) (2023-01-29T20:42:54Z) - Learning from aggregated data with a maximum entropy model [73.63512438583375]
我々は,観測されていない特徴分布を最大エントロピー仮説で近似することにより,ロジスティック回帰と類似した新しいモデルが,集約データからのみ学習されることを示す。
我々は、この方法で学習したモデルが、完全な非凝集データでトレーニングされたロジスティックモデルに匹敵するパフォーマンスを達成することができるという、いくつかの公開データセットに関する実証的な証拠を提示する。
論文 参考訳(メタデータ) (2022-10-05T09:17:27Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳(メタデータ) (2021-07-30T15:25:13Z) - Renyi Differential Privacy of the Subsampled Shuffle Model in
Distributed Learning [7.197592390105457]
クライアントは、プライバシを必要とするサーバとのインタラクションを通じて、学習モデルを反復的に構築する分散学習フレームワークで、プライバシを研究する。
最適化とフェデレートラーニング(FL)パラダイムによって動機付けられ、各ラウンドで少数のデータサンプルがランダムにサブサンプリングされた場合に焦点を当てる。
より強力なローカルプライバシ保証を得るために,各クライアントがローカルディファレンシャル・プライベート(LDP)機構を用いて応答をランダム化するシャッフルプライバシ・モデルを用いてこれを検証した。
論文 参考訳(メタデータ) (2021-07-19T11:43:24Z) - Shuffle Private Stochastic Convex Optimization [20.379311972125034]
シャッフルプライバシでは、各ユーザがランダム化されたメッセージの集合を信頼できるシャッフルに送信する。
シャッフルラーはランダムにこれらのメッセージをパーミュートし、その結果、シャッフルされたメッセージの集合は、差分プライバシーを満たさなければならない。
凸最適化のための対話型シャッフルプロトコルを提案する。
論文 参考訳(メタデータ) (2021-06-17T20:44:00Z) - On the Renyi Differential Privacy of the Shuffle Model [25.052851351062845]
シャッフルモデルでは、各$n$クライアントはローカル差分プライベート(LDP)メカニズムを使用してレスポンスをランダム化し、信頼できないサーバは各クライアントに関連付けることなくクライアントレスポンスのランダムな置換(シャッフル)のみを受け取ります。
本稿では,シャッフルドプライバシモデルにおける一般離散局所ランダム化機構に対する最初の非自明な保証について述べる。
論文 参考訳(メタデータ) (2021-05-11T16:34:09Z) - Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
分割雑音を伴う非加法的決定論的平滑化法(dssn)を提案する。
一様加法平滑化とは対照的に、ssn認証は無作為なノイズコンポーネントを独立に必要としない。
これは、規範ベースの敵対的脅威モデルに対して決定論的「ランダム化平滑化」を提供する最初の仕事である。
論文 参考訳(メタデータ) (2021-03-17T21:49:53Z) - The Limits of Pan Privacy and Shuffle Privacy for Learning and
Estimation [3.2942333712377083]
種々の高次元学習および推定問題に対して,シャッフルモデルとパンプライベートモデルでは,中央モデルと比較してサンプルの複雑さが指数関数的に高くなることを示す。
我々の研究は、パンプライベートモデルと一般的なマルチメッセージシャッフルモデルの両方に対して、これらの問題に対する最初の非自明な下界を与える。
論文 参考訳(メタデータ) (2020-09-17T01:15:55Z) - Connecting Robust Shuffle Privacy and Pan-Privacy [11.367579037903734]
差分プライバシのEmphshuffleモデルでは、データ保持ユーザはセキュアなシャフラーにランダム化されたメッセージを送信し、シャフラーはメッセージを置換する。
Emphpan-privateモデルでは、アルゴリズムがストリームデータに関して異なるプライベートな内部状態を維持しながら、データのストリームを処理する。
弊社の結果は、プライバシー保証が悪意のあるユーザの影響を大きく受けていないプライベートプロトコルを不当にシャッフルすることに焦点を当てている。
論文 参考訳(メタデータ) (2020-04-20T17:58:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。