論文の概要: Optimized Homomorphic Vector Permutation From New Decomposition Techniques

• arxiv url: http://arxiv.org/abs/2410.21840v2
• Date: Sat, 02 Nov 2024 21:19:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:45:49.945955
• Title: Optimized Homomorphic Vector Permutation From New Decomposition Techniques
• Title（参考訳）: 新しい分解技術による均質ベクトルの最適置換
• Authors: Xirong Ma, Junling Fang, Dung Hoang Duong, Yali Jiang, Chunpeng Ge,
• Abstract要約: 同型置換は、単語単位の同型暗号に基づくプライバシー保護計算の基礎となる。 本稿では、置換の任意の分解の理想的な性能を定義し、この境界を達成するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 1.4447019135112429
• License:
• Abstract: Homomorphic permutations are fundamental to privacy-preserving computations based on word-wise homomorphic encryptions, which can be accelerated through permutation decomposition. This paper defines an ideal performance of any decomposition on permutations and designs algorithms to achieve this bound. We start by proposing an algorithm searching depth-1 ideal decomposition solutions for permutations. This allows us to ascertain the full-depth ideal decomposability of two types of permutations used in specific homomorphic matrix transposition (SIGSAC 18) and multiplication (CCSW 22), enabling these algorithms to achieve asymptotic improvement in speed and rotation key reduction. We further devise a new strategy for homomorphically computing arbitrary permutations, aiming to approximate the performance limits of ideal decomposition, as permutations with weak structures are unlikely to be ideally factorized. Our design deviates from the conventional scope of permutation decomposition and surpasses state-of-the-art techniques (EUROCRYPT 12, CRYPTO 14) with a speed-up of up to $\times2.27$ under the minimum requirement of rotation keys.
• Abstract（参考訳）: 同型置換は、ワードワイドの同型暗号に基づくプライバシー保護計算の基本であり、置換分解によって高速化される。 本稿では、置換の任意の分解の理想的な性能を定義し、この境界を達成するアルゴリズムを設計する。 まず、置換に対するdeep-1理想的な分解解を求めるアルゴリズムを提案する。 これにより、特定のホモモルフィック行列変換(SIGSAC 18)と乗算(CCSW 22)で使用される2種類の置換の完全なデコンポーザビリティを確認でき、これらのアルゴリズムは速度と回転鍵の減少の漸近的な改善を達成できる。 さらに、弱構造をもつ置換が理想的に分解される可能性が低いため、理想分解の性能限界を近似することを目的として、任意の置換を同型に計算する新しい戦略を考案する。 我々の設計は、従来の置換分解の範囲から逸脱し、ローテーションキーの最低限の条件で最大$\times2.27$の高速化で最先端技術(EUROCRYPT 12, CRYPTO 14)を超える。

関連論文リスト

• Strategies for optimizing double-bracket quantum algorithms [0.050257374758179374]
  ダブルブラケット進化の選択を最適化するための戦略を提案する。 また,CNOTやシングルキュービット回転ゲートに直接コンパイル可能な対角展開パラメトリゼーションも提案する。
  論文  参考訳（メタデータ） (2024-08-14T10:07:54Z)
• SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization [24.55623897747344]
  ニューラルネットワークプルーニングは、大規模で拡張性があり、解釈可能で、一般化可能なモデルを構築するための重要な技術である。 群スパース最適化の非正規化として,既存の微分可能なプルーニング手法がいくつあるかを示す。 我々は、ImageNetとCriteoデータセット上の大規模ニューラルネットワークブロックワイドプルーニングタスクの最先端技術であるSequentialAttention++を提案する。
  論文  参考訳（メタデータ） (2024-02-27T21:42:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Novel and Optimal Spectral Method for Permutation Synchronization [8.517406772939292]
  置換同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。 本稿では,新しい,統計的に最適なスペクトルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-21T17:43:26Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• A doubly stochastic matrices-based approach to optimal qubit routing [0.0]
  スワップマッピングは、SWAPゲートによって論理量子回路を等価な物理実装可能なものにマッピングする量子コンパイラ最適化である。 本研究では、置換行列の組み合わせとして定義される二重凸行列と呼ばれる構造を用いる。 提案アルゴリズムは,追加時間のコストで,アートアルゴリズムSABREの状態と比較して,大幅な深度低減を実現することができることを示す。
  論文  参考訳（メタデータ） (2022-11-14T09:25:35Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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