論文の概要: Fast \(\ell_\infty\)-Reduction of Rank-2 Lattices in $\mathbb{R}^n$ via a New Reduced-Basis Notion

• arxiv url: http://arxiv.org/abs/2610.24719v1
• Date: Sat, 17 Oct 2026 14:31:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-22 16:47:32.968846
• Title: Fast \(\ell_\infty\)-Reduction of Rank-2 Lattices in $\mathbb{R}^n$ via a New Reduced-Basis Notion
• Title（参考訳）: Fast \(\ell_\infty\)-新しい還元バシス記法による$\mathbb{R}^n$のランク2格子の還元
• Abstract要約: 最短ベクトル問題(SVP)は格子ベースの暗号における重要な格子問題である。 本研究では、$mathbbRn$の階数2の格子に焦点をあて、無限大ノルムの下で基底の減少という新しい概念を導入する。 提案アルゴリズムは,古典的なラグランジュ・ガウス還元の複雑性次数と一致する,$O(nT2)$の若干の複雑性を実現する。
• 参考スコア（独自算出の注目度）: 3.7992354494247675
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The shortest vector problem (SVP) under the infinity norm ($\ell_\infty$-norm) is an important lattice problem with applications in lattice-based cryptography. In particular, the security analysis of the post-quantum signature standard ML-DSA highlights the importance of finding short solutions satisfying infinity-norm constraints, rather than only Euclidean norm bounds. However, most existing lattice reduction algorithms are developed for the Euclidean norm, while dedicated studies under the infinity norm remain limited. In this work, we focus on rank-two lattices in $\mathbb{R}^n$ and introduce a new notion of reduced basis under the infinity norm. Based on this definition, we propose an efficient lattice basis reduction algorithm that performs a multi-dimensional analogue of Euclidean division using a dominant coordinate of the basis vectors. Each non-terminal iteration guarantees a factor-two decrease of the maximum infinity norm of the basis vectors. We prove that the algorithm terminates and achieves a bit complexity of $O(nT^2)$, matching the asymptotic complexity order of the classical Lagrange--Gauss reduction. Moreover, the proposed algorithm saves at least $2n$ multiplications per iteration compared with the classical approach. Experiments demonstrate significant runtime improvements, especially for high-dimensional lattices. This work provides a foundation for developing lattice reduction techniques under the infinity norm.
• Abstract（参考訳）: 最短ベクトル問題(SVP)は、格子ベースの暗号における重要な格子問題である。 特に、ポスト量子署名標準ML-DSAのセキュリティ分析は、ユークリッドノルム境界だけでなく、無限ノルム制約を満たす短い解を見つけることの重要性を強調している。 しかしながら、既存の格子還元アルゴリズムのほとんどはユークリッドノルムのために開発されているが、無限大ノルムに基づく専用研究は限定的である。 本研究では、$\mathbb{R}^n$ の階数 2 の格子に焦点をあて、無限大ノルムの下で還元基底という新しい概念を導入する。 この定義に基づいて、基底ベクトルの優越座標を用いてユークリッド分割の多次元アナログを実行する効率的な格子基底還元アルゴリズムを提案する。 各非終端反復は、基底ベクトルの最大無限大ノルムの係数2の減少を保証する。 このアルゴリズムは古典的なラグランジュ-ガウス還元の漸近的複雑性次数と一致する$O(nT^2)$を終了し、少し複雑化することを示す。 さらに、提案アルゴリズムは、古典的なアプローチと比較して、イテレーション毎に少なくとも2n$の乗算を節約する。 実験では特に高次元格子において、実行時の大幅な改善が示されている。 この研究は、無限大ノルムの下で格子還元技術を開発するための基盤を提供する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization [0.0]
  2つのOFOノイズ耐性アルゴリズムが提示され、制約を扱い、不正確な勾配を扱い、二階情報を使用する。 数値実験は、PDEに基づく問題から深層ニューラルネットワークトレーニングに至るまでの応用について論じ、その卓越した計算効率を示す。
  論文  参考訳（メタデータ） (2025-07-15T17:32:10Z)
• Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
  2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。 我々は、ユークリッドアルゴリズムを次元にわたって戦略的に適用する効率的な適応格子削減アルゴリズム textbfCrossEuc を開発した。 textbfHVecを反復的に呼び出すことによって、最適化されたアルゴリズム textbfHVecSBP は、ビット長$n$の任意の入力ベースに対して$O(log n M(n) )$ time の還元基底を得る。
  論文  参考訳（メタデータ） (2025-04-17T13:50:51Z)
• Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity [6.78476672849813]
  本稿では,アンカード・エクストラグラディエントとネステロフのアクセルド・エクストラグラディエントという,2種類のエクストラグラディエント・ベースの手法について検討する。 我々は、より広い範囲のスキームにモノトン包摂を包含するアンカー付き指数関数のクラスを統一し、一般化する。 我々は、包含性を解決するために、Nesterovの高速化された指数関数の新たなクラスを提案する。
  論文  参考訳（メタデータ） (2025-01-08T16:06:15Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  非負の行列因子化(NMF)は、非負のデータを部品ベースの表現で表すことの有効性から、近年広く研究されている。 そこで本研究では,係数行列に対数ノルムを課した新しいNMF法を提案する。 提案手法のロバスト性を高めるために,$ell_2,log$-(pseudo) ノルムを新たに提案した。
  論文  参考訳（メタデータ） (2022-04-22T11:38:10Z)

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

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