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

• arxiv url: http://arxiv.org/abs/2402.16393v3
• Date: Thu, 03 Oct 2024 08:12:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-04 23:26:38.575546
• Title: Optimal Communication Unbalanced Private Set Union
• Title（参考訳）: 最適な通信不均衡なプライベート・セット・ユニオン
• Authors: Jean-Guillaume Dumas, Alexis Galan, Bruno Grenet, Aude Maignan, Daniel S. Roche,
• Abstract要約: 我々は、アンバランス・プライベート・セット・ユニオン問題のための新しい2つのプロトコルを提案する。 我々のプロトコルは、Sender の計算コストと通信容量が Sender の集合のサイズにのみ線形である最初のものである。 HElibを用いた予備的な結果は、例えば、1000個の要素を持つSenderが、2秒未満の計算時間と10MB未満の通信量を使用して、最初のプロトコルを完了できることを示している。
• 参考スコア（独自算出の注目度）: 3.174848963159788
• License:
• Abstract: We present new two-party protocols for the Unbalanced Private Set Union (UPSU) problem.Here, the Sender holds a set of data points, and the Receiver holds another (possibly much larger) set, and they would like for the Receiver to learn the union of the two sets and nothing else. Furthermore, the Sender's computational cost, along with the communication complexity, should be smaller when the Sender has a smaller set.While the UPSU problem has numerous applications and has seen considerable recent attention in the literature, our protocols are the first where the Sender's computational cost and communication volume are linear in the size of the Sender's set only, and do not depend on the size of the Receiver's set.Our constructions combine linearly homomorphic encryption (LHE) withfully homomorphic encryption (FHE). The first construction uses multi-point polynomial evaluation (MEv) on FHE, and achieves optimal linear cost for the Sender, but has higher quadratic computational cost for the Receiver. In the second construction we explore another trade-off: the Receiver computes fast polynomial Euclidean remainder in FHE while the Sender computes a fast MEv, in LHE only. This reduces the Receiver's cost to quasi-linear, with a modest increase in the computational cost for the Sender.Preliminary experimental results using HElib indicate that, for example, a Sender holding 1000 elements can complete our first protocol using less than 2s of computation time and less than 10MB of communication volume, independently of the Receiver's set size.
• Abstract（参考訳）: 我々は、アンバランス・プライベート・セット・ユニオン(UPSU)問題に対する新たな2つのプロトコルを提案し、Senderは一連のデータポイントを持ち、受信側は別の(おそらくはるかに大きい)データセットを持ち、受信側は2つのセットのユニオンを学習し、それ以上のことは望まない。 さらに、Senderの計算コストは、通信の複雑さとともに小さくすべきであり、UPSU問題には多くの応用があり、文献で注目されているが、我々のプロトコルは、Senderの計算コストと通信量がSenderの集合のサイズだけに線形であり、受信者の集合のサイズに依存しない最初のものである。 最初の構成では、FHE上の多点多項式評価(MEv)を用い、Senderの最適線形コストを実現するが、受信側では2次計算コストが高い。 受信者は FHE の高速多項式ユークリッド剰余を計算し、Sender は LHE の高速 MEv を演算する。 HElibを用いた実験結果によると、例えば、1000個の要素を保持するSenderは、2秒未満の計算時間と10MB未満の通信量で、受信者の設定サイズとは無関係に、最初のプロトコルを完了させることができる。

関連論文リスト

• 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)

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

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