論文の概要: 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))$ の指数的スピードアップをもたらす。

関連論文リスト

• Exact Coset Sampling for Quantum Lattice Algorithms [9.910562011343009]
  複雑なガウス窓を持つ最近のウィンドウ付きQFT格子アルゴリズムのステップ9において、競合する「ドメイン拡張」を簡易に置き換える。 我々の新しいサブルーチンは、未知のオフセットを正確にキャンセルするペアシフト差分によってドメイン拡張を置き換える。
  論文  参考訳（メタデータ） (2025-09-15T18:10:28Z)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• 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)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。 これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
  論文  参考訳（メタデータ） (2022-05-19T18:51:28Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling [0.0]
  弱シミュレーションはしばしば弱いシミュレーションと呼ばれ、量子的優位性をいつ求めるかを決定する方法である。 最低の$L_$ノルムサンプリングコストの上限を$mathcal O(xit delta-2)$から$t$の次の順序に構築的に締め付ける。 これは、我々の知識の最悪の場合において、この境界の有限t$への依存を下げた最初の弱いシミュレーションアルゴリズムである。
  論文  参考訳（メタデータ） (2021-04-15T05:50:11Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation [5.025654873456756]
  サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
  論文  参考訳（メタデータ） (2020-09-10T13:32:46Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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