論文の概要: Communication Optimal Unbalanced Private Set Union
- arxiv url: http://arxiv.org/abs/2402.16393v1
- Date: Mon, 26 Feb 2024 08:36:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 07:18:43.967384
- Title: Communication Optimal Unbalanced Private Set Union
- Title(参考訳): コミュニケーションの最適不均衡なプライベート・セット・ユニオン
- Authors: Jean-Guillaume Dumas, Alexis Galan, Bruno Grenet, Aude Maignan, Daniel S. Roche,
- Abstract要約: 2つの党はそれぞれプライベートな要素の集まりを持ち、その1つに2つの組の合同を学びたいと願っている。
我々のプロトコルは、受信機の設定サイズが送信機の設定サイズよりも大きい不均衡ケースをターゲットにしています。
漸近的に、送信者の(より小さい)設定サイズで通信コストを線形にし、各設定サイズでほぼ直線的な送信者と受信者の計算コストを計算します。
- 参考スコア(独自算出の注目度): 3.174848963159788
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the private set union (PSU) problem, where two parties each hold a private set of elements, and they want one of the parties (the receiver) to learn the union of the two sets and nothing else. Our protocols are targeted for the unbalanced case where the receiver's set size is larger than the sender's set size, with the goal of minimizing the costs for the sender both in terms of communication volume and local computation time. This setting is motivated by applications where the receiver has significantly more data (input set size) and computational resources than the sender which might be realized on a small, low-power device. Asymptotically, we achieve communication cost linear in the sender's (smaller) set size, and computation costs for sender and receiver which are nearly-linear in their respective set sizes. To our knowledge, ours is the first algorithm to achieve nearly-linear communication and computation for PSU in this unbalanced setting. Our protocols utilize fully homomorphic encryption (FHE) and, optionally, linearly homomorphic encryption (LHE) to perform the necessary computations while preserving privacy. The underlying computations are based on univariate polynomial arithmetic realized within homomorphic encryption, namely fast multiplication, modular reduction, and multi-point evaluation. These asymptotically fast HE polynomial arithmetic algorithms may be of independent interest.
- Abstract(参考訳): プライベート・セット・ユニオン(PSU)問題を考えると、2つのパーティがそれぞれプライベート・セットの要素を持ち、2つのセットのユニオンを学ぶために1つのパーティ(受信機)を欲しがる。
本プロトコルは,受信者の設定サイズが送信者の設定サイズよりも大きい不均衡ケースを対象としており,通信量とローカル計算時間の両方において送信者のコストを最小限に抑えることを目的としている。
この設定は、受信機が小型の低消費電力デバイスで実現される可能性のある送信機よりもはるかに多くのデータ(入力セットサイズ)と計算資源を持つアプリケーションによって動機付けられている。
漸近的に、送信側(より小さい)設定サイズで通信コストを線形にし、各設定サイズでほぼ直線的な送信側と受信側の計算コストを計算します。
我々の知る限り、この不均衡な環境でPSUのほぼ直線的な通信と計算を実現する最初のアルゴリズムである。
本プロトコルは, 完全同型暗号(FHE)と任意に線形同型暗号(LHE)を用いて, プライバシを保ちながら必要な計算を行う。
基礎となる計算は、ホモモルフィック暗号の中で実現された単変量多項式演算、すなわち高速乗算、モジュラーリダクション、マルチポイント評価に基づいている。
これらの漸近的に高速なHE多項式算術アルゴリズムは独立した興味を持つかもしれない。
関連論文リスト
- Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-08-31T12:22:40Z) - Over-the-Air Federated Averaging with Limited Power and Privacy Budgets [49.04036552090802]
本稿では,電力予算が制限されたプライベート・オーバ・ザ・エア・フェデレーション(DP-OTA-FedAvg)システムについて検討する。
我々は,DP-OTA-FedAvg係数のギャップを最小化し,プライバシー機能を最小化するために解析的問題を改善することを目的としている。
論文 参考訳(メタデータ) (2023-05-05T13:56:40Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
複数の基地局とセル間干渉を持つ無線システムにおける連合学習モデルを考える。
本稿では,学習過程の収束挙動を,その最適性ギャップの上限を導出することによって示す。
提案するスケジューラは,ランダムなスケジューラと比較して予測平均精度を向上する。
論文 参考訳(メタデータ) (2022-08-25T03:37:11Z) - Task-Oriented Sensing, Computation, and Communication Integration for
Multi-Device Edge AI [108.08079323459822]
本稿では,AIモデルの分割推論と統合センシング通信(ISAC)を併用した,新しいマルチインテリジェントエッジ人工レイテンシ(AI)システムについて検討する。
推定精度は近似的だが抽出可能な計量、すなわち判別利得を用いて測定する。
論文 参考訳(メタデータ) (2022-07-03T06:57:07Z) - Federated Learning for Energy-limited Wireless Networks: A Partial Model
Aggregation Approach [79.59560136273917]
デバイス間の限られた通信資源、帯域幅とエネルギー、およびデータ不均一性は、連邦学習(FL)の主要なボトルネックである
まず、部分モデルアグリゲーション(PMA)を用いた新しいFLフレームワークを考案する。
提案されたPMA-FLは、2つの典型的な異種データセットにおいて2.72%と11.6%の精度を改善する。
論文 参考訳(メタデータ) (2022-04-20T19:09:52Z) - Settling the Communication Complexity for Distributed Offline
Reinforcement Learning [10.315054389907031]
オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。
各マシンが送信できる情報の総数(ビット数)には予算の制約がある。
文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
論文 参考訳(メタデータ) (2022-02-10T06:27:07Z) - HD-cos Networks: Efficient Neural Architectures for Secure Multi-Party
Computation [26.67099154998755]
マルチパーティ計算(MPC、Multi-party calculation)は、暗号化の分野の一つで、複数の非解決パーティが関数を安全に計算するためのプロトコルを実行する。
MPC設定下でニューラルネットワークのトレーニングと推論について検討する。
どちらの手法も、MPC設定下での強力な理論的モチベーションと効率的な計算を享受できることを示す。
論文 参考訳(メタデータ) (2021-10-28T21:15:11Z) - Optimal Communication-Computation Trade-Off in Heterogeneous Gradient
Coding [23.783023315297875]
グラデーションのサイズによって正規化された最適な通信コストは$(r-s-2a)-1$に等しく、mathbbN$の$rはデータパーティションが複製される最小数である。
また、近似計算からいくつかのアイデアを借用し、通信コストに課される制約を満たすためにデータ配置の繰り返しが必要とされるものよりも小さい場合の近似勾配符号化スキームを提案する。
論文 参考訳(メタデータ) (2021-03-02T09:25:30Z) - Berrut Approximated Coded Computing: Straggler Resistance Beyond
Polynomial Computing [34.69732430310801]
本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。
BACCは計算複雑性が低い数値的に安定であることが証明されている。
特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
論文 参考訳(メタデータ) (2020-09-17T14:23:38Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。