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

• arxiv url: http://arxiv.org/abs/2410.21840v1
• Date: Tue, 29 Oct 2024 08:07:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-30 13:38:40.160999
• Title: Optimized Homomorphic Vector Permutation From New Decomposition Techniques
• Title（参考訳）: 新しい分解技術による均質ベクトルの最適置換
• Authors: Xirong Ma, Junling Fang, Steven Duong, Yali Jiang, Chunpeng Ge,
• Abstract要約: 同型置換は、単語単位の同型暗号に基づくプライバシー保護計算の基礎となる。 本稿では、置換の任意の分解の理想的な性能を定義し、この境界を達成するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 1.1534313664323634
• 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 $\times 1.05 \sim \times 2.27$ under minimum requirement of rotation keys.
• Abstract（参考訳）: 同型置換は、ワードワイドの同型暗号に基づくプライバシー保護計算の基本であり、置換分解によって高速化される。 本稿では、置換の任意の分解の理想的な性能を定義し、この境界を達成するアルゴリズムを設計する。 まず、置換に対するdeep-1理想的な分解解を求めるアルゴリズムを提案する。 これにより、特定のホモモルフィック行列変換(SIGSAC 18)と乗算(CCSW 22)で使用される2種類の置換の完全なデコンポーザビリティを確認でき、これらのアルゴリズムは速度と回転鍵の減少の漸近的な改善を達成できる。 さらに、弱構造をもつ置換が理想的に分解される可能性が低いため、理想分解の性能限界を近似することを目的として、任意の置換を同型に計算する新しい戦略を考案する。 我々の設計は、従来の置換分解のスコープから逸脱し、ローテーションキーの最低限の条件で、$\times 1.05 \sim \times 2.27$のスピードアップで最先端技術(EUROCRYPT 12, CRYPTO 14)を超える。

関連論文リスト

• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。 標準的な暗号仮定では、既存のアルゴリズムよりも高速なアルゴリズムを設計できることを示す。
  論文  参考訳（メタデータ） (2025-02-18T17:08:59Z)
• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  置換を進化させるには、特別な進化作用素が必要である。 本稿では、置換のための進化的演算子の幅を調査する。 これらのすべては、進化計算のためのオープンソースのJavaライブラリであるChips-n-Salsaで実装しています。
  論文  参考訳（メタデータ） (2023-11-24T16:32:44Z)
• 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)
• 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)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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