論文の概要: 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つの計算タスクを導入する。

関連論文リスト

• Differential Privacy on Trust Graphs [54.55190841518906]
  差分プライバシー(DP)は、各当事者がそのデータで他の当事者の(既知の)サブセットのみを信頼するマルチパーティ環境で研究する。 我々は、DPのローカルモデルよりもはるかに優れたプライバシーとユーティリティのトレードオフを持つ集約のためのDPアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-10-15T20:31:04Z)
• Efficient Fault-Tolerant Quantum Protocol for Differential Privacy in the Shuffle Model [2.0794380287086214]
  本稿では,ランダムシャッフルを暗黙的に実装し,シャッフルモデルにおける差分プライバシーを実現する量子プロトコルを提案する。 シャッフルモデルは、データコントリビュータから得られる結果を増幅する。 例えば、mix-networksによるシャッフルの実装や、信頼できるサードパーティによるシャッフルなどです。 本稿では、量子状態の絡み合いを利用したプロトコルの量子バージョンを提案し、これらの余分な要求なしにシャッフルを実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-09-06T04:53:19Z)
• Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling [21.031062710893867]
  本稿では,PIC(Private Individual Computation)と呼ばれる新しいパラダイムを紹介する。 PICは、プライバシを保持しながらパーソナライズされたアウトプットを可能にし、シャッフルによってプライバシーを増幅する。 実用性を高めるためにPICモデルのために設計された最適確率化器Minkowski Responseを提案する。
  論文  参考訳（メタデータ） (2024-06-26T07:53:48Z)
• Towards a Generalist and Blind RGB-X Tracker [91.36268768952755]
  我々は、推論時間中に任意のモダリティ X を無視できる単一のモデルトラッカーを開発する。 トレーニングプロセスは非常にシンプルで,複数ラベルの分類損失をルーティング関数に統合する。 我々のジェネラリストとブラインドトラッカーは、確立されたモーダル固有モデルと比較して、競争性能を達成することができる。
  論文  参考訳（メタデータ） (2024-05-28T03:00:58Z)
• Differentially Private Aggregation via Imperfect Shuffling [64.19885806149958]
  本稿では,メッセージがほぼ均一にシャッフルされる不完全なシャッフル差分プライバシモデルを導入し,キュレーターによるプライベートアグリゲーションの検証を行った。 驚くべきことに、不完全なシャッフルモデルには追加のエラーオーバーヘッドは必要ない。
  論文  参考訳（メタデータ） (2023-08-28T17:34:52Z)
• 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)
• Tight Differential Privacy Guarantees for the Shuffle Model with $k$-Randomized Response [6.260747047974035]
  ほとんどの差分プライベート(DP)アルゴリズムは、サードパーティがデータセットやユーザがローカルにデータを摂動するローカルモデル上で作成したクエリにノイズを挿入することを前提としている。 最近提案されたシャッフルモデルは、中央パラダイムと局所パラダイムの中間フレームワークである。 合成データと実データの両方を用いて、シャッフルモデルのプライバシーユーティリティトレードオフと、民営化された中央データの比較実験を行う。
  論文  参考訳（メタデータ） (2022-05-18T10:44:28Z)
• Shuffle Private Stochastic Convex Optimization [20.379311972125034]
  シャッフルプライバシでは、各ユーザがランダム化されたメッセージの集合を信頼できるシャッフルに送信する。 シャッフルラーはランダムにこれらのメッセージをパーミュートし、その結果、シャッフルされたメッセージの集合は、差分プライバシーを満たさなければならない。 凸最適化のための対話型シャッフルプロトコルを提案する。
  論文  参考訳（メタデータ） (2021-06-17T20:44:00Z)

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

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