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

• arxiv url: http://arxiv.org/abs/2410.21840v4
• Date: Sat, 30 Nov 2024 00:40:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-03 16:54:05.022972
• Title: Optimized Homomorphic Permutation From New Permutation Decomposition Techniques
• Title（参考訳）: 新しい置換分解法による均一置換の最適化
• Authors: Xirong Ma, Junling Fang, Dung Hoang Duong, Yali Jiang, Chunpeng Ge, Yanbin Li,
• Abstract要約: ホモモルフィックな置換は、バッチエンコーディングのホモモルフィック暗号に基づくプライバシ保存計算の基礎となる。 本稿では,新しい分解手法により,同相置換の効率を向上させる。
• 参考スコア（独自算出の注目度）: 1.8911961520222993
• License:
• Abstract: Homomorphic permutation is fundamental to privacy-preserving computations based on batch-encoding homomorphic encryption. It underpins nearly all homomorphic matrix operation algorithms and predominantly influences their complexity. Permutation decomposition as a potential approach to optimize this critical component remains underexplored. In this paper, we enhance the efficiency of homomorphic permutations through novel decomposition techniques, advancing homomorphic encryption-based privacy-preserving computations. We start by estimating the ideal effect of decompositions on permutations, then propose an algorithm that searches depth-1 ideal decomposition solutions. This helps us ascertain the full-depth ideal decomposability of permutations used in specific secure matrix transposition and multiplication schemes, allowing them to achieve asymptotic improvement in speed and rotation key reduction. We further devise a new method for computing arbitrary homomorphic permutations, considering that permutations with weak structures are unlikely to be ideally factorized. Our design deviates from the conventional scope of decomposition. But it better approximates the ideal effect of decomposition we define than the state-of-the-art techniques, with a speed-up of up to $\times 2.27$ under minimal rotation key requirements.
• Abstract（参考訳）: ホモモルフィックな置換は、バッチエンコーディングのホモモルフィック暗号に基づくプライバシ保存計算の基礎となる。 ほぼすべてのホモモルフィック行列演算アルゴリズムを基盤としており、その複雑さに大きく影響している。 この重要なコンポーネントを最適化するための潜在的なアプローチとしての置換分解は、未検討のままである。 本稿では、新しい分解手法により、同相の置換の効率を向上し、同相の暗号化に基づくプライバシ保存計算を前進させる。 まず、置換に対する分解の理想的な効果を推定し、深さ1の理想的な分解解を探索するアルゴリズムを提案する。 これにより、特定のセキュアな行列変換や乗算スキームで使用される置換の完全な理想的分解可能性を確認し、速度と回転鍵の減少の漸近的な改善を達成できる。 さらに、弱構造をもつ置換が理想的に分解される可能性が低いことを考慮し、任意の準同型置換を計算するための新しい手法を考案する。 我々の設計は従来の分解の範囲から逸脱する。 しかし、これは我々が定義する分解の理想的な効果を、最小の回転鍵条件下で最大2.27$のスピードアップで、最先端技術よりも近似した方がよい。

関連論文リスト

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

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

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