論文の概要: Communication Optimal Unbalanced Private Set Union

• arxiv url: http://arxiv.org/abs/2402.16393v2
• Date: Tue, 9 Jul 2024 09:34:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 23:51:16.465788
• 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多項式算術アルゴリズムは独立した興味を持つかもしれない。

関連論文リスト

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions [5.030459935922802]
  マルチパーティ・プライベート・セット・ユニオン(MPSU)プロトコルにより、$m$$(m > 2)$パーティがそれぞれセットを保持し、集合のユニオンをまとめて計算することができる。 本稿では,標準半高次モデルにおいて,暗黙の転送と対称鍵技術に基づく最初のMPSUプロトコルを提案する。 当社のプロトコルでは,それぞれ220ドルのアイテムをセットした3つのパーティに対して,オンラインフェーズで4.4ドル秒しか必要としない。
  論文  参考訳（メタデータ） (2024-06-11T07:10:45Z)
• Joint Constellation Shaping Using Gradient Descent Approach for MU-MIMO Broadcast Channel [2.868688147297278]
  完全チャネル知識を持つ放送チャンネルの連星座を最適化するための学習に基づくアプローチを提案する。 提案手法の目的は、送信機と受信機間の最小の相互情報を最大化することである。 本手法により得られたレートは,線形プリコーダで得られたレートと比較される。
  論文  参考訳（メタデータ） (2024-06-03T08:20:06Z)
• Algorithmic Persuasion Through Simulation [51.23082754429737]
  本研究では,受取人に製品購入などの二元的行動を取るよう説得するベイズ説得ゲームについて検討する。 送信者は、製品の品質が高いか低いかなどの世界の(バイナリ)状態について通知されるが、受信者の信念やユーティリティに関する情報は限られている。 顧客の調査やユーザスタディ、最近のAIの進歩によって動機づけられた私たちは、受信者の振る舞いをシミュレートする託宣をクエリすることで、送信側が受信者についてより深く学ぶことを可能にする。
  論文  参考訳（メタデータ） (2023-11-29T23:01:33Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。 本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
  論文  参考訳（メタデータ） (2023-09-23T08:45:27Z)
• Settling the Communication Complexity for Distributed Offline Reinforcement Learning [10.315054389907031]
  オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。 各マシンが送信できる情報の総数(ビット数)には予算の制約がある。 文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
  論文  参考訳（メタデータ） (2022-02-10T06:27:07Z)
• Multi-Channel End-to-End Neural Diarization with Distributed Microphones [53.99406868339701]
  EENDのTransformerエンコーダを,マルチチャネル入力を処理する2種類のエンコーダに置き換える。 また,単一チャンネル記録のみを用いたモデル適応手法を提案する。
  論文  参考訳（メタデータ） (2021-10-10T03:24:03Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Multi-Receiver Online Bayesian Persuasion [51.94795123103707]
  本研究では,未知の逆選択型の受信者に対して,送信者が繰り返し対面するオンライン学習フレームワークについて検討する。 オフラインモデルの慣習として、外部性やバイナリアクションのないケースに重点を置いています。 本稿では,損失関数を有限個に制限したオンライン学習問題に対処する一般的なオンライン降下スキームを提案する。
  論文  参考訳（メタデータ） (2021-06-11T16:05:31Z)
• Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding [23.783023315297875]
  グラデーションのサイズによって正規化された最適な通信コストは$(r-s-2a)-1$に等しく、mathbbN$の$rはデータパーティションが複製される最小数である。 また、近似計算からいくつかのアイデアを借用し、通信コストに課される制約を満たすためにデータ配置の繰り返しが必要とされるものよりも小さい場合の近似勾配符号化スキームを提案する。
  論文  参考訳（メタデータ） (2021-03-02T09:25:30Z)
• Data capacity scaling of a distributed Rydberg atomic receiver array [0.0]
  空間分布プローブ光を用いた単一入出力(SIMO)構成で原子-光受信器のアレイを実装した。 分散受信機構成のデータ容量は、$N$からなる配列に対して$textlog (1 + NtimestextSNR)$としてスケールされる。
  論文  参考訳（メタデータ） (2021-02-10T06:39:52Z)

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

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