論文の概要: Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

• arxiv url: http://arxiv.org/abs/2609.34996v1
• Date: Mon, 28 Sep 2026 12:04:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-02 17:57:41.63027
• Title: Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
• Title（参考訳）: サイクロトミックコセット:隠れ部分群と素電力変調のための量子シービングアルゴリズム
• Abstract要約: 隠れ部分群構造を正確に保存する DCP のシクロトミック一般化を導入する。 得られた$-adicイデアル鎖を利用して、相状態の modulo $L,L-1,ldots,ldots を減少させる量子シーブを構築する。 我々の結果だけでは、標準LWEの準多項式時間アルゴリズムは得られない。
• 参考スコア（独自算出の注目度）: 2.9105492398209116
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
• Abstract（参考訳）: LWE問題(Learning With Errors)は、量子後暗号における基本的な前提である。 レゼフは、LWE から DCP (Dhedral Coset Problem) への量子還元を確立した。 その後、ブラカースキーらは外挿二面コセット問題 (EDCP) を導入し、LWEと等価性を証明した。 しかし、DCPとは異なり、EDCPはコセット構造をもはや認めない。 これにより、隠れた部分群問題に対するテクニックの直接適用が制限される。 本研究では, DCP のサイクロトミック一般化であるCyclotomic Coset Problem (CCP) を導入する。 1 のプリミティブ $p$-th root とし、n を $π= π-1$ とし、q=p^t$ と $L=t(p-1)$ と書く。 我々は$R_q=\mathbb Z_q[n_p] \cong \mathbb Z[n_p]/(π^L)$上で働き、同型は全分岐単位$から従う。 (p)=(π)^{p-1}$。 結果として得られる$π$-進イデアル鎖を利用して、相状態 modulo $π^{L},π^{L-1},\ldots,π$ を連続的に減少させる量子シーブを構成する。 固定素数$p$と modulus $q=p^t$ に対して、我々のアルゴリズムは時間とサンプルの複雑さで CCP を解く。 q)}$, 多項式量子空間を用いる。 シーブは均一なEDCPとガウスS|LWE>にも適用され、$q=\text{poly}(n)$のとき、上記のすべての問題に対して準多項式時間アルゴリズムが生成される。 これは、Bai et al (CRYPTO 2025)の2つのEDCPシーブ(英語版)をシクロトミックセッティングに拡張する。 しかし,本研究の結果は,標準LWEの準多項式時間アルゴリズムを生成できないことが強調されている。

関連論文リスト

• Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields [1.4323566945483497]
  有限体上のローレントルムの解数の近似について検討する。 我々の最初の主要な結果は、成功確率1-$で、$widehat(f)$ fulfilling [ |widehatN(f) - N(f)| le varepsilon qn+s/2-]を出力する量子アルゴリズムである。 2つ目の主要な結果として、ランダム時間チューリング還元の下で同じ問題が$#$P-hardになることを示す。
  論文  参考訳（メタデータ） (2026-08-25T00:23:27Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics [1.0152838128195467]
  ML-KEMと関連する2パワーサイクロトミック格子スキームに対する量子攻撃を提案する。 ML-KEM-1024の近似係数は, ML-KEM-1024に対して$le 21 q/2=1664.5$を満たす。 解析を量子アルゴリズムを用いて2パワーのサイクロトミック環上でファルコン、ホーク、NTRUに拡張する。
  論文  参考訳（メタデータ） (2026-05-17T12:16:04Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• Pauli-based model of quantum computation with higher-dimensional systems [0.0]
  パウリベースの計算(英: Pauli-based calculation、PBC)は、量子ビットを用いた量子計算の普遍モデルである。 奇数原始次元系のPBCを一般化し、その普遍性を実証する。
  論文  参考訳（メタデータ） (2023-02-27T12:05:13Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

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