論文の概要: Predicting Module-Lattice Reduction

• arxiv url: http://arxiv.org/abs/2510.10540v1
• Date: Sun, 12 Oct 2025 10:46:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:29.998906
• Title: Predicting Module-Lattice Reduction
• Title（参考訳）: モジュール格子低減予測
• Authors: Léo Ducas, Lynn Engelberts, Paola de Perthuis,
• Abstract要約: モジュール-格子還元の具体的な平均ケース解析について述べる。 モジュール-BKZは非構造的よりもブロックサイズが大きいと結論付ける。 我々は、いくつかのシクロトミックフィールドに対するモジュール-BKZの最初のオープンソース実装を提供する。
• 参考スコア（独自算出の注目度）: 5.378188812712555
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as 'Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehl\'e, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens-Davidowitz, CRYPTO 2020) confirmed the existence of such module variants of LLL and block-reduction algorithms, but focus only on provable worst-case asymptotic behavior. In this work, we present a concrete average-case analysis of module-lattice reduction. Specifically, we address the question of the expected slope after running module-BKZ, and pinpoint the discriminant $\Delta_K$ of the number field at hand as the main quantity driving this slope. We convert this back into a gain or loss on the blocksize $\beta$: module-BKZ in a number field $K$ of degree $d$ requires an SVP oracle of dimension $\beta + \log(|\Delta_K| / d^d)\beta /(d\log \beta) + o(\beta / \log \beta)$ to reach the same slope as unstructured BKZ with blocksize $\beta$. This asymptotic summary hides further terms that we predict concretely using experimentally verified heuristics. Incidentally, we provide the first open-source implementation of module-BKZ for some cyclotomic fields. For power-of-two cyclotomic fields, we have $|\Delta_K| = d^d$, and conclude that module-BKZ requires a blocksize larger than its unstructured counterpart by $d-1+o(1)$. On the contrary, for all other cyclotomic fields we have $|\Delta_K| < d^d$, so module-BKZ provides a sublinear $\Theta(\beta/\log \beta)$ gain on the required blocksize, yielding a subexponential speedup of $\exp(\Theta(\beta/\log \beta))$.
• Abstract（参考訳）: モジュール格子還元は非構造格子還元よりも優れているか? この問題は、Kyber NIST の標準化申請書 (Avanzi et al , 2021) で "Q8" として強調され、Kyber や他のモジュール-格子ベースのスキームの具体的なセキュリティに影響を与える可能性がある。 Lee, Pellet-Mary, Stehl\'e, Wallet, ASIACRYPT 2019; Mukherjee and Stephens-Davidowitz, CRYPTO 2020) は、LLLおよびブロック還元アルゴリズムのそのようなモジュール変種の存在を確認したが、証明可能な最悪の症例漸近行動のみに焦点を当てた。 本研究では,モジュール-格子還元の具体的な平均ケース解析について述べる。 具体的には、モジュール-BKZを実行した後の予想される斜面の問題に対処し、この斜面を駆動する主量として、手元にある数体の判別値$\Delta_K$をピンポイントする。 これをブロックサイズ $\beta$: module-BKZ in a number field $K$ of degree $d$ の SVP oracle of dimension $\beta + \log(|\Delta_K| / d^d)\beta /(d\log \beta) + o(\beta / \log \beta)$ のブロックサイズ $\beta$ の非構造的 BKZ と同じ勾配に達するために変換する。 この漸近的な要約は、実験的に検証されたヒューリスティックスを用いて具体的に予測する更なる用語を隠蔽する。 ちなみに、いくつかのシクロトミックフィールドに対して、モジュール-BKZの最初のオープンソース実装を提供する。 2つのシクロトミック場に対して、$|\Delta_K| = d^d$ が存在し、加群-BKZ は非構造体よりも $d-1+o(1)$ のブロックサイズを必要とすると結論付ける。 逆に、他のすべてのシクロトミック場に対して、$|\Delta_K| < d^d$ を持つので、加群-BKZ は必要となるブロックサイズに対する部分線型 $\Theta(\beta/\log \beta)$ のゲインを提供し、$\exp(\Theta(\beta/\log \beta))$ の指数的スピードアップをもたらす。

関連論文リスト

• Lasso and Partially-Rotated Designs [2.28438857884398]
  我々は新しい$textitsemirandom$ family of designを導入し、秘密に関する RE 定数は 0 から外される。 その結果,Lassoは予測誤差$O(k log d / lambda_min n)$を高い確率で達成していることがわかった。
  論文  参考訳（メタデータ） (2025-05-16T10:25:08Z)
• Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy [17.711455925206298]
  HuとMehta(2024年)は、オープンな問題を提起した:$varepsilon$-differential privacyの下で、決定論的オンライン学習($K$アクションと$T$ラウンドを含む)の最適なインスタンス依存率は何ですか?
  論文  参考訳（メタデータ） (2025-02-16T05:13:51Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Measurement-induced phase transition for free fermions above one dimension [46.176861415532095]
  自由フェルミオンモデルに対する$d>1$次元における測定誘起エンタングルメント相転移の理論を開発した。 臨界点は、粒子数と絡み合いエントロピーの第2累積のスケーリング$$elld-1 ln ell$でギャップのない位相を分離する。
  論文  参考訳（メタデータ） (2023-09-21T18:11:04Z)
• Improved Langevin Monte Carlo for stochastic optimization via landscape modification [0.0]
  目的関数$H$を最小にするか,あるいは目標とするGibbs分布$pi_beta0propto e-beta H$を低温からサンプリングすると,本論文では,代替ランドスケープで動作するLangevin Monte Carlo (LMC)アルゴリズムを提案し,解析する。 変換されたランドスケープのエネルギー障壁は減少し、その結果、$pif_beta,c,1$に付随する修正Log-Sobolev定数の$beta$と$M$の両方に依存することが示される。
  論文  参考訳（メタデータ） (2023-02-08T10:08:37Z)
• Smooth Non-Stationary Bandits [49.19728527803684]
  本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。 スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
  論文  参考訳（メタデータ） (2023-01-29T06:03:20Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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