論文の概要: Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$

• arxiv url: http://arxiv.org/abs/2503.23238v1
• Date: Sat, 29 Mar 2025 22:32:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-01 14:32:13.437641
• Title: Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
• Title（参考訳）: WagnerのアルゴリズムはSIS$^\infty$の指数時間で実行可能である
• Authors: Léo Ducas, Lynn Engelberts, Johanna Loyer,
• Abstract要約: Avariant of the Blum-Kalai-Wasserman (B) algorithm should solve the Learning with Errors problem (LWE) 我々は、このワグナーステップを、投影された格子の連鎖を後方に歩き、補助的な超格子をジグザグするものとして再解釈する。 このアプローチはサンプル増幅を回避し、ワグナーのアルゴリズムを$q$ary格子に対して近似した離散ガウス標本化器に変換する。
• 参考スコア（独自算出の注目度）: 4.908917260079968
• License:
• Abstract: At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus $q=\mathrm{poly}(n)$ and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner's algorithm (CRYPTO 2002), run over the corresponding dual problem, and the Aharonov-Regev distinguisher (JACM 2005). Hence the subexponential Wagner step alone should be of interest for solving this dual problem - namely, the Short Integer Solution problem (SIS) - but this appears to be undocumented so far. We re-interpret this Wagner step as walking backward through a chain of projected lattices, zigzagging through some auxiliary superlattices. We further randomize the bucketing step using Gaussian randomized rounding to exploit the powerful discrete Gaussian machinery. This approach avoids sample amplification and turns Wagner's algorithm into an approximate discrete Gaussian sampler for $q$-ary lattices. For an SIS lattice with $n$ equations modulo $q$, this algorithm runs in subexponential time $\exp(O(n/\log \log n))$ to reach a Gaussian width parameter $s = q/\mathrm{polylog}(n)$ only requiring $m = n + \omega(n/\log \log n)$ many SIS variables. This directly provides a provable algorithm for solving the Short Integer Solution problem in the infinity norm ($\mathrm{SIS}^\infty$) for norm bounds $\beta = q/\mathrm{polylog}(n)$. This variant of SIS underlies the security of the NIST post-quantum cryptography standard Dilithium. Despite its subexponential complexity, Wagner's algorithm does not appear to threaten Dilithium's concrete security.
• Abstract（参考訳）: CRYPTO 2015において、Kirchner と Fouque は Blum-Kalai-Wasserman (BKW) アルゴリズムの注意深く調整された変種 (JACM 2003) は、十分な LWE サンプルが与えられたとき、 modulus $q=\mathrm{poly}(n)$ に対してわずかに指数関数時間でLWE(Learning with Errors problem) を解くべきであると主張した。 モジュラービューをみると、BKWはワグナーのアルゴリズム(CRYPTO 2002)とアハロノフ=レーゲフ微分器(JACM 2005)の組み合わせと見なすことができる。 したがって、ワーグナーのステップだけでは、この二重問題(すなわち、ショート・インテガー・ソリューション問題(SIS))を解決することには興味があるはずだが、これまでのところ文書化されていないようだ。 我々は、このワグナーステップを、投影された格子の連鎖を後方に歩き、補助的な超格子をジグザグするものとして再解釈する。 さらに、ガウスのランダム化ラウンドリングを用いてバケットのランダム化を行い、ガウスの強力な離散機械を利用する。 このアプローチはサンプル増幅を回避し、ワグナーのアルゴリズムを$q$ary格子に対して近似した離散ガウス標本化器に変換する。 n$ 方程式を modulo $q$ とする SIS 格子に対して、このアルゴリズムは部分指数時間 $\exp(O(n/\log \log n))$ をガウス幅パラメータ $s = q/\mathrm{polylog}(n)$ に到達するために動作し、$m = n + \omega(n/\log \log n)$ 多くの SIS 変数を必要とする。 これは、ノルム境界$\beta = q/\mathrm{polylog}(n)$に対して、infinity norm$\mathrm{SIS}^\infty$)で短整数解を解くための証明可能なアルゴリズムを直接提供する。 このSISの派生型は、NISTのポスト量子暗号標準であるディリシウムのセキュリティの根底にある。 余分な複雑さにもかかわらず、ワグナーのアルゴリズムはディリシウムの具体的なセキュリティを脅かしていないように見える。

関連論文リスト

• Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions [0.3004066195320147]
  GFastは,f:mathbbZ_qnrightarrow mathbbR$のスパースフーリエ変換を計算するアルゴリズムである。 GFastは、ニューラルネットワークの予測的相互作用を、既存のアルゴリズムと比較して25%$より小さな正規化平均二乗誤差で説明する。
  論文  参考訳（メタデータ） (2025-01-21T18:45:09Z)
• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  サブセット Sum 問題にモジュラー算術的アプローチを導入する。 本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
  論文  参考訳（メタデータ） (2024-08-28T19:32:14Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem [2.90985742774369]
  SDLPは,いくつかの重要な症例においてさらに容易であることを示す。 SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
  論文  参考訳（メタデータ） (2023-12-21T16:58:59Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
  我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。 ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
  論文  参考訳（メタデータ） (2022-02-22T01:49:41Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)

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

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