論文の概要: Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

• arxiv url: http://arxiv.org/abs/2604.22900v1
• Date: Fri, 24 Apr 2026 13:54:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:07.043228
• Title: Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection
• Title（参考訳）: モジュール格子セキュリティ(第2報):最適符号選択によるモジュール格子削減
• Authors: Ming-Xing Luo,
• Abstract要約: 我々はCDPR格子削減アルゴリズムを理想からモジュール格子に拡張する。 精度を制御するため,完全分割素数でCRTスケールのラウンドリングを導入する。 さらに,CDPR符号選択サブプロブレムを混合整数線形プログラムとして再構成する。
• 参考スコア（独自算出の注目度）: 1.0152838128195467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We extend the CDPR lattice reduction algorithm from ideal to module lattices, leveraging the trace orthogonality of the power basis to decompose the module into rank-1 submodules and applying CDPR independently to each. This base module reduction achieves a Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matching the ideal case, with a module reduction factor $O(1)$ independent of the rank, under a balance hypothesis automatically satisfied for MLWE-distributed bases. To control precision, we introduce CRT-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding error and yielding a bounded-precision implementation. We further reformulate the CDPR sign-selection subproblem as a mixed-integer linear program, determining the optimal balanced discrepancy to be a universal constant $δ^*\approx 0.4407$. All results build on the class number one condition $h_k^+=1$ established in Part I of this series.
• Abstract（参考訳）: 我々は、CDPR格子削減アルゴリズムを理想からモジュール格子に拡張し、パワー基底のトレース直交を利用して、モジュールをランク1サブモジュールに分解し、それぞれに独立してCDPRを適用する。 この基底加群還元は、MLWE分散基底に対して自動的に満たされるバランス仮説の下で、理想的なケースと、ランクから独立な加群還元係数$O(1)$とを一致させるヘルミート因子$\exp(\tilde{O}(\sqrt{n}))を達成させる。 精度制御のために,完全分割素数でのCRTスケールのラウンドリングを導入し,Gram-Schmidtラウンドリング誤差を低減し,有界精度実装を実現する。 さらに、CDPR符号選択サブプロブレムを混合整数線形プログラムとして再構成し、最適平衡誤差を普遍定数$δ^*\approx 0.4407$と判定する。 すべての結果はクラス番号 1 の条件 $h_k^+=1$ に基づいて構築される。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  サブセット Sum 問題にモジュラー算術的アプローチを導入する。 本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
  論文  参考訳（メタデータ） (2024-08-28T19:32:14Z)
• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice [5.543220407902113]
  濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。 特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。 提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
  論文  参考訳（メタデータ） (2021-11-19T12:07:16Z)
• Faster First-Order Algorithms for Monotone Strongly DR-Submodular Maximization [11.919431962501479]
  連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。 そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-15T18:53:14Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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