2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@satokan3(Satoru Kanno)
in

格子暗号の今を正しく受け止めるための整理 ― Simon「A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem」を解説

2
Posted at

こんばんはっ！
GMOコネクト株式会社 執行役員CTO / GMOインターネットグループ株式会社 共同研究推進グループ 主席研究員 菅野哲（かんの さとる）でございます。

皆さん、査読前のプレプリント1本でヒヤリとしたことはありますか？
2026年8月6日、IACR の Cryptology ePrint Archive に1本の論文が公開されました。タイトルは「A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem」、整理番号は 2026/1591。著者は Daniel R. Simon、あの Simon のアルゴリズムの Simon 本人です！！（AWS 自身が量子技術の公式サイトで「Daniel Simon is a Principal Security Engineer in the AWS Cryptography group」として同一人物だと紹介しています）

Dihedral Coset Problem（以下 DCP）は原語のまま使います。強いて訳せば「二面体群の剰余類に関する問題」ですが（coset の数学の標準訳は「剰余類」であって「コセット」ではありません）、この訳語が日本語で使われている例を見つけられませんでした。中身は後ろの節で説明します。

この論文が正しければ、ML-KEM や ML-DSA が依拠する格子問題の困難性が量子計算機によって多項式時間で解けることになります。SNS では当日から「PQC が破られた」という反応が出ました。ただ、二次情報を読んでいるだけでは「どこまでが証明されていて、どこからが未証明なのか」がまるで分かりません。そこで論文の PDF を取得して16ページを通読し、参照先の Regev 論文と突き合わせて確認しました。本記事はその結果です。結論を先に書くと、慌てる必要はありませんが、大丈夫でもありません。危ないところと危なくないところが、報道されている切り分けとはかなり違っています。

本記事は2026年8月9日時点の公開情報（eprint.iacr.org/2026/1591 の PDF 本文、Oded Regev「Quantum Computation and Lattice Problems」（arXiv cs/0304005）の PDF 本文、および各種二次情報）に基づくスナップショットです。参照した文献は末尾にまとめました。対象論文は公開から3日しか経っておらず、査読も独立検証も受けていません。本文中「」で囲んだ英文引用はすべて一次資料の逐語であり、和訳は筆者によるものです。日本語の定訳が確認できなかった専門用語は、無理に訳さず原語のまま表記します（DCP、DSP、unique-SVP、pairwise independence、noise rate）。定訳が確認できたものは日本語で書きます（隠れ部分群問題、最短ベクトル問題、二面体群、剰余類、部分和問題）。「筆者の見立て」と明記した箇所は論文に書かれていない推論であり、一次資料による裏付けはありません。

公開からここまでの動き

日付 出来事
2026年7月31日 論文本文の日付（PDF の作成日時は8月1日 03:32 JST）
2026年8月3日 ePrint に投稿（Received）
2026年8月6日 ePrint で公開（Approved）。同日、複数の技術メディアが報道
2026年8月9日 本記事執筆時点。ePrint 上の改訂はなく、公開された反証も、著者による撤回も、独立検証の結果も出ていない（同日に ePrint を確認）

比較のために書いておくと、後述する2024年の類似事例では、公開から8日目にバグが発見されています。つまり今は、判断材料が出そろう前の期間にいます。

結論を3つに分ける

論文の主張は1つに見えて、実は証明の強度がまったく違う3層に分かれています。ここを混ぜると議論が壊れます。

第1層、DCP が量子多項式時間で解ける。これが論文の本体です。10ページを使って証明が書かれています。ただし要となる補題3本が「(Sketch)」と明記されています。

第2層、したがって √n·polylog(n) 近似の最短ベクトル問題（SVP）が解ける。これは Simon の新規結果ではなく、Regev（2002）と BKSW18（Brakerski、Kirshanova、Stehlé と Wen による2018年の論文「Learning With Errors and Extrapolated Dihedral Cosets」。以下この略号で呼びます）の既存の還元を組み合わせただけです。Regev の原論文に当たって確認したところ、この算術は整合していました。第1層が正しければ第2層は自動的に従います。

第3層、したがって ML-KEM 等の具体パラメータが破れる。ここが問題で、論文はこれをまったく証明していません。 該当箇所は最後の1文だけです。

Corollary. There exists a polynomial-time quantum algorithm that computes O(√n polylog(n))-factor approximations of SVP solutions, and solutions to LWE instances with α = O(√n polylog(n)).[9][7]

（系。SVP 解の O(√n polylog(n)) 倍近似と、α = O(√n polylog(n)) の LWE インスタンスの解を計算する量子多項式時間アルゴリズムが存在する。）

参照されている [9] と [7] を巻末で引くと、こうなっています。

[7] D. Micciancio. Personal Communication.
[9] S. Ragavan. Personal Communication.

どちらも Personal Communication、日本語でいう私信です。 論文や報告書ではなく、著者が個人的なやり取りで得た内容を指します。読者が当たれる資料は存在せず、導出も書かれていません。

ただし、この Corollary から ML-KEM までの道すじが丸ごと私信に頼っているわけではありません。鎖の各段は、査読を通った論文ですでに埋まっています。私信2件が受け持っているのは、その鎖を通したときに出てくる具体的な数字のほうです。段ごとに何が支えているのかは、後ろの節で表にして示します。

先にサマリー：正しかった場合、何が効くのか

技術的な中身に入る前に、影響範囲だけ先に出しておきます。論文が証明しているのは「DCP が多項式時間」までで、そこから先は暗号方式ごとに事情がまったく違います。 一括りに「PQC が破られる」と言える状態ではありません。

対象 もし正しければどうなるか そう言える根拠の強さ
CSIDH / CSI-FiSh 等の可換群作用型の同種写像暗号 条件付き。別途検証が要る 弱い。CSIDH が依拠するのは可換群作用の隠れシフト問題で、Simon が解いた N = 2^n の DCP とは別物。CSIDH の類群は位数が奇数であり、両者がつながるかは論文が扱っていない。後述
FHE（BGV / BFV / CKKS / TFHE） 射程内の可能性が高い。ただし未確定 中。modulus/noise 比が大きいほど不利という読み自体が、後述の α の解釈（筆者の見立て）に乗っている。方式ごとの誤差分布やモジュラス鎖までは見ていない
ML-KEM (FIPS 203) / ML-DSA (FIPS 204) 条件付き。論文からは判定不能 中。Simon の結果から ML-KEM まで6段あり、2段目以降は査読済みの論文で埋まっている。かかっているのは1段目（Simon 自身の証明）と、閾値の具体値を出す私信2件。後述
FrodoKEM 同上（非構造 LWE で最も素直に該当しうる） 同上
FN-DSA / Falcon、NTRU LWE 経路では非該当。uSVP 経路は要別途検証 未確定。NTRU 格子のギャップが √n·polylog(n) を超えるかは自明ではない
SLH-DSA、XMSS / LMS（ハッシュベース署名） 無傷 確定。格子問題と無関係
HQC、Classic McEliece（符号ベース） 無傷 確定。格子問題と無関係

そのうえで、時間軸も分けて考える必要があります。正しければ安全性の仮定は即座に終わりますが、動いているシステムへの攻撃は当面ゼロです。 論文には回路図も、必要な論理量子ビット数も、誤り訂正コストの見積もりも書かれていません。影響が及ぶのは移行計画のタイムラインで、今日の通信ではありません。

なぜこういう切り分けになるのかを、以下で順に説明します。

前提：DCP と格子はどうつながっているのか

そもそもなぜ二面体群の話が格子暗号に効くのか、ここを押さえないと騒ぎの構造が見えません。

DSP（Dihedral Subgroup Problem）は、二面体群（正N角形の対称性のなす群）における隠れ部分群問題です。なお DSP という呼び方は Simon 論文のもので、英語でも通常は dihedral hidden subgroup problem と呼びます。以下に示す形への定式化は Regev によるもので、DCP という問題そのものも Regev が定義しました。Mark Ettinger と Peter Høyer の結果（「On Quantum Algorithms for Noncommutative Hidden Subgroups」、2000年）により、部分群の位数が2の場合に帰着でき、標準的なサンプリング法を適用すると次の形になります。

(|0, x⟩ + |1, x + d mod N⟩) / √2 という重ね合わせのサンプルが何個でも手に入る。
x はサンプルごとに任意、d は全サンプル共通。d を求めよ。

ここで重要な事実が2つあります。1つ目、Ettinger–Høyer は、多項式個のサンプルがあれば情報理論的には d が決まることを示しています。つまり足りないのは情報ではなく、その情報から d を取り出す効率的な手続きだけです。この点は Regev 論文にも明記されています。

Ettinger and Høyer [6] showed that one can obtain sufficient statistical information about the hidden subgroup with only a polynomial number of queries. However, there is no efficient algorithm that solves the HSP using this information.

（Ettinger と Høyer は、隠れ部分群についての十分な統計的情報が多項式個のクエリだけで得られることを示した。しかし、この情報を使って HSP を解く効率的なアルゴリズムは存在しない。）

多項式時間解法は、何ら理論的障壁に抵触しません。 今回の主張を一目で無理だと切り捨てられない理由の1つが、ここにあります。

2つ目、DCP（Dihedral Coset Problem）は上の DSP に「一定確率でサンプルが壊れている」という条件を加えたものです。Regev（2002）の Theorem 1.1 がこう述べます。

Theorem 1.1 If there exists a solution to the dihedral coset problem with failure parameter f then there exists a quantum algorithm that solves the Θ(n^{1/2+2f})-unique-SVP.

（定理1.1 failure parameter が f の Dihedral Coset Problem の解法が存在するならば、Θ(n^{1/2+2f})-unique-SVP を解く量子アルゴリズムが存在する。）

γ-unique-SVP は、最短ベクトルが2番目に短いベクトルより γ 倍以上短いと保証された格子で、その最短ベクトルを求める問題です。γ が大きいほど飛び抜けて短い1本が見つけやすくなるので、問題としては易しくなります。したがって γ が小さいまま解けるほど強い結果になります。

failure parameter f は「各サンプルが確率 (1/log N)^f で壊れる」という意味です。つまり、壊れたサンプルへの耐性が高いほど、得られる SVP の近似率が良くなるという交換関係になっています。Regev 自身が示したのは「部分和オラクルがあれば f=1 の DCP が解ける」という条件付きの還元で、そこから得られる近似率は Θ(n^2.5) でした。オラクルなしで DCP が解けるとは言っていません。

Simon の主張は「誤りサンプル率 1/O(log n) まで耐えられる」です。ここに BKSW18 の改良還元を組み合わせると、近似率が √n·polylog(n) まで下がります。Simon 論文は BKSW18 の改良点をこう説明しています。

This quadratic dimension increase was later removed in an improved reduction from LWE presented by Brakerski, Kirshanova, Stehlé and Wen [3].

（この次元の2乗化は、Brakerski、Kirshanova、Stehlé、Wen による LWE からの改良された還元によって、後に取り除かれた。）

「次元の2乗化」という言い方はやや紛らわしいので補足します。BKSW18 本文に当たると、実際に膨らむのは次元ではなくモジュラスでした。

m-dimensional DCP can be reduced to 1-dimensional DCP, with a significant modulus increase: the resulting modulus N is 2^{O(m²)}.

（m 次元の DCP は1次元の DCP に還元できるが、モジュラスが大きく増加する。結果として得られるモジュラス N は 2^{O(m²)} になる。）

そして BKSW18 が改良したのはここです。

Third, and most importantly, the DCP modulus N is only q and not 2^{O(m²)}. ... This improvement results in a much tighter reduction.

（第三に、そして最も重要な点として、DCP のモジュラス N は q だけであって 2^{O(m²)} ではない。……この改良によって、はるかにタイトな還元が得られる。）

つまり 2^{O(m²)} の指数にあった m² が消えて N = q になった、というのが改良の中身です。Simon 論文の「次元の2乗化」は、この指数部の m² を指した表現と読めます。

論文本文の記述と Regev の定理を突き合わせると、この計算は合っています。

そして √n·polylog(n) という数字にはもう1つ意味があります。Dorit Aharonov と Oded Regev の「Lattice Problems in NP ∩ coNP」（2005年）により、√n 近似の SVP と CVP は NP ∩ coNP に属しており、NP困難ではありません。Simon が主張している近似率は、複雑性理論が許す範囲のちょうど内側に置かれています。 主張が P = NP のような不可能事に化けないよう、意図的にこの位置を選んでいるように読めます。

何が新しいのか

Regev の多項式時間 DSP アルゴリズムには、部分和オラクルという強力すぎる前提が1つだけ残っていました。使い道は限定的で、重ね合わせの中に散らばったビット b_i を可逆に消去する（計算を巻き戻し、痕跡を残さずに消す）ためだけに使われます。ここが20年以上ボトルネックでした。

Simon の発想は、消すのをやめて、消さなくても済む形に持ち込むことです。

  1. Q = k·n^{c+1} 個のサンプルを取り、部分和 z = Σ b_i y_i の下位 n−1 ビットを測定する。最上位ビット h に、求めたい d の最下位ビット d_n が位相として乗る（ここまで Regev と同じ）
  2. b_i を c·log n 個ずつのグループに分け、各グループの部分和の上位 log n ビットを計算しておく
  3. b_i をアダマール変換して測定してしまう。測定結果が全ゼロだったグループを集合 A、それ以外を集合 B に振り分ける。A に属するグループには余計な位相 (−1)^(ϕ·D) が乗らない
  4. A だけから新しい最上位ビット h* を組み立て、h' = h ⊕ h* を測定して、d_n の符号情報を h から h* へ移す
  5. B の寄与は h*=0 と h*=1 で同一なので、括り出して無視する

この論文で最も見事なのは、5 を保証する Lemma 2 です。 z* の最上位ビットを反転させると h も連動して反転する（h' は測定済みで固定されているため）ので、制約式 z* + Σ_B b_i y_i = z' + 2^(n−1)·h が mod 2^n で保存されます。結果として集合 B は集合として文字通り一致し、係数も一致します。

そして Lemma 2 は、この論文で唯一 (Sketch) が付いていない完全証明の補題です。 短く、追いやすく、正しく見えます。

証明の状態を一覧にする

ここがこの記事で最も伝えたい表です。

主張 証明の状態
Theorem（本体） 骨格は記述あり
Lemma 1（集合 A に n/log n グループを確保できる） (Sketch)
Lemma 2（B の寄与が h* に依らず一致する） 完全証明。健全に見える
Lemma 3（well-behaved 性と振幅の上界） (Sketch)
Corollary to Lemma 3 (Sketch)
Lemma 4（A 側のカウントがほぼ一様） (Sketch)
最終 Corollary（SVP / LWE のパラメータ） 証明なし。私信2件のみ

Lemma 2 が片付いたことで、残る問題は1点に絞られています。集合 A 側の状態数が h*=0 と h*=1 で等しいか。 これを担当するのが Lemma 4 で、そこは Sketch です。つまり論文の成否は、Sketch のまま残された補題3本に丸ごと乗っています。

気になった箇所

以下は筆者の読みであり、反証ではありません。誤りを見つけたという主張ではなく、第三者に検証してほしい箇所として挙げます。

なお、この節には当初もう1件、「Lemma 3 の振幅の上界は正規化のせいで自明になっている」という指摘を書いていました。これは筆者の誤読だったので削除しました。 α_z* は最終状態の直交基底成分ではなく、z* で分割した非直交な部分和です（論文の最終状態のケットは |h*, h'⟩ だけで、z* は残っていません）。互いに打ち消し合う部分和の絶対値は1を超え得るので、正規化から自明な上界は出ません。

pairwise independence と正規性

論文の概要節に、著者自身が仮定を明記している箇所があります。

(We're assuming here that the amplitudes associated with each z* value are "well-behaved" enough—that is, that they aren't so huge and mutually canceling—that the tiny differences among amplitudes associated with the ϕA state-portions for different z* values aren't unduly magnified. Fortunately, the pairwise independence of the phases of states over possible measured values of the Hadamard-transformed bits bi ensures that these per-z* amplitudes are roughly normally distributed, and hence within reasonable bounds with high probability.)

（ここでは、各 z* に対応する振幅が十分に「行儀が良い」こと、すなわち巨大かつ相互に打ち消し合うほどではなく、異なる z* に対する ϕA 状態部分の振幅間のわずかな差が過度に増幅されないことを仮定している。幸いにも、アダマール変換されたビット bi の測定値にわたる状態の位相の pairwise independence が、これら z* ごとの振幅がほぼ正規分布であり、したがって高い確率で妥当な範囲に収まることを保証する。）

pairwise independence（どの2つを取り出しても独立、という性質）から出るのは2次モーメント、すなわちチェビシェフの不等式による裾の評価までで、正規性は出ません。 実際の Lemma 3 と Lemma 4 の証明ではチェビシェフを使っており運用としては正しいのですが、この一文は根拠のない格上げになっています。

引っかかるのは、次の点です。取り出したい信号は符号がほぼランダムな 2^n 項の和なので、キャンセルを込みで √(2^n) 程度のオーダーしかありません。一方で誤差は絶対値の和、すなわち 2^n のオーダーで評価されています。 この √(2^n) の開きを、Lemma 3 の well-behaved 性と振幅の上界で抑え込むというのが論文の筋書きです。抑え込めているかどうかは、相殺の効き方を独立に評価しないと決まりません。ここは Sketch のままなので、追いかけようがありませんでした。

測定結果 D の分布の扱い

Lemma 3 の証明は「D の選び方にわたって、任意の状態は等頻度で正負に振り分けられる」として位相を pairwise independent に扱います。しかし D は一様乱数ではなく、いま解析対象にしている干渉パターン自身が決めた Born 確率で得られた測定値です。 論文は測定確率で重み付けする箇所を設けてはいますが、この種のモデル化は隠れた依存性が紛れ込む典型的な場所です。Lemma 1 の「（Y の選び方にわたって）和は正にも負にも同じ確率でなる」も、証明ではなく対称性の主張にとどまっています。

2024年に何が起きたか

2024年4月10日、Yilei Chen 氏が「Quantum Algorithms for Lattice Problems（格子問題に対する量子アルゴリズム）」（ePrint 2024/555）を公開しました。多項式の modulus/noise 比を持つ LWE を量子多項式時間で解くという主張で、当時も大きな騒ぎになりました。

8日後の4月18日、Hongxun Wu 氏と Thomas Vidick 氏が独立に、アルゴリズムの Step 9 に誤りを発見します。Chen 氏は論文を撤回せず、abstract の冒頭に注記を足した改訂版を出しました。

Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.

（多項式の modulus-noise 比を持つ LWE を多項式時間の量子アルゴリズムで解くという主張は、もはや成立しない。論文の残りはそのままにしておく（Step 8 のある操作について説明を追加した）。Complex Gaussian や windowed QFT といったアイデアが、量子計算の他の応用先を見つけるか、あるいは別の方法で LWE に取り組む助けになることを期待して。）

壊れたのは量子状態の振幅の見積もりです。

この件を失敗例として引き合いに出すのは、たぶん正しくありません。公開から8日で誤りが見つかり、著者はそれを論文の冒頭に自分で書きました。しかも論文を消さずに残し、使えるアイデアは持っていってほしいと添えています。査読前に公開する、短期間で第三者が検証する、誤りが出たら著者が明示する。この一連の流れが、いちばん良く機能した例です。今回の Simon 論文は、その2番目、第三者の検証を待っている段階にあります。 慌てるにも安心するにも早い、というのはそういう意味です。

技術的には、今回 Simon 論文で気になった箇所は、これと同じクラスの誤りが起こりうる場所です。そして今回の論文の謝辞には Thomas Vidick の名前があります。 Micciancio、Vaikuntanathan、Ragavan、Menda と並んで、格子と量子の第一線が投稿前に目を通しています。これは論文の信頼度を上げる材料である一方、それでも「Preliminary Draft」と題して Sketch のまま公開されているという事実のほうを、重く見ています。

影響範囲の読み解き方

冒頭のサマリーで示した表が、なぜあの形になるのかを説明します。ここが報道と最も食い違うところです。

騒ぎの中心は ML-KEM ですが、報道が触れていない対象が2つあります。CSIDH と FHE です。ただしどちらも、当初この記事が書いていたほど確実ではありませんでした。外部レビューの指摘を受けて弱めています。

CSIDH は NIST 標準ではありませんが、格子が危なくなったときの代替候補として扱われてきた経緯があります。二面体群まわりの問題が基盤なので直撃するはずだ、と最初は書きました。しかし CSIDH が依拠するのは可換群作用の隠れシフト問題であって、Simon が解いた DCP とは別物です。そして Simon の証明にはこうあります。

For simplicity, let N = 2^n, and assume all arithmetic operations and relations involving states, amplitudes and phases are (mod N).

（簡単のため N = 2^n とし、状態と振幅、位相にかかわる演算と関係はすべて mod N とする。）

アルゴリズム全体が Z_{2^n} 上のビット操作として組まれています。一方 CSIDH が使うイデアル類群は位数が奇数で、そもそも構造が合いません。「簡単のため」と書かれている以上、一般化の余地はあるのかもしれませんが、論文はそれを示していません。 ここは別途検証が要ります。

FHE についても、modulus/noise 比が大きいから射程内、と書いていました。この読みは、後述する α の解釈に丸ごと乗っています。そしてその解釈は筆者の見立てです。見立ての上に「確実」を積むのは筋が通らないので、こちらも未確定に下げます。

一方で ML-KEM については、報道が断定しているほどの根拠が論文にありません。念のため書いておくと、α = √n polylog(n) という表記は、LWE の α（noise rate。ノイズの大きさを modulus に対する比で表したもの）が定義上1未満であることを考えると、そのままでは値として成立しません。逆数（modulus/noise 比）の意味に読むのが自然です。その読みを採ると、ML-KEM の q/σ ≈ 2700〜3300 は n=768 における √n·polylog(n) と同じ桁に来ます。ただしこれは筆者の見立てであって、論文の主張ではありません。 polylog の底も定数も書かれていない以上、ここは Corollary が証明された形で出てくるまで確定しません。なお ML-KEM-768 の 768 は、ring degree 256 に module rank 3 を掛けた値です。LWE インスタンスとして見たときの格子の次元がこれにあたります。

MLWE から EDCP への査読済みの還元

ここは当初書き落としていた点で、外部レビューの指摘を受けて追記します。

2026年1月30日、Weiqiang Wen と Jinwei Zheng が「Module Learning With Errors and Structured Extrapolated Dihedral Cosets」（ePrint 2026/155）を公開しています。ePrint 上の表示は「A major revision of an IACR publication in CRYPTO 2026」で、査読を通った論文です。

Our equivalence result holds for MLWE defined over power-of-two cyclotomic rings with constant module rank, a setting of particular relevance in cryptographic applications. Moreover, we present a reduction from IP-M-EDCP to EDCP.

（我々の等価性の結果は、2冪円分環上で定義されモジュールランクが定数である MLWE について成立する。これは暗号応用において特に重要な設定である。さらに我々は IP-M-EDCP から EDCP への還元を与える。）

2冪円分環かつモジュールランクが定数という条件は、ML-KEM と ML-DSA の設定そのものです。つまり MLWE から EDCP までの経路は、私信ではなく査読済みの論文として存在します。

ただしこの経路にも限定条件が付きます。Wen–Zheng が示した等価性は MLWE の search 版についてのもので、著者自身が同論文の Open Problems 節でこう書いています。

Our reduction between MLWE and IP-M-EDCP has heavily relied on the Rényi divergence, which is particularly suitable for the search variants but does not naturally extend to decision variants. A possible workaround is to first establish an equivalence between search and decision variants of IP-M-EDCP, then combine this with the known equivalence for MLWE, as well as our results, to bridge the decision variants.

（MLWE と IP-M-EDCP の間の我々の還元は Rényi ダイバージェンスに大きく依存しており、これは search 版には特に適しているが decision 版には自然には拡張しない。回避策として考えられるのは、まず IP-M-EDCP の search 版と decision 版の等価性を確立し、それを MLWE についての既知の等価性および我々の結果と組み合わせて、decision 版どうしを橋渡しすることである。）

ML-KEM の安全性証明が依拠しているのは decision 版のほうです。その橋渡しは、著者自身が未解決問題として挙げています。なお攻撃という観点だけで言えば、search 版が解ければ秘密が求まるので目的は達せられます（この一文は解釈です）。

DCP と EDCP のつなぎ目

Simon が解いたと主張しているのは DCP です。上の経路が降りてくる先は EDCP です。この2つは別の問題で、BKSW18 の本文にこう書かれています。

Note that DCP is the special case of EDCP for n = 1 and f being the indicator function of {0, 1}.

（DCP は、n = 1 かつ f が {0, 1} の指示関数である場合の EDCP の特別な場合であることに注意せよ。）

EDCP は重ね合わせの幅を M 段に広げた一般形で、DCP はその M = 2 の場合です。そして BKSW18 の Theorem 1 で LWE に対応するのは M = poly(n log q)/α の EDCP であって、M = 2 ではありません。

では M = 2 の解法から、M の大きい EDCP へは行けないのか。行けます。同じ BKSW18 が1文だけ触れています。

It is not hard to see that, at least so long as M is polynomial, a solution to DCP implies a solution to EDCP^ℓ_{n,N,M}.

（少なくとも M が多項式である限り、DCP の解法が EDCP^ℓ_{n,N,M} の解法を導くことは、見て取るのが難しくない。）

暗号で使うパラメータでは 1/α が多項式なので、M = poly(n log q)/α も多項式です。したがって、DCP が解ければ EDCP も解けます。

ここは筆者が一度間違えた場所なので、経緯を残しておきます。当初この記事は、この段を「どちらの論文にも書かれていない空白」と書いていました。BKSW18 の「We conjecture that G-EDCP is strictly easier than DCP.」（G-EDCP は DCP より厳密に易しいと予想する）という一文を、DCP から EDCP へ行けない根拠として読んでいたためです。含意の向きが逆でした。 易しいというのは、難しいほうが解ければ易しいほうも解ける、という意味です。BKSW18 の上の1文は、まさにそれを述べています。

結局どの段が埋まっていて、どの段が空いているのか

ここまでの話を、Simon のアルゴリズムから ML-KEM まで順に並べます。攻撃する側から見て、下から上へ登っていく形です。

EDCP には変種があるので、そこも段として分けます。BKSW18 は M 段の一様な重みを U-EDCP、ガウス型の重みを G-EDCP と呼び分けていて、上で引いた「DCP が解ければ EDCP も解ける」は U-EDCP のほうです。一方 Wen–Zheng が還元する先は G-EDCP です。両者は BKSW18 が繋いでいます。

We show that G-EDCP and U-EDCP are equivalent up to small parameter losses.

（G-EDCP と U-EDCP は、小さなパラメータ損失を除いて等価であることを示す。）

# この段を越えると 何がそれを支えているか 状態
1 DCP（M = 2）が解ける Simon 論文の本体、10ページ ここだけが未確定。補題3本が Sketch
2 U-EDCP（M が多項式の範囲）が解ける BKSW18 の1文 査読済み（PKC 2018）
3 G-EDCP が解ける BKSW18、U-EDCP と G-EDCP の等価性 査読済み（PKC 2018）
4 IP-M-EDCP が解ける Wen–Zheng、IP-M-EDCP から G-EDCP への還元 査読済み（CRYPTO 2026）
5 search MLWE が解ける（＝秘密が求まる） Wen–Zheng、MLWE と IP-M-EDCP の等価性 査読済み。ただし search 版に限る
6 ML-KEM が破れる 秘密が求まれば復号できる 段としては自明

2段目から6段目まで、鎖は公開された査読済みの論文で埋まっています。かかっているのは1段目、Simon 自身の主張が通るかどうかの一点です。

では私信2件は何を担っているのか。最終 Corollary が述べているのは近似率と α の具体的な値でした。Simon の誤りサンプル耐性、Regev の Theorem 1.1、BKSW18 のパラメータ損失を順に通したときに、最終的にどの数字が出るか。その計算が私信2件の担当範囲だと読むのが素直です。鎖が存在するかどうかではなく、鎖を通した後に出てくる数字のほうです。

なお EDCP そのものを直接攻める研究も進んでいます。2025年に Shi Bai、Hansraj Jangir、Elena Kirshanova、Tran Ngo、William Youmans が「A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli」（ePrint 2025/1046、CRYPTO 2025）を出しています。BKSW18 の著者の1人が入っていて、2冪という設定も同じです。ただし著者自身が abstract で釘を刺しています。

We stress that our algorithm does not affect the security of LWE with standard parameters, as the reduction from standard LWE to EDCP limits the number of samples to be polynomial.

（強調しておくが、我々のアルゴリズムは標準的なパラメータの LWE の安全性に影響しない。標準的な LWE から EDCP への還元では、サンプル数が多項式に制限されるからである。）

必要なのが準多項式個のサンプル、還元が許すのが多項式個。EDCP を直接攻めるほうは、まだ届いていません。

ML-KEM の安全性証明が乗っているのは5段目の decision 版のほうで、そこは前述のとおり著者自身が未解決問題に挙げています。ただし攻撃としては search 版で秘密が求まれば足ります。

まとめると、鎖そのものは公開された論文で説明がつきます。 全体がかかっているのは1段目、つまり Sketch のまま置かれた補題3本が通るかどうかです。この記事で証明の状態を一覧にしたのは、そこが全部を決めるからです。

サンプル数 n^13

サンプル数は Q = k·n^(c+1) で、Lemma 1 が k > c、Lemma 4 が c ≥ 12 を要求します。したがって d の1ビットを復元するのに k·n^13（ただし k > 12）個のサンプルが要る、という計算になります。さらにステップ6で望みの測定結果が出る確率が 2/n、他にも定数確率の関門が複数あり、その上で d の n ビットを再帰的に剥がしていきます。

n=768 を入れると 768^13 ≈ 2^124.6 で、k > 12 の係数まで含めると 2^128 を超えます。

これは正しさへの反論にはなりません。多項式は多項式です。 ただし含意は2つに分かれます。正しければ安全性の仮定としては即座に終わりますが、具体的な攻撃としては当面ゼロです。論文には回路図も、論理量子ビット数も、回路深さも、誤り訂正コストの見積もりも一切ありません。

歴史的には、この種のアルゴリズムは後から定数と次数が削られていくものなので、「n^13 だから安心」と考えるのは適切ではありません。しかし「明日 ML-KEM の通信が復号される」という話でもありません。影響が及ぶのは移行計画のタイムラインで、いま動いているシステムではありません。

何を見て判断するか

今後の判断材料はこれです。

その前に1点。著者は完全版を出すと明言していません。 本文にも謝辞にも「full version」「forthcoming」の類の予告はなく、ePrint 上の版も本記事執筆時点で1つだけです（2026年8月3日 received、8月6日 approved、8月9日時点で改訂なし）。ただしタイトルに自ら [Preliminary Draft] と付け、補題に (Sketch) と明記している以上、完全版を意図していると読むのが自然です。前例の Chen 2024/555 は撤回ではなく改訂で瑕疵を明記する形を取ったので、改訂が出るとしても、完全な証明が付いてくるとは限りません。

  • Lemma 1、3、4 の Sketch が完全証明として出てくるか。とくに Lemma 3 の well-behaved 性、つまり相殺の効き方の評価が埋まるか
  • 私信2件（Micciancio 氏、Ragavan 氏）が論文または独立のノートとして公開されるか。これが出ない限り「LWE が破れた」とは言えません
  • Regev、Kuperberg、Peikert、Vidick、Wu といった面々からの公開コメント。および pqc-forum のスレッド
  • 小規模な数値シミュレーション。c を小さく取った縮約版を n=8〜16 程度で回し、d_n の測定バイアスが 1/2 から有意にずれるかを見る。理論の可否より先に、これが最速の判定材料になる可能性があります

Chen 2024 のケースが8日で決着したことを踏まえると、数日から数週のスパンで何らかの結論が出るはずです。

今日やること、やらないこと

やらないこと。ML-KEM の展開を止めることです。 攻撃は存在せず、それを走らせる量子計算機も存在しません。止める側のコストのほうが確実に大きいです。

やることは3つです。

  1. ハイブリッド構成（例: X25519 + ML-KEM）を維持する。今回の件は、ハイブリッド運用という選択の正当化そのものです
  2. 暗号アジリティの優先度を上げる。格子だけに依存している箇所を集中リスクとして棚卸しし、格子以外の代替手段（ハッシュベース署名、HQC）が制度的にも実装的にも使える状態か確認しておく
  3. FHE や CSIDH を製品に組み込む計画があるなら、この件を監視対象に入れておく。報道は ML-KEM ばかり扱いますが、この2つは誰も追っていません

まとめ

  • 論文の第1層（DCP が多項式時間）は10ページの証明があるが、要となる補題3本が Sketch
  • 第2層（√n·polylog(n) 近似の SVP）は既存の還元の組み合わせで、算術は Regev 原論文と照合して整合
  • 第3層（ML-KEM 等の具体パラメータ）は、論文としては未証明。ただし DCP から ML-KEM までの鎖自体は査読済みの論文で埋まっており、私信2件が担うのは通した後の数字
  • 最も気になったのは Lemma 3 の相殺の評価で、2024年に同種の主張が取り下げられたのと同じクラスの箇所
  • 報道が触れていない対象として CSIDH と FHE がある。ただしどちらも未確定で、当初書いていたほど確実ではない
  • 実務上、今日変えるべきことはない。ハイブリッドと暗号アジリティという既定路線が、そのまま正解

この主張は一目で無理と言えるものではありません。理論的障壁にも複雑性の壁にも抵触せず、Lemma 2 は綺麗で、著者は Simon のアルゴリズムの Simon です。真面目に検証されるべき論文だと考えています。

そのうえで筆者は否定寄りに見ています。理由は2つです。成否を担う補題3本が Sketch のまま置かれていること。そして引っかかった箇所が、2024年に取り下げられた主張と同じクラス、つまり量子状態の振幅の相殺の見積もりだということ。ただし確信度は低く、数字にできるほどの根拠はありません。 論文を否定する材料を持っているわけではなく、肯定する材料がまだ出ていない、というだけです。

数日から数週で答えが出ます。それまでは、慌てず、しかし目は離さずにいましょう。

参照した文献

この記事の主張はすべて以下に当たって確認しています。丸数字は付けず、本文で言及した順に並べます。

評価対象

  • Daniel R. Simon, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem [Preliminary Draft]", Cryptology ePrint Archive, Paper 2026/1591, 2026年8月
    https://eprint.iacr.org/2026/1591
    ePrint は同じ URL で差し替えが起こります。読んだのは SHA-256 が e62fad01… で始まる版（PDF 作成日時 2026年8月1日 03:32 JST）です。

PDF 本文まで当たって確認したもの

  • Oded Regev, "Quantum Computation and Lattice Problems", FOCS 2002 / SIAM J. Comput. 33(3):738–760, 2004
    https://arxiv.org/abs/cs/0304005
    （Theorem 1.1 と DCP の failure parameter の定義を、ここから直接引用しています）

  • Zvika Brakerski, Elena Kirshanova, Damien Stehlé, Weiqiang Wen, "Learning With Errors and Extrapolated Dihedral Cosets", PKC 2018（本記事の BKSW18）
    https://arxiv.org/abs/1710.08223
    （DCP と EDCP の関係、および Theorem 1 の M ≈ 1/α をここから直接引用しています）

  • Weiqiang Wen, Jinwei Zheng, "Module Learning With Errors and Structured Extrapolated Dihedral Cosets", CRYPTO 2026 / Cryptology ePrint Archive, Paper 2026/155
    https://eprint.iacr.org/2026/155
    （abstract と、同論文の Open Problems 節をここから直接引用しています）

本文で言及したが、該当箇所または要旨しか確認していないもの

二次情報（裏取り前提で参照を実施）

最後に、GMOコネクトでは研究開発や国際標準化に関する支援や技術検証をはじめ、幅広い支援を行っておりますので、何かありましたらお気軽にお問合せください。

お問合せ: https://gmo-connect.jp/contactus/

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?