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

• arxiv url: http://arxiv.org/abs/2410.21840v3
• Date: Mon, 11 Nov 2024 00:08:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:02:57.613632
• 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 vector permutation is fundamental to privacy-preserving computations based on batch-encoded homomorphic encryption, underpinning nearly all homomorphic matrix operation algorithms and predominantly influencing their complexity. A potential approach to optimize this critical component lies in permutation decomposition, a technique we consider as not yet fully explored. In this paper, we enhance the efficiency of homomorphic permutations through novel decomposition techniques, thus advancing privacy-preserving computations. We start by estimating the ideal performance of decompositions on permutations and proposing an algorithm that searches depth-1 ideal decomposition solutions. This enables us to ascertain the full-depth ideal decomposability of specific permutations in homomorphic matrix transposition (SIGSAC 18) and multiplication (CCSW 22), allowing these privacy-preserving computations to achieve asymptotic improvement in speed and rotation key reduction. We further devise a new method for computing arbitrary homomorphic permutations, aiming to approximate the performance of ideal decomposition, as permutations with weak structures are unlikely to be ideally factorized. Our design deviates from the conventional scope of permutation decomposition. It outperforms 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（参考訳）: ホモモルフィックベクトル置換は、バッチ符号化されたホモモルフィック暗号に基づくプライバシ保存計算の基本であり、ほぼすべてのホモモルフィック行列演算アルゴリズムの基盤となり、その複雑さに大きく影響する。 この重要なコンポーネントを最適化する潜在的なアプローチは、置換分解(permutation decomposition)にある。 本稿では、新しい分解手法により、同型置換の効率を向上し、プライバシー保護計算の効率化を図る。 まず、置換に対する分解の理想的な性能を推定し、深さ1の理想的な分解解を探索するアルゴリズムを提案する。 これにより、同相行列変換(SIGSAC 18)と乗算(CCSW 22)における特定の置換の完全なデコンポーザビリティを確認でき、これらのプライバシ保存計算により、速度と回転鍵の短縮の漸近的な改善が達成できる。 さらに、弱構造をもつ置換が理想的に分解される可能性が低いため、任意の同型置換を計算し、理想分解の性能を近似することを目的とした新しい手法を考案する。 我々の設計は、従来の置換分解の範囲から逸脱する。 最先端技術(EUROCRYPT 12、CRYPTO 14)より優れており、ローテーションキーの最低限の要件で最大$\times2.27$である。

関連論文リスト

• 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)

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

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