論文の概要: 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$である。
関連論文リスト
- 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) - A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
置換を進化させるには、特別な進化作用素が必要である。
本稿では、置換のための進化的演算子の幅を調査する。
これらのすべては、進化計算のためのオープンソースのJavaライブラリであるChips-n-Salsaで実装しています。
論文 参考訳（メタデータ） (2023-11-24T16:32:44Z) - Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations
by QUBO and Ising Models with Quadratic Sizes [0.14454647768189902]
本稿では、二重行列ドメインウォールと呼ばれる新しい置換符号化手法を提案する。
これは、カーネル内の二次項の数と最大絶対係数値を著しく減少させる。
また、部分置換と準非制約バイナリ最適化(QUBO)モデルへの符号化手法の適用性を実証する。
論文 参考訳（メタデータ） (2023-08-02T09:15:30Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - 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) - 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) - Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on
Clustered Shortest-Path Tree problem [2.578242050187029]
CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。
探索処理の性能を向上させるために,2つの手法を提案する。
論文 参考訳（メタデータ） (2020-10-19T08:37:18Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。