論文の概要: Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$

• arxiv url: http://arxiv.org/abs/2609.37482v1
• Date: Sat, 26 Sep 2026 22:07:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.520866
• Title: Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$
• Title（参考訳）: Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$
• Abstract要約: ハールランダムな一モジュラー格子上の格子 我々は、Haar-random 格子上での Sieving と同じ複雑さを確実に達成できることを示す。
• 参考スコア（独自算出の注目度）: 0.3437656066916039
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In an attempt to close the gap between the best provable and heuristic algorithms for hard lattice problems, such as the shortest (SVP) and closest vector problem (CVP), we analyze lattice sieving on Haar-random unimodular lattices. With well-chosen modifications to heuristic sieving, we show that the heuristic assumptions are no longer necessary, and we can provably achieve the same complexities as heuristic sieving on Haar-random lattices for various lattice problems. Concretely, with probability $1 - o(1)$ over the randomness of the Haar-random lattice and the algorithmic randomness, we show how to: 1. Solve SVP in time $2^{0.2924\ldots n + o(n)}$ and space $2^{0.2075\ldots n + o(n)}$; 2. Solve CVP for random targets with the same complexities; 3. Produce $2^{0.2075\ldots n + o(n)}$ discrete Gaussian samples at any width with these complexities, up to a $2^{-Ω(n)}$ error in the joint distribution. This improves on the SVP complexities for Haar-random lattices of Pouly-Shen [Eurocrypt, 2026] running in time $2^{0.633n + o(n)}$ and space $2^{0.5n + o(n)}$, as well as the recent worst-case SVP (and average-case CVP) improvements of Gao-Feng-Hu and Hhan [Cryptology ePrint Archive, 2026], both running in time and space $2^{0.5n + o(n)}$ or higher. Similar to standard sieving methods, our approach proceeds through a series of thin spherical shells, starting from a large radius and iteratively combining vectors to obtain vectors from shells with smaller radius. Our main technical contribution is making a series of adjustments to guarantee that for each sieve list generated at each spherical shell, each list vector is independent and uniformly random over all lattice points within this shell. Once this invariant is satisfied, it is a matter of smooth sailing through the spherical shells until we find a solution.
• Abstract（参考訳）: 最短(SVP)と最短ベクトル問題(CVP)のようなハード格子問題に対する最も証明可能なアルゴリズムとヒューリスティックなアルゴリズムのギャップを埋めるために、Haar-random の一モジュラー格子上での格子シーリングを解析する。 ヒューリスティック Sieving に対するハウリスティックな修正により、ヒューリスティックな仮定はもはや不要であることが示され、様々な格子問題に対するハールランダムな格子上でヒューリスティックな Sieving と同じ複雑さを確実に達成できる。 具体的には、確率 1 - o(1)$ がハールランダム格子のランダム性とアルゴリズム的ランダム性に乗じて、次の方法を示す: 1. 時間 2^{0.2924\ldots n + o(n)}$ と空間 $2^{0.2075\ldots n + o(n)}$; 2. 同じ複素量を持つランダムターゲットに対して CVP を解く; 3. 2^{0.2075\ldots n + o(n)}$ これらの複素量を持つ任意の幅で離散ガウス標本を最大 2^{0.207(n)$ の誤差を与える。 これは Pouly-Shen [Eurocrypt, 2026] の Haar-random 格子の 2^{0.633n + o(n)}$ と space $2^{0.5n + o(n)}$ の SVP の複雑さを改善し、また最近の最悪のケースでは Gao-Feng-Hu と Hhan (Cryptology ePrint Archive, 2026] が 2^{0.5n + o(n)}$ 以上の時間で実行されている。 通常のシービング法と同様に、我々の手法は、大きな半径から始まる細い球状殻を通り、反復的にベクトルを結合してより小さい半径の殻からベクトルを得る。 我々の主な技術的貢献は、各球殻で生成された各シーブリストに対して、各リストベクトルが独立であり、このシェル内の全ての格子点に対して均一にランダムであることを保証するための一連の調整を行うことである。 一度この不変量を満たすと、溶液を見つけるまで球殻を滑らかに航行する問題である。

関連論文リスト

• Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions [5.603202398374589]
  ポテンシャルは$$-strongly convexと$L$-smoothであり、原点に関する半径$-1/2$の球に未知のモードがある。 Nstar_textTV=!left(log(1+)+ frac2right), ] $:=frac L$は条件数である。
  論文  参考訳（メタデータ） (2026-09-11T08:44:06Z)
• Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
  一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。 $t-設計はハール測度の最初の$tモーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)はハール測度と計算的に区別できないランダムユニタリーである。
  論文  参考訳（メタデータ） (2024-04-19T06:13:02Z)
• Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
  問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。 任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
  論文  参考訳（メタデータ） (2023-07-03T17:46:23Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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