技術要約：素数冪（べき）モジュラスにおける円分余集合、隠れ部分群、および量子シィービング

1. 問題の背景と動機

学習エラー問題（LWE）は、ポスト量子暗号における基礎的な仮定である。RegevがLWEから二面体余集合問題（DCP）への量子還元を確立し、その後BrakerskiらがEDCP（Extrapolated Dihedral Coset Problem）を導入してLWEとの等価性を証明したが、そこには重大な構造的制限が存在する。DCPとは異なり、一般的なEDCPは、平行移動の集合が部分群を形成しないため、厳密な隠れ部分群構造を持たない。この制限により、効率的な隠れ部分群手法の直接的な適用が困難となっている。特に、モジュラスが2の冪乗ではない場合には顕著である。

最近の研究（Bai et al., CRYPTO 2025）では、2進イデアル鎖を利用することで、2の冪乗モジュラス（$q=2^t$）におけるEDCPおよびガウス型$S|LWE\rangle$に対する準多項式時間の量子アルゴリズムを実現した。しかし、これを任意の素数冪モジュラス（$q=p^t$）へ一般化することは困難であった。なぜなら、位数$2q$の二面体群は、$q$が2の冪乗である場合にのみべき零（nilpotent）となるためである。その結果、標準的なべき零群シィービング技術（ImranおよびIvanyosらによるものなど）を、2の冪乗ではないモジュラスを持つEDCPやDCPに直接適用することができなかった。

2. 手法と核となる構成

2.1 円分余集合問題 (CCP)

一般的な素数冪におけるEDCPの隠れ部分群構造の欠如を克服するため、著者らは**円分余集合問題（Cyclotomic Coset Problem: CCP）**を導入する。この問題は、円分環 $R_q = \mathbb{Z}_q[\zeta_p]$（ここで $p$ は素数、$q=p^t$、$\zeta_p$ は原始$p$乗単数）上で定義される。

著者らは、半直積群 $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$ を定義した。この群はべき零であり、べき零度は $t(p-1)$ である。この群の中で、$(s, 1)$ によって生成される隠れ部分群 $H_s$ を特定する。ここで $s$ は秘密ベクトルである。この部分群に関連する余集合状態は、次のように表される：
$$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$$
ただし、$\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$ である。$p=2$ のとき、この構成は標準的なDCPに正確に帰着する。

2.2 円分環上の量子フーリエ変換 (QFT)

重要な技術的要素は、環 $R_L = R/\pi^L R$（ここで $\pi = \zeta_p - 1$）上の量子フーリエ変換の定義と効率的な実装である。著者らは、体跡（field trace）とイデアル $(p) = (\pi)^{p-1}$ の $\pi$ 進分解を用いて、CCPサンプルを**位相状態（phase states）**へと写像するQFTを構築した。

この変換により、余集合状態から $s$ を復元する問題が、秘密が量子状態の位相にエンコードされた**位相状態問題（Phase-State Problem: PSP）**へと変換される：
$$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$$
ここで $\chi_y$ は環の加法群の指標である。

2.3 量子シィービング・アルゴリズム

著者らは、「Simon-meets-Kuperberg」のフレームワークを円分の設定に適応させている。アルゴリズムは、$\pi$ 進イデアル鎖を用いてモジュラスのレベルを反復的に減少させることで動作する：
$$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$$

シィービング過程は以下のステップで行われる：

1. ゼロ和探索（Zero-Sum Search）： ラベル $y_i$ を持つ位相状態サンプルが与えられたとき、アルゴリズムは $\sum y_i \equiv 0 \pmod \pi$ となる部分列を見つけ出す。これは、$\pi$ に関する剰余に対して適用される決定論的なゼロ和探索アルゴリズム（ImranおよびIvanyosに基づく）を用いて達成される。
2. 状態結合（State Combination）： 対応する量子状態をテンソル積とし、特定の基底変換と測定を行うことで、より低い環 $R_{\pi^{L-1}}$ のラベルを持つ新しい位相状態サンプルを生成する。
3. 反復（Iteration）： このプロセスを $L-1$ 回繰り返し、問題を $\mathbb{F}_p$ 上のベースケースへと減少させる。その後、線形代数を用いて完全な秘密を復元する。
4. リフティング（Lifting）： $s \pmod p$ が求まった後、アルゴリズムは再帰的に高い冪乗の $p$ について解き、完全な秘密 $s \in \mathbb{Z}_q^n$ を復元する。

3. 主な貢献

1. CCPおよびCyLWEの導入： 本論文は、円分余集合問題（CCP）および円分LWE（CyLWE）を定義している。これらが、定数 $p$ に対して、それぞれの古典的な対応物（DCPおよびLWE）と等価であり、一般的なEDCPとは異なり、べき零群上の隠れ部分群構造を持つことを確立した。
2. 円分QFTと位相状態： 著者らは円分環 $R_q$ 上のQFTを厳密に定義し、CCPサンプルを位相状態へと変換する方法を示し、シィービング手法の適用を可能にした。
3. 準多項式時間量子シィービング・アルゴリズム： 準多項式個数のサンプルが提供されるという条件下で、CCPを準多項式時間（$2^{O(\log n \log q)}$）で解く量子アルゴリズム（Algorithm 1）を提示した。これは多項式量の量子空間を使用する。
4. 先行研究の一般化： 本研究は、Baiらによる結果（$q=2^t$ に限定されていた）を、任意の素数冪モジュラス $q=p^t$ へと拡張した。
5. 等価性の証明： 以下の量子還元を提示した：
   • 素数冪モジュラスにおける一様EDCPおよびガウス型$S|LWE\rangle$は、CCPに還元できる。
   • したがって、一様EDCPおよびガウス型$S|LWE\rangle$に対して、準多項式時間の量子アルゴリズムが存在する。

4. 結果と計算量

• 計算量： 提案されたアルゴリズムは、多項式量の量子空間を用いて、時間およびサンプル計算量 $2^{O(\log n \log q)}$ でCCPを解く。
• 範囲： 結果は、$p$ が固定された素数である任意のモジュラス $q = p^t$ に適用される。
• 還元： 本論文は、CCPを解くことが、同様のパラメータ制約下で一様EDCPおよびガウス型$S|LWE\rangle$を解くことを可能にすることを確立している。

5. 意義と限界

著者らは、本研究が素数冪モジュラスにおける格子問題に対する量子アルゴリズムの理解を大きく進展させた一方で、標準的なLWEに対する準多項式時間のアルゴリズムをもたらすものではないことを強調している。

この限界は、以下の還元連鎖に起因する：

1. 標準的なLWEはDCP（またはEDCP）に還元される。
2. DCP/EDCPはCCPに還元される。
3. CCPソルバーは準多項式個数のサンプルを必要とする。

LWEからDCP/EDCPへの既知の還元は、限られた（多項式量の）近似状態のみを生成する。CCPソルバーが必要とするサンプル数は、LWEからの還元によって得られるサンプル数を上回っているため、標準的なLWEを解くための全体的な計算量は依然として指数関数的なままである。

したがって、本論文の主要な貢献は理論的なものである。すなわち、べき零群シィービングの能力をより広いクラスのモジュラスへと拡張し、円分環上の余集合問題のための統一されたフレームワークを提供した点にある。同時に、標準的なLWEの安全性に対する直接的な脅威については、慎重な立場を維持している。