Amazon Web Services（AWS）の暗号研究者Daniel R. Simonが、Oded Regevが格子問題との接続を示した2002年以来の空白を埋めると主張した。対象はDihedral Coset Problem（DCP、二面体コセット問題）で、Simonはこれを量子コンピューター上の多項式時間で解く手順を示したという。DCPには格子問題からの既存の還元があるため、証明が成立すれば格子暗号を支える困難性の一部にも影響が及ぶ。ただし、標準化された暗号への攻撃を実装した研究ではない。論文は公開直後のプレプリントであり、まず検証すべきなのは証明そのものである。
DCPに残っていた多項式時間の空白
Simonの論文「A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem」は、IACR Cryptology ePrint Archiveが2026年8月3日に受領し、同月6日に承認した。著者はSimon一人で、所属はAWS。掲載区分はプレプリントであり、DOIは付与されていない。査読済みの学術誌や会議に採録されたとの記載はなく、公開から日が浅いため独立した再現や追試の報告もまだない。
DCPでは、同じ未知量 s を埋め込んだ量子状態を複数受け取り、そこから s を回収する。各入力は、概略的には |0,x⟩ と |1,x+s⟩ の重ね合わせだ。Simonの主張は、この量子サンプルを入力サイズに対して多項式個使い、全体を多項式時間で処理できるというものである。固定の実測サンプル数を示した研究ではなく、入力が大きくなったときの増え方を論じる漸近解析だ。
従来の代表的な到達点は、Greg Kuperbergが『SIAM Journal on Computing』で示した劣指数時間の量子アルゴリズムだった。2005年の論文（DOI: 10.1137/S0097539703436345）は、時間と問い合わせ回数を 2^{O(√log N)} に抑えた。さらにShi Baiらは2025年のePrintプレプリントで、2のべき乗を法とする拡張DCP（eDCP）を準多項式時間で解くアルゴリズムを示した。この成果は2026年のPKCに収録されている。Simonのプレプリントが従来研究を超える点は、DCPそのものに多項式時間を主張したことにある。
subset-sum oracleを外す手順
技術上の難所は、量子サンプルに付いた不要な情報を消しながら、未知量 s を符号化した位相を壊さないことだ。Oded RegevはDCPをモジュラー部分和問題へ結び付ける手法を示したが、重要な消去処理にsubset-sum oracleという理想化された機構を置いていた。Simonは多数のサンプルをグループに分け、測定と選別を組み合わせて、oracleを使わずにサンプルビットを消す手順を提案する。
処理後の位相は、未知量の1ビットを別の量子ビットへ移す。これを再帰的に繰り返し、残りのビットを回収する。論文は、各段階で必要な量子情報が十分に残り、多項式回の反復によって成功確率を高められると論じている。したがって中心成果は、実機で観測した速度向上ではなく、アルゴリズムと確率評価からなる数学的証明である。量子回路のシミュレーション結果やハードウェア実験の結果も報告されていない。
入力に誤りが混じる場合にも条件がある。Simonは、所期の重ね合わせではなくランダムな古典情報を含む「faulty sample」の割合が、論文の表記で最大 1/O(log n) でもアルゴリズムが機能すると主張する。固定の誤り率を提示したわけではない。実験で耐性を測ったのではなく、定めた入力モデルの下で許容率のオーダーを導いた結果である。
格子問題へ届く範囲
DCPが暗号研究者の関心を集める理由は、DCPから格子問題へ攻撃が自然に飛び火するからではない。向きは逆で、格子問題をDCPへ変換する既存の還元があるためだ。Regevの「Quantum Computation and Lattice Problems」（FOCS 2002、DOI: 10.1109/SFCS.2002.1181976）は、DCPの効率的な解法を仮定し、unique Shortest Vector Problem（unique-SVP）へ量子アルゴリズムを与えた。
その後、Zvika Brakerski、Elena Kirshanova、Damien Stehlé、Weiqiang WenはPKC 2018の論文（DOI: 10.1007/978-3-319-76581-5_24）で、LWEとeDCPが量子多項式時間の還元で同値になることを示した。eDCPはDCPを緩和した問題で、緩和の幅はLearning With Errors（LWE）のノイズ率に応じて変わる。同論文はRegevの結果を「DCPが量子多項式時間で解ければLWEも解ける」と要約し、DCPの解法からLWEへ至る向きを明記している。
Simonは今回のDCPアルゴリズムを、Regevが示しBrakerskiらが改良した還元と組み合わせると説明する。その条件の下で、n 次元格子におけるShortest Vector Problem（SVP）の √n polylog(n) 近似や、論文の記号で α=√n polylog(n) と表されるLWEインスタンスを量子多項式時間で解けると述べている。
この主張は、DCPの証明が正しく、各還元の前提が満たされる場合の論理的な帰結だ。相関関係を測った研究でも、DCPの解法が暗号破りを引き起こす因果効果を実験した研究でもない。また、得られるのは近似SVPであり、厳密な最短ベクトルを常に求める結果ではない。LWEについても条件付きのパラメータ範囲で、あらゆるLWE変種を一括して解くとは述べていない。
ML-KEMが直ちに破られたわけではない
NISTが2024年にFIPS 203（DOI: 10.6028/NIST.FIPS.203）として標準化したML-KEMは、Module Learning With Errors（Module-LWE）の計算困難性と安全性が結び付いている。標準はML-KEM-512、ML-KEM-768、ML-KEM-1024という3つのパラメータ集合を定める。一方、Simonのプレプリントはplain LWEと格子問題への漸近的な含意を示す段階にあり、Module-LWEを使うML-KEMの各パラメータを破る具体的な攻撃へ落とし込んではいない。
実用性を判断する材料も不足している。論文には、標準パラメータを対象とした実行時間、必要な論理量子ビット数、回路深さ、誤り訂正の費用がない。「多項式時間」は入力が増えたときの伸び方を分類する言葉であり、現実の暗号鍵を短時間で破れるという意味ではない。固定の量子サンプル数も提示されておらず、実装ベンチマークとの比較はできない。
それでも、証明が検証されれば理論上の変化は大きい。DCPに対する多項式時間アルゴリズムの不在は、格子問題の量子計算量を考える上で長く残ってきた前提だったからだ。公開直後の単著プレプリントを定説の転覆とみなす段階ではない。暗号移行の判断を変えるには、専門家による証明の精査、独立した再導出、標準パラメータへ写した具体的な資源見積もりが揃う必要がある。
