論文の概要: Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions
- arxiv url: http://arxiv.org/abs/2406.07011v2
- Date: Mon, 17 Jun 2024 07:36:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 01:50:51.829448
- Title: Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions
- Title（参考訳）: 自由を破る:非協力的仮定なしで効率的な多人数のプライベート・セット・ユニオン
- Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai,
- Abstract要約: マルチパーティ・プライベート・セット・ユニオン(MPSU)プロトコルにより、$m$$(m > 2)$パーティがそれぞれセットを保持し、集合のユニオンをまとめて計算することができる。
本稿では,標準半高次モデルにおいて,暗黙の転送と対称鍵技術に基づく最初のMPSUプロトコルを提案する。
当社のプロトコルでは,それぞれ220ドルのアイテムをセットした3つのパーティに対して,オンラインフェーズで3.6ドル秒しか必要としない。
- 参考スコア（独自算出の注目度）: 5.030459935922802
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of MPSU protocols: The first builds on public-key techniques. All existing works in this category involve a super-linear number of public-key operations, resulting in poor practical efficiency. The second builds on oblivious transfer and symmetric-key techniques. The only existing work in this category is proposed by Liu and Gao (ASIACRYPT 2023), which features the best concrete performance among all existing protocols, despite its super-linear computation and communication. Unfortunately, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice. Therefore, the problem of constructing a practical MPSU protocol based on oblivious transfer and symmetric-key techniques in standard semi-honest model remains open. Furthermore, there is no MPSU protocol achieving both linear computation and linear communication complexity, which leaves another unresolved problem. In this work, we resolve these two open problems. We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $4.9-9.3 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $3.6$ seconds in online phase for 3 parties with sets of $2^{20}$ items each. We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao.
- Abstract（参考訳）: マルチパーティ・プライベート・セット・ユニオン(MPSU)プロトコルでは、$m$$(m > 2)$パーティがそれぞれセットを持っていて、他のパーティに追加情報を公開することなく、セットのユニオンをまとめて計算することができる。
MPSUプロトコルには2つの主要なカテゴリがある。
このカテゴリの既存のすべての作業は、超直線的な公開鍵操作を含み、結果として実用的効率が低下する。
2つ目は、暗黙の転送と対称キー技術に基づくものである。
このカテゴリにおける唯一の既存の研究は、Liu and Gao (ASIACRYPT 2023) によって提案されている。
残念なことに、これは通常の半正直なセキュリティを達成しない。
したがって、標準的な半真性モデルにおいて、暗黙の転送と対称鍵技術に基づく実用的なMPSUプロトコルを構築するという問題は未解決のままである。
さらに,線形計算と線形通信の複雑さを両立させるMPSUプロトコルは存在しない。
本稿では、これらの2つの未解決問題を解決する。
本稿では,標準半高次モデルにおいて,暗黙の転送と対称鍵技術に基づく最初のMPSUプロトコルを提案する。
このプロトコルは、LAN設定でLiuやGaoよりも高速な4.9-9.3 \timesである。
具体的には、当社のプロトコルはオンラインフェーズでわずか3.6ドル秒で、それぞれ2〜20ドルのアイテムがセットされている。
公開鍵演算に基づく線形計算と線形通信の複雑さを両立させる最初のMPSUプロトコルを提案する。
このプロトコルは通信コストが低く、Liu や Gao と比較すると、通信コストが3.0-36.5 倍になる。
関連論文リスト
- A Multiparty Quantum Private Equality Comparison scheme relying on $\ket{ GHZ_{ 3 } }$ states [0.0]
本稿では,マルチパーティ量子プライベート比較を実現する革新的な絡み合いベースのプロトコルを提案する。
これは、億万長者の数に関係なく、プロトコルがGHZ3三重項のみを使用するためである。
このプロトコルは情報理論上は安全であり、外部の関係者が占いや内部のプレイヤーがお互いの秘密の番号を知るのを妨げている。
論文 参考訳（メタデータ） (2024-07-07T14:21:22Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - A General Framework for Sequential Decision-Making under Adaptivity
Constraints [112.79808969568253]
適応性制約(まれなポリシースイッチ)とバッチ学習(バッチ学習)という2つの制約の下で、一般的なシーケンシャルな意思決定について検討する。
稀なポリシースイッチの制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを達成するアルゴリズムを提供する。
バッチ学習制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを提供するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-06-26T07:20:25Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Communication complexity of entanglement assisted multi-party
computation [11.820804392113294]
プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。
量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。
これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
論文 参考訳（メタデータ） (2023-05-08T03:10:08Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine Learning [5.774912335678817]
本研究は,非線形関数評価の効率を向上するセキュアな3要素プロトコルであるBicoptorのファミリーを導入する。
我々の3PC符号決定プロトコルは、通信ラウンドを2回しか必要とせず、前処理を一切含まない。
パブリッククラウド上での3次元LANネットワーク上でのBicoptorの評価を行い,370,000 DRELU/ReLUまたは41,000 Maxpoolの動作を毎秒達成した。
論文 参考訳（メタデータ） (2022-10-05T02:33:53Z) - Non-local computation of quantum circuits with small light cones [0.0]
ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。
我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
論文 参考訳（メタデータ） (2022-03-18T18:00:06Z) - Communication Complexity of Private Simultaneous Quantum Messages
Protocols [0.609170287691728]
本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。
プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。
また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
論文 参考訳（メタデータ） (2021-05-15T03:08:01Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。