論文の概要: Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited

• arxiv url: http://arxiv.org/abs/2504.12948v1
• Date: Thu, 17 Apr 2025 13:50:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-18 14:34:54.287572
• Title: Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited
• Title（参考訳）: 2次元格子における最短ベクトル問題のアルゴリズムの再検討
• Authors: Lihao Zhao, Chengliang Tian, Jingguo Bi, Guangwu Xu, Jia Yu,
• Abstract要約: 2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。 我々は、ユークリッドアルゴリズムを次元にわたって戦略的に適用する効率的な適応格子削減アルゴリズム textbfCrossEuc を開発した。 textbfHVecを反復的に呼び出すことによって、最適化されたアルゴリズム textbfHVecSBP は、ビット長$n$の任意の入力ベースに対して$O(log n M(n) )$ time の還元基底を得る。
• 参考スコア（独自算出の注目度）: 4.843809993270313
• License:
• Abstract: Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry. While simpler than its high-dimensional counterpart, two-dimensional SVP motivates scalable solutions for high-dimensional lattices and benefits applications like sequence cipher cryptanalysis involving large integers. In this work, we first propose a novel definition of reduced bases and develop an efficient adaptive lattice reduction algorithm \textbf{CrossEuc} that strategically applies the Euclidean algorithm across dimensions. Building on this framework, we introduce \textbf{HVec}, a vectorized generalization of the Half-GCD algorithm originally defined for integers, which can efficiently halve the bit-length of two vectors and may have independent interest. By iteratively invoking \textbf{HVec}, our optimized algorithm \textbf{HVecSBP} achieves a reduced basis in $O(\log n M(n) )$ time for arbitrary input bases with bit-length $n$, where $M(n)$ denotes the cost of multiplying two $n$-bit integers. Compared to existing algorithms, our design is applicable to general forms of input lattices, eliminating the cost of pre-converting input bases to Hermite Normal Form (HNF). The comprehensive experimental results demonstrate that for the input lattice bases in HNF, the optimized algorithm \textbf{HVecSBP} achieves at least a $13.5\times$ efficiency improvement compared to existing methods. For general-form input lattice bases, converting them to HNF before applying \textbf{HVecSBP} offers only marginal advantages in extreme cases where the two basis vectors are nearly degenerate. However, as the linear dependency between input basis vectors decreases, directly employing \textbf{HVecSBP} yields increasingly significant efficiency gains, outperforming hybrid approaches that rely on prior \textbf{HNF} conversion.
• Abstract（参考訳）: 2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。 2次元のSVPは高次元の格子に対するスケーラブルな解を動機付け、大きな整数を含むシーケンス暗号解析のような応用の恩恵を受ける。 本研究では,まず,削減基底の新たな定義を提案し,次元をまたいだユークリッドアルゴリズムを戦略的に適用した適応格子削減アルゴリズム \textbf{CrossEuc} を開発した。 このフレームワーク上に構築された \textbf{HVec} は、もともと整数に対して定義された半GCDアルゴリズムのベクトル一般化であり、2つのベクトルのビット長を効率よく半減し、独立な関心を持つことができる。 繰り返し呼び出しを行うことで、最適化されたアルゴリズム \textbf{HVecSBP} は、ビット長$n$の任意の入力ベースに対して$O(\log n M(n) )$ time を減らし、$M(n)$は2$n$ビット整数を乗算するコストを表す。 既存のアルゴリズムと比較して、我々の設計は入力格子の一般的な形式に適用でき、Hermite Normal Form (HNF)への事前変換のコストを削減できる。 総合的な実験結果から,HNF の入力格子基底に対して最適化アルゴリズム \textbf{HVecSBP} が,既存の手法に比べて少なくとも13.5\times$効率の改善を達成できることが示されている。 一般形式の入力格子基底に対して、それらを HNF に変換して \textbf{HVecSBP} を適用すると、2つの基底ベクトルがほぼ退化している極端な場合において、限界的な利点しか得られない。 しかし、入力基底ベクトル間の線形依存性が減少するにつれて、直接的に \textbf{HVecSBP} を用いると、より顕著な効率向上が得られ、以前の \textbf{HNF} 変換に依存するハイブリッドアプローチよりも優れている。

関連論文リスト

• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions [0.0]
  我々は,暗号アルゴリズムに焦点をあてて,準拘束的二項最適化の最先端を推し進めることを目指している。 AES-128/192/256、MD5、SHA1、SHA256など、最も広く使われている暗号アルゴリズムについて考察する。 これらの結果から,QUBO 行列のスパースと係数の大きさを低く保ちながら,これまでに公表した結果と比較して,QUBO のインスタンスを数千の論理変数で減らした。
  論文  参考訳（メタデータ） (2024-09-10T18:46:26Z)
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes [1.8416014644193066]
  共次元$k$ over $mathbbZ_Pd$, ここでは$P$は素数である。 共次元の$$は、プロジェクションのパッキング特性である mod $P$ を1つの双対符号ワードに初期セットの非格子ベクトルに利用することで解決される。 そこで本研究では,反復数,すなわち全長拡大係数を最小化して,短い格子ベクトルが得られることを示す。
  論文  参考訳（メタデータ） (2024-01-22T22:17:41Z)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。 計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
  論文  参考訳（メタデータ） (2023-06-14T02:54:12Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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