暗号解読の量子アルゴリズムとは？ショアのアルゴリズムと格子暗号の現在地
「量子コンピュータで暗号が全部破られる」は正確ではありません。何がすでに理論上破られていて、何がまだ破られていないのかを整理します。
現在の状況: 何が破られていて、何が破られていないか
本記事執筆時点(2026年)で、実用規模の暗号(RSA-2048やECC-256相当)を実際に解読できるだけの 誤り耐性量子コンピュータは、まだ実現していません。NISQ(ノイズあり中規模量子)デバイスは 急速に発展していますが、ショアのアルゴリズムを実用的な鍵長に対して実行するには、 論理量子ビット換算で数百万〜数千万ゲート級のエラー訂正が必要とされており、依然として 大きな隔たりがあります。ただし、アルゴリズムの理論上の攻略可能性と 今それを実行できるハードウェアがあるかは別の話です。以下では前者、 つまり「量子コンピュータが十分に大きければ何が起きるか」を扱います。
ショアのアルゴリズムと量子位相推定
ショアのアルゴリズム(1994年、Peter Shor)は、素因数分解と離散対数問題の両方を、 古典コンピュータでは実現不可能な多項式時間で解く量子アルゴリズムです。核となる部品は 量子位相推定(Quantum Phase Estimation, QPE)です。
大まかな流れは次の通りです。素因数分解したい数をNとすると、ランダムに選んだ
aに対してf(x) = a^x mod Nという関数の周期(位数)
rを求める問題に帰着できます。この周期rを求める部分に量子位相推定を
使うのがショアのアルゴリズムの核心です。fを計算するユニタリ変換の固有値の位相を、
量子フーリエ変換を使って読み出すことで、rに関する情報を(重ね合わせを使って)
1回の量子計算でまとめて取得できます。古典コンピュータではrを求めるのに
指数時間かかるのに対し、量子位相推定を使えば多項式時間で求まります。
この「周期を求める」という構造は、素因数分解(RSA)だけでなく、有限体上の離散対数問題(DH)、 楕円曲線上の離散対数問題(ECC/ECDSA/ECDHE)にも共通しています。いずれも「群の中の周期構造を 見つける」という同じ枠組みに落とし込めるため、ショアのアルゴリズムの変種1つで、 RSA・DH・ECCのすべてが理論上は多項式時間で攻略可能になります。これが、 「耐量子暗号(Post-Quantum Cryptography)への移行」が叫ばれている根本的な理由です。
格子暗号はなぜ(今のところ)無事なのか
一方、NISTが耐量子暗号の標準として選定したML-KEM(Kyber)・ML-DSA(Dilithium)などの 格子暗号は、最短ベクトル問題(SVP)やLearning With Errors(LWE)といった 問題の困難性に安全性の根拠を置いています。これらの問題には、ショアのアルゴリズムのような 「周期構造」がありません。RSA・DH・ECCが破られるのは、その困難性の根拠が本質的に 群の中の(隠れた)周期性・アーベル群の構造に依存しているためで、量子位相推定は まさにそうした周期構造を見つけるのが得意なアルゴリズムです。格子問題は、現状そのような 代数的構造につけ込む方法が知られていません。
ただし「知られていない」ことは「存在しない」ことの証明ではありません。実際に2026年8月、 AWS(Amazon Web Services)の暗号研究グループに所属するDaniel R. Simon氏が、 二面体コセット問題(Dihedral Coset Problem, DCP)に対する多項式時間量子 アルゴリズムを主張する論文を IACR ePrint Archiveに投稿し、大きな注目を 集めました。DCPは、過去20年ほどの研究の蓄積により格子問題(近似最短ベクトル問題やLearning With Errors)との還元関係が知られているため、もしこの主張が正しければ格子暗号の安全性根拠の一部にも 影響が及びうる、という点で注目度の高い発表でした。
しかし発表から間もない2026年8月15日時点で、この論文には重大な誤りが指摘され、主張されていた アルゴリズムは(少なくとも多項式時間では)機能しないことが判明しています。NIST標準の格子暗号 (ML-KEM/ML-DSA)などが実際に攻略されたわけではなく、費用計算済みの攻撃が示されたわけでも ありません。「画期的な主張が査読・追試の過程で撤回される」という、この分野でたびたび起きる パターンの、もっとも新しい実例です。
まとめ
- ショアのアルゴリズムは、量子位相推定を用いて周期(位数)を多項式時間で求めることで、RSA・DH・ECCすべてを理論上攻略できる
- この攻略可能性は、これらの問題がアーベル群の周期構造に依拠していることに起因する
- 格子暗号(SVP/LWE)にはそうした周期構造がなく、量子位相推定の適用対象になっていない
- 2026年8月のAWS Simon氏によるDCP多項式時間アルゴリズムの主張は、同月中に誤りが指摘され撤回に至った
- ただし研究は現在進行形であり、査読済みの一次情報を継続的に確認することが重要
- 実用規模のRSA/ECCを解読できる誤り耐性量子コンピュータは、本記事執筆時点でまだ存在しない