論文の概要: Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity

• arxiv url: http://arxiv.org/abs/2501.11235v1
• Date: Mon, 20 Jan 2025 02:46:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:19:01.575099
• Title: Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity
• Title（参考訳）: 複雑度が低い任意三値完全同型暗号
• Authors: Yijia Chang, Songze Li,
• Abstract要約: 我々はtextitapproximate secret sharing (ApproxSS) と呼ばれる新しいプリミティブを開発する。 任意閾値(ATh)-ApproxSS特性上におけるAThFHEの正当性と安全性を実証する。 ATASSESは3.83タイム= -- 15.4タイム=ベースライン以上のスピードアップを実現している。
• 参考スコア（独自算出の注目度）: 8.228450733641122
• License:
• Abstract: Threshold fully homomorphic encryption (ThFHE) enables multiple parties to compute functions over their sensitive data without leaking data privacy. Most of existing ThFHE schemes are restricted to full threshold and require the participation of \textit{all} parties to output computing results. Compared with these full-threshold schemes, arbitrary threshold (ATh)-FHE schemes are robust to non-participants and can be a promising solution to many real-world applications. However, existing AThFHE schemes are either inefficient to be applied with a large number of parties $N$ and a large data size $K$, or insufficient to tolerate all types of non-participants. In this paper, we propose an AThFHE scheme to handle all types of non-participants with lower complexity over existing schemes. At the core of our scheme is the reduction from AThFHE construction to the design of a new primitive called \textit{approximate secret sharing} (ApproxSS). Particularly, we formulate ApproxSS and prove the correctness and security of AThFHE on top of arbitrary-threshold (ATh)-ApproxSS's properties. Such a reduction reveals that existing AThFHE schemes implicitly design ATh-ApproxSS following a similar idea called ``noisy share''. Nonetheless, their ATh-ApproxSS design has high complexity and become the performance bottleneck. By developing ATASSES, an ATh-ApproxSS scheme based on a novel ``encrypted share'' idea, we reduce the computation (resp. communication) complexity from $\mathcal{O}(N^2K)$ to $\mathcal{O}(N^2+K)$ (resp. from $\mathcal{O}(NK)$ to $\mathcal{O}(N+K)$). We not only theoretically prove the (approximate) correctness and security of ATASSES, but also empirically evaluate its efficiency against existing baselines. Particularly, when applying to a system with one thousand parties, ATASSES achieves a speedup of $3.83\times$ -- $15.4\times$ over baselines.
• Abstract（参考訳）: Threshold fully homomorphic encryption (ThFHE)により、複数のパーティがデータのプライバシーを漏洩することなく、機密データ上の関数を計算できる。 既存のThFHEスキームのほとんどは完全なしきい値に制限されており、計算結果を出力するためにはtextit{all}パーティの参加が必要である。 これらのフルスレッショルドスキームと比較して、任意のしきい値(ATh)-FHEスキームは非参加者に対して堅牢であり、多くの実世界のアプリケーションに対して有望な解決策となる。 しかし、既存のAThFHEスキームは、多数のパーティ$N$と大きなデータサイズ$K$を適用できないか、あるいは、すべての種類の非参加者を許容できないかのいずれかである。 本稿では,既存方式よりも複雑度が低い全種類の非参加者を扱うためのAThFHE方式を提案する。 私たちの計画の核心は、AThFHE 構造から、新しいプリミティブである \textit{approximate secret sharing} (ApproxSS) の設計への還元である。 特に、ApproxSSを定式化し、任意のスレッショルド(ATh)-ApproxSSの特性上におけるAThFHEの正当性と安全性を証明する。 このような削減は、既存のAThFHEスキームが、'`noisy share''と呼ばれる同様のアイデアに従って、ATh-ApproxSSを暗黙的に設計していることを明らかにする。 それでも、ATh-ApproxSSの設計は複雑さが高く、パフォーマンスのボトルネックとなっている。 新たな‘暗号化共有’のアイデアに基づくATh-ApproxSSスキームであるATASSESを開発することにより,計算複雑性を$\mathcal{O}(N^2K)$から$\mathcal{O}(N^2+K)$(resp)$に削減する。 $\mathcal{O}(NK)$から$\mathcal{O}(N+K)$へ。 我々は理論的にATASSESの正しさと安全性を証明しただけでなく、既存のベースラインに対してその効率を実証的に評価した。 特に、1000のパーティを持つシステムに適用する場合、ATASSESは3.83\times$ --15.4\times$ over baselinesというスピードアップを達成する。

関連論文リスト

• Simultaneously Solving FBSDEs with Neural Operators of Logarithmic Depth, Constant Width, and Sub-Linear Rank [8.517406772939292]
  フォワード・バックワード微分方程式(FBSDEs)は、最適制御、ゲーム理論、経済学、数学ファイナンスの中心である。 Small'' NOs は FBSDEs の構造された族に対する解演算子を均一に近似できることを示す。 また、同様の深さ、幅、ランクの畳み込みNOは、解作用素を楕円型PDEの広いクラスに近似することができることを示す。
  論文  参考訳（メタデータ） (2024-10-18T18:01:40Z)
• CSPs with Few Alien Constraints [12.330326247154968]
  CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。 我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
  論文  参考訳（メタデータ） (2024-08-23T08:34:13Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
  我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。 我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。 我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
  論文  参考訳（メタデータ） (2023-07-14T01:32:16Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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