論文の概要: Provable Subexponential Algorithms for NIST Third-Round Lattice Families

• arxiv url: http://arxiv.org/abs/2610.11254v1
• Date: Thu, 08 Oct 2026 05:01:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:53.811636
• Title: Provable Subexponential Algorithms for NIST Third-Round Lattice Families
• Title（参考訳）: NIST 3線格子ファミリの確率的部分指数アルゴリズム
• Abstract要約: 提案手法は,NIST第3ラウンドの格子候補に関連付けられたパラメータ群の成長における秘密回復のための古典的部分指数アルゴリズムである。 雑音や丸い線形関係に対して、各座標推定によって定義される比較ベクトルの2乗ユークリッドノルムの正確なギャップを利用する。 我々は、2つのモジュライの素数とパワーに対する構造化された公開作用素の新たな境界によって、必要なサンプリング保証を確立する。
• 参考スコア（独自算出の注目度）: 1.9485627909326053
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.
• Abstract（参考訳）: 提案手法は,NIST第3ラウンドの格子候補に関連付けられたパラメータ群の成長における秘密回復のための古典的部分指数アルゴリズムである。 ここでは, Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, Dilithium/ML-DSAファミリーについて, 多項式モジュラーおよび多対数係数のスケールにより, 期待時間と空間2^{(1/2+o(1))n/\ln\ln n}$の短い秘密成分の回復が得られた。 雑音や丸い線形関係に対して、各座標推定によって定義される比較ベクトルの2乗ユークリッドノルムの正確なギャップを利用する。 1つのガウスリストは、他のリストを列挙することなく、バイナリーサーチによってすべての秘密座標を識別するのに十分である。 我々は、素数と2つのモジュライのパワーに関する構造化された公開作用素に対する新しい幾何学的境界により、必要なサンプリング保証を確立する。 建設は、ダカス、エンゲルバート、ロイヤー(CRYPTO 2025)のワグナー式のガウス式サンプリングフレームワークと、ハン、ガオ、フの低エラー決定LWEアルゴリズム(2026)をベースにしている。 NTRU型の商関係を推定するために,アフィンスライス探索 (アフィンスライス探索): 固定座標は公共格子のスライスに候補対を限定し,その推定ガウス質量は次の座標の選択を導く。 前述のモジュラー窓では、ファルコンのキージェネレーションの品質条件が必要とされる質量を供給している。 アルゴリズムは、時間と空間が 2^{O(n/\ln\ln n)}$ の確率の高い等価署名キーを復元する。 同じ検索で、環状NTRU-HPS/HRSSの短いキーコアが復元される。 これらの結果から、7つのNIST3ラウンド格子候補に付随する問題族に対する部分指数アルゴリズムが得られた。 半指数的な複雑さにもかかわらず、我々の結果は、現在特定されているパラメータ集合の具体的なセキュリティを低下させるものではない。

関連論文リスト

• H2CE: Modeling Geo-Semantic Interactions for POI Reranking with Heterogeneous Two-Stage Cross-Encoders [50.334243169621175]
  ローカル検索におけるPOI(Point-of-Interest)の再ランクは、クエリ条件付きトレードオフをモデル化する必要がある。 遅延バウンドPOIリグレードのための異種二段クロスエンコーダH2CEを提案する。
  論文  参考訳（メタデータ） (2026-10-08T05:40:08Z)
• Near-optimal node-private community estimation in polynomial-time [9.8953002257286]
  ブロックモデルの正確な回復のために,Klopp & Zadik の指数時間ノードプライベートアルゴリズムとほぼ一致した高確率ノードプライベートアルゴリズムを提案する。 提案アルゴリズムのプライバシ,ランタイム,ユーティリティを厳密に分析し,コミュニティの数がノード数nと対数的に増加する場合でも,プライバシパラメータepsがlog(n)として増加することで,正確なリカバリの最小値を達成することができることを示した。
  論文  参考訳（メタデータ） (2026-07-10T14:12:03Z)
• Quantum approaches to learning parity with noise [0.0]
  ノイズ問題に対するパリティに対して,量子的手法が代替的なアプローチを提供するかどうかを考察する。 Simonのアルゴリズムを実行すると、基本的に新しい学習サンプルが生成される。 これにより、1つ以上の変数を無視し、問題を反復的に減らすのに十分な新しいサンプルを作成できるのではないか、という期待が得られます。
  論文  参考訳（メタデータ） (2026-02-23T13:20:24Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• NK Hybrid Genetic Algorithm for Clustering [7.4854762711225025]
  本稿では,クラスタリングのためのNKハイブリッド遺伝的アルゴリズムを提案する。 実験では、NKハイブリッド遺伝的アルゴリズムは、他の遺伝的アルゴリズムや最先端のクラスタリングアルゴリズムと比較して非常に良い結果を得た。
  論文  参考訳（メタデータ） (2024-02-06T08:57:49Z)
• Scalable network reconstruction in subquadratic time [0.0]
  本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。 我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。 本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
  論文  参考訳（メタデータ） (2024-01-02T19:00:13Z)
• Robust affine point matching via quadratic assignment on Grassmannians [50.366876079978056]
  Robust Affine Matching with Grassmannians (RoAM) は点雲のアフィン登録を行うアルゴリズムである。 このアルゴリズムは、グラスマンの2つの要素間のフロベニウス距離を最小化することに基づいている。
  論文  参考訳（メタデータ） (2023-03-05T15:27:24Z)

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

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