耐量子暗号 — ショアの脅威に備える格子の砦

十分に大きな量子コンピュータが完成すると、RSA も楕円曲線暗号も多項式時間で崩壊します。それを見越してインターネットはすでに静かな引っ越し — 耐量子暗号（PQC: Post-Quantum Cryptography）への移行 — を始めています。何が壊れ、何が生き残り、格子という新しい砦はなぜ硬いのか。2026年時点の現在地まで含めて動かしながら理解します。

1. ショアの脅威 — 何が壊れ、何が生き残るか

現代の公開鍵暗号はすべて、素因数分解や（楕円曲線）離散対数といった「一方向にしか計算できない」数学の問題に立っています。ところが1994年にショアが示したアルゴリズム（量子コンピュータ編・第10回）は、誤り訂正された大規模量子コンピュータ — CRQC（Cryptographically Relevant Quantum Computer）— さえあれば、この両方を多項式時間で解いてしまいます。つまり RSA・DH・楕円曲線暗号は鍵長を多少伸ばしても助かりません。

一方、AES のような共通鍵暗号やハッシュ関数に対して知られている量子攻撃はグローバー探索による平方根の加速までです。理論上 AES-128 の全数探索は 264 回相当に縮みますが、逐次実行が必要で並列化が効かないため現実的脅威は限定的で、鍵長・出力長を増やせば耐えられます（だから推奨は AES-256、長期用途は SHA-384）。ここに公開鍵系と共通鍵系の決定的な運命の分かれ目があります。

CRQC はまだ存在しません。RSA-2048 の解読に必要な規模の試算は年々下がっており（2019年の試算で約2000万物理量子ビット・8時間 → 2025年には「100万個未満のノイズあり量子ビットで1週間以内」という試算も）、誤り訂正の実験も進展していますが、それでも現状の実機からはまだ遠い。問題は「いつ来るか」が不確実な帯でしか言えないこと、そして脅威が到来を待ってくれないことです。

ショアの脅威マップ — CRQC到来シミュレーション
上＝現行暗号の一覧。年を進めると、CRQC出現の予想帯（紫、時期は不確実）で公開鍵系が赤く崩れ、共通鍵系は黄（余裕減）〜緑（耐える）に分かれます。下＝「今盗んで、後で解読」のタイムライン。スライダーで「この暗号文は何年間秘密であってほしいか」を動かすと、保持期間がCRQC予想帯に重なる危険が見えます。
警告 — Harvest Now, Decrypt Later（今盗んで、後で解読） 暗号文は今日盗んで保存しておけるので、CRQC が完成した瞬間に「過去の通信」まで遡って裸になります。医療記録・戸籍・外交文書・企業秘密など10年以上秘密であるべきデータは、「量子コンピュータが来てから対応」では手遅れ。長期保存データの保護は2026年の今から耐量子方式に切り替える必要があり、これが各国が移行を急ぐ最大の理由です。
x + y > z　ならば手遅れ モスカの不等式 — x: データが秘密であるべき年数、y: 移行にかかる年数、z: CRQC到来までの年数。大組織の暗号移行（y）は10年仕事なので、z が「2030年代のどこか」なら多くの組織で既に警報が鳴っている

2. 格子という新しい砦 — なぜ量子でも硬い（と考えられる）のか

移行先の主役は格子暗号です。格子とは、基底ベクトル b1, …, bn の整数係数の組み合わせで作れる点の集合。ここで「与えられた点に最も近い格子点を探せ」という最近ベクトル問題（CVP）や「最短の非ゼロ格子ベクトルを探せ」という最短ベクトル問題（SVP）が、高次元では猛烈に難しくなります。

面白いのは同じ格子を張る基底が無数にあること。ほぼ直交した「良い基底」を持っていれば、座標を丸めるだけ（Babai の丸め法）で最近格子点がほぼ当てられます。しかし細長くほぼ平行な「悪い基底」しか持っていないと、同じ丸め操作が大外れする。良い基底＝秘密鍵、悪い基底＝公開鍵という非対称性が、そのまま暗号になります。下のデモでクリックして体験してください。

最近格子点を探せ — 良い基底 vs 悪い基底（クリックで目標点を移動）
×＝目標点（キャンバスをクリックで移動）。オレンジ＝いまの基底で座標を丸めた推定、緑＝真の最近格子点。悪い基底に切り替えると同じ丸め操作が大外れします。この2次元では総当たりでも探せますが、下のメーターのとおり実際の暗号は数百次元 — 候補数が宇宙の原子数を超え、良い基底なしには誰も探せません。
b ≡ A·s + e （mod q） LWE（Learning With Errors）問題 — ランダム行列 A と b から秘密 s を当てる。小さな誤差 e を足すだけで連立一次方程式が一気に困難になる。ML-KEM / ML-DSA はこの構造（Module-LWE）の上に建っている
POINT — 「量子でも硬い」と考えられる3つの根拠 ① 最悪ケースからの帰着：ランダムに作った LWE を平均的に解けるなら、格子問題の「最悪の意地悪なインスタンス」まで解けてしまうことが証明されている（Ajtai・Regev）。つまり鍵をランダムに作るだけで最悪ケースの硬さが保証される — RSA にはない性質。 ② ショアが効く構造がない：ショアの高速化の源は「周期性」という隠れた代数構造だが、格子問題にはそれに対応する使いやすい構造が見つかっていない。 ③ 40年以上の攻撃の蓄積：LLL 以来の古典解読も量子アルゴリズム研究も、次元に対して指数時間の壁を破れていない。 ただしこれは「破る方法が見つかっていない」という経験的信頼であって数学的証明ではない。P≠NP と同じく、暗号の安全性は常に仮定の上に立つ。

3. 標準化と移行の現在地 — 2016年の公募から2026年のいま

NIST は2016年に耐量子暗号の公募を開始し、世界中から集まった82方式（受理69方式）を約8年がかりの公開の潰し合いにかけました。2022年に最終候補を選定し、2024年8月に最初の標準が正式発行：鍵交換の ML-KEM（旧 Kyber、FIPS 203）、署名の ML-DSA（旧 Dilithium、FIPS 204）と SLH-DSA（旧 SPHINCS+、ハッシュベース、FIPS 205）です。さらに2025年3月には格子偏重へのバックアップとして符号ベースの HQC を追加選定し、格子系の FN-DSA（旧 Falcon）も標準化作業が続いています。

一歩先へ — SIKE の脱落が教えたこと 同種写像ベースの SIKE は鍵が短く有望視され、最終ラウンドまで残った。ところが2022年、Castryck と Decru が量子コンピュータどころか普通のノートPCで約1時間で破る古典攻撃を発表し、即座に脱落（前段では多変数署名の Rainbow も同年に古典攻撃で脱落）。教訓は2つ。①新しい数学的仮定は世界中の攻撃者の目に晒す長い検証が不可欠で、NIST の8年がかりの公開コンペはまさにそのための装置だったこと。②一つの仮定に全員が乗るのは危険で、だから NIST は格子系に加えてハッシュ系（SLH-DSA）や符号系（HQC）という別系統を意図的に残している。

そして移行は「将来の話」ではなく進行中の現実です。実運用の主流は、従来方式と PQC を二重に掛けるハイブリッド。TLS 1.3 では X25519（楕円曲線）と ML-KEM-768 を同時に走らせる X25519MLKEM768 が2024年から主要ブラウザで既定になり、大手CDNの観測では2025年時点で TLS 接続の3割超がすでにハイブリッド鍵交換を使い、その割合は増え続けています。SSH（OpenSSH は2022年からハイブリッド鍵交換が既定）、Signal の PQXDH（2023）、Apple iMessage の PQ3（2024）と、身近なプロトコルは次々に対応済み。NIST は移行計画の草案（IR 8547）で従来公開鍵暗号を2030年に非推奨、2035年に廃止という道筋を示しています。一方で、証明書チェーンのサイズが膨らむ署名の移行と、更新の難しい組み込み機器・レガシーシステムは、鍵交換より遅れて2020年代後半の課題として残っています。

PQC移行タイムラインと、ハイブリッドという保険
上＝標準化と移行の歩み（2026年のいま＝緑の点）。下＝TLSのハイブリッド鍵交換。2つの鍵交換の結果 ss₁・ss₂ を混ぜてセッション鍵を作るので、チェックボックスでどちらか片方を破っても鍵は漏れません。両方同時に破られて初めて危険 — 新旧それぞれの「未知のリスク」に対する保険です。

4. まとめ — 量子時代の暗号設計図