論文の概要: Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions
- arxiv url: http://arxiv.org/abs/2410.17000v1
- Date: Tue, 22 Oct 2024 13:22:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-23 14:26:50.658803
- Title: Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions
- Title（参考訳）: Yaoの億万長者を超えて - 非多項式関数のセキュアなマルチパーティ計算
- Authors: Seyed Reza Hoseini Najarkolaei, Mohammad Mahdi Mojahedian, Mohammad Reza Aref,
- Abstract要約: 我々はシャミール秘密共有に基づく無条件でセキュアな$N$-party比較スキームを提案する。
各パーティは、プライベート番号を保持し、入力を公表することなく、$N$利用可能なプライベート番号の中で最大の番号を確認することを目指している。
- 参考スコア（独自算出の注目度）: 5.625796693054093
- License:
- Abstract: In this paper, we present an unconditionally secure $N$-party comparison scheme based on Shamir secret sharing, utilizing the binary representation of private inputs to determine the $\max$ without disclosing any private inputs or intermediate results. Specifically, each party holds a private number and aims to ascertain the greatest number among the $N$ available private numbers without revealing its input, assuming that there are at most $T < \frac{N}{2}$ honest-but-curious parties. The proposed scheme demonstrates a lower computational complexity compared to existing schemes that can only compare two secret numbers at a time. To the best of our knowledge, our scheme is the only information-theoretically secure method for comparing $N$ private numbers without revealing either the private inputs or any intermediate results. We demonstrate that by modifying the proposed scheme, we can compute other well-known non-polynomial functions of the inputs, including the minimum, median, and rank. Additionally, in the proposed scheme, before the final reveal phase, each party possesses a share of the result, enabling the nodes to compute any polynomial function of the comparison result. We also explore various applications of the proposed comparison scheme, including federated learning.
- Abstract（参考訳）: 本稿では,Shamir秘密共有に基づく無条件でセキュアな$N$-party比較スキームを提案し,プライベート入力のバイナリ表現を利用して,プライベート入力や中間結果の開示なしに$\max$を決定する。
具体的には、各パーティはプライベート番号を保持し、少なくとも$T < \frac{N}{2}$ honest-but-curious party が存在すると仮定して、入力を明らかにすることなく、$N$利用可能なプライベートナンバーのうち最大の番号を確認することを目指している。
提案手法は,2つの秘密数を同時に比較できる既存のスキームと比較して計算複雑性が低いことを示す。
我々の知る限り、我々のスキームは、プライベートな入力と中間的な結果の両方を明らかにすることなく、$N$プライベートな数値を比較する唯一の情報理論的に安全な方法である。
提案手法を改良することにより、最小、中央値、ランクを含む入力の他のよく知られた非ポリノミカル関数を計算できることを実証する。
さらに、提案方式では、最終公開フェーズの前に各ノードが結果の共有を保持し、ノードが比較結果の多項式関数を計算できるようにする。
また、フェデレート学習を含む、提案した比較スキームの様々な応用についても検討する。
関連論文リスト
- Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。
これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。
これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。
論文 参考訳（メタデータ） (2024-10-22T18:33:02Z) - Differential Privacy on Trust Graphs [54.55190841518906]
差分プライバシー(DP)は、各当事者がそのデータで他の当事者の(既知の)サブセットのみを信頼するマルチパーティ環境で研究する。
我々は、DPのローカルモデルよりもはるかに優れたプライバシーとユーティリティのトレードオフを持つ集約のためのDPアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-10-15T20:31:04Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
非プライベートなデータ依存前処理アルゴリズムによって生じる追加のプライバシーコストを評価するための一般的なフレームワークを提案する。
当社のフレームワークは,2つの新しい技術的概念を活用することにより,全体的なプライバシー保証の上限を確立する。
論文 参考訳（メタデータ） (2024-03-19T17:54:49Z) - A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
閾値秘密共有方式により、ディーラーは、秘密が一定量の株式から正しく回収されたことをすべての参加者に分配することができる。
我々は、リング上の$ell$-bitシークレットのための、進化する$k$-thresholdシークレット共有スキームを、正確性と完全なセキュリティで新たに構築することを提案する。
論文 参考訳（メタデータ） (2024-02-02T05:04:01Z) - Quantum Private Membership Aggregation [35.16231062731263]
我々は、絡み合った量子状態を用いて、N$パーティのプライベート・セット・メンバシップ・アグリゲーションの問題を考察する。
本稿では,従来の情報を識別可能な量子状態にマッピングする符号化アルゴリズムと,マッピングされた状態の識別性を利用する復号アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-29T18:32:19Z) - Differentially Private Secure Multiplication: Hiding Information in the
Rubble of Noise [7.767656876470667]
プライベート分散マルチパーティ乗算の問題点を考察する。
Shamirの秘密共有コーディング戦略が、分散計算における完全な情報理論プライバシを実現することは、十分に確立されている。
論文 参考訳（メタデータ） (2023-09-28T02:13:13Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。
ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。
これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
論文 参考訳（メタデータ） (2022-06-06T13:49:37Z) - Optimal Accounting of Differential Privacy via Characteristic Function [25.78065563380023]
本稿では,プライバシ・プロフィール,プライバシ・プロファイル,$f$-DP,PLDフォーマリズムなどの最近の進歩を,ある最悪のケースのプライバシ・ロスランダム変数の特徴関数(phi$-function)を介して統一することを提案する。
我々のアプローチは、Renyi DPのような自然適応的な構成を可能にし、PDDのような厳密なプライバシ会計を提供し、プライバシープロファイルや$f$-DPに変換できることが示されています。
論文 参考訳（メタデータ） (2021-06-16T06:13:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。