ポスト量子暗号（PQC）の原理：格子問題と ML-KEM/ML-DSA

なぜ「量子で破れる」のか：Shor のアルゴリズム

現在公開鍵暗号として広く使われている RSA / ECC / DH の安全性は、すべて特定の数学問題が古典計算機では現実時間で解けないことに依拠しています。

• RSA：巨大な合成数 N の素因数分解が難しい
• ECC（楕円曲線）/ DH：群の上での離散対数問題が難しい

これらは古典アルゴリズムでは（一般数体ふるい等を使っても）準指数時間〜指数時間かかり、鍵長を増やせば事実上解けません。問題は、量子計算機ではこの前提が崩れることです。

1994 年に Peter Shor が示した Shor のアルゴリズムは、素因数分解と離散対数を多項式時間で解きます。核心は、これらの問題が周期発見（period finding）に帰着できる点にあります。たとえば素因数分解では、a^x mod N という関数の周期 r を求められれば、N の因数が高い確率で得られます。Shor はこの周期を量子フーリエ変換（QFT）で一気に求めます。量子重ね合わせで多数の x を同時に評価し、QFT によって周期成分を増幅して観測する――この「周期を指数的に速く見つける」能力が、RSA・ECC・DH を鍵長に関わらず原理的に破壊します。

重要なのは、Shor を実行できる誤り訂正済みの大規模量子計算機（CRQC）はまだ存在しない点です。しかし「いつできるか」が不確実だからこそ、後述の harvest-now-decrypt-later が現実の脅威になります。

格子問題：量子でも難しいとされる土台

ポスト量子暗号（PQC）は、量子計算機でも効率的に解く方法が知られていない数学問題の上に作られます。NIST 標準の中核を担うのが格子（lattice）問題です。

格子とは、基底ベクトルの整数結合で張られる点の集合です。n 次元空間で「与えられた点に最も近い格子点を探す（最近ベクトル問題 CVP）」「最短の非ゼロ格子点を探す（最短ベクトル問題 SVP）」は、次元が上がると古典でも量子でも難しいことが知られています。

実際の暗号で直接使われるのは、この困難性を扱いやすくした LWE（Learning With Errors）です。LWE は次の形をしています。秘密ベクトル s に対し、ランダムな A と小さな誤差 e を使って

b = A · s + e   (mod q)

を多数公開する。(A, b) から s を復元するのが LWE 問題です。誤差 e が無ければ単なる連立一次方程式で簡単に解けますが、わざと小さなノイズを混ぜることで、ガウスの消去法が破綻し、問題が格子の最近ベクトル探索に化けて難しくなります。LWE は平均ケースの困難性が最悪ケースの格子問題に帰着することが証明されており、これが安全性の理論的な強さの源です。

ML-KEM（Kyber）：鍵をカプセル化する

ML-KEM（Module-Lattice-based Key-Encapsulation Mechanism、旧 CRYSTALS-Kyber、FIPS 203）は、共通鍵を安全に共有するための KEM です。RSA 暗号化や DH 鍵交換の置き換えにあたります。

KEM は「暗号化」ではなく鍵カプセル化という形を取ります。任意のメッセージを暗号化するのではなく、ランダムな共通鍵そのものを生成して相手に届けるのが目的です。動作は 3 つの関数からなります。

KeyGen()        -> (公開鍵 pk, 秘密鍵 sk)
Encaps(pk)      -> (暗号文 ct, 共有鍵 K)     # 送信側：ランダムKを作りカプセル化
Decaps(sk, ct)  -> K                          # 受信側：自分のskでKを取り出す

中身は LWE そのものです。Encaps は受信者の公開鍵（LWE の (A, b) に相当）を使ってランダム性を「ノイズ付きの計算」に埋め込み、その結果として両者が同じ共有鍵 K を導けるようにします。攻撃者は ct を見ても、LWE を解かない限り K を復元できません。得られた K は 共通鍵暗号（AES-256-GCM 等）の鍵として使われ、以降の大量データはそれで暗号化されます。構造としては crypto-basics で説明したハイブリッド方式とまったく同じで、鍵交換部分だけが格子ベースに置き換わる形です。

ML-KEM は IND-CCA2 安全を達成するため、内部で Fujisaki-Okamoto 変換を用います。これは復号時に暗号文を再暗号化して一致を確かめる仕組みで、不正な暗号文を送って秘密鍵の情報を漏らそうとする選択暗号文攻撃を防ぎます。

ML-DSA（Dilithium）：格子ベースの署名

ML-DSA（Module-Lattice-based Digital Signature Algorithm、旧 CRYSTALS-Dilithium、FIPS 204）は、RSA 署名や ECDSA を置き換える電子署名です。安全性は Module-LWE と Module-SIS（短い解を見つける問題）の両方に依拠します。

仕組みは Fiat-Shamir with Aborts と呼ばれる方式です。署名は「秘密鍵を知っていることのゼロ知識証明」をハッシュで非対話化したもので、z = y + c·s のような形で秘密 s を含む値を作ります。ここで y は毎回のランダムなマスクで、s を統計的に隠します。ただし z が一定範囲を外れると s の情報が漏れる恐れがあるため、範囲外なら署名をやり直す（abort）――この棄却サンプリングが「with Aborts」の由来であり、安全性の要です。

PQC は安全な代わりにサイズが大きいのが共通の弱点です。代表的なパラメータを古典方式と比べると一目瞭然です。

harvest-now-decrypt-later と移行戦略

PQC への移行を「量子計算機ができてからでいい」と考えるのは危険です。理由は鍵交換と署名で脅威の時間軸が違うことにあります。

• 鍵交換（機密性）：攻撃者は今のうちに暗号文を保存しておき、将来 CRQC が完成した時点で復号できます。これが **harvest-now-decrypt-later（収穫してから後で復号）**です。守りたいデータの「秘匿を保ちたい年数」が、量子計算機の登場までの猶予を超えるなら、対策は今すぐ必要です。
• 署名（真正性）：偽署名は CRQC ができて初めて作れるため、過去に遡って偽造はできません。証明書の有効期間内に移行が間に合えばよく、相対的に猶予があります。

このため実務の最優先は鍵交換のハイブリッド化です。既存の X25519 と ML-KEM を組み合わせ、両方の共有鍵を結合（KDF で混合）して TLS のセッション鍵を導出します。

shared_secret = KDF( ECDH(X25519) || Decaps(ML-KEM) )
# どちらか一方が破れても、もう一方が無事なら安全が保たれる

移行を計画する際は 暗号アジリティ（crypto-agility）――アルゴリズムを後から差し替えられる設計が鍵になります。具体的には、(1) 自組織で使う暗号資産（プロトコル・ライブラリ・証明書）の棚卸し、(2) 長期秘匿が必要なデータの鍵交換からハイブリッド KEM へ移行、(3) ライブラリやハードウェアのアルゴリズム差し替え可能性の確保、という順で進めます。PKI / 証明書 のチェーンも将来 ML-DSA 署名へ移行する必要があり、サイズ増を見越した設計が求められます。

まとめ

量子の脅威の本質は Shor のアルゴリズムが周期発見を多項式時間で解き、RSA・ECC・DH を鍵長に関わらず破ることにあります。対称暗号とハッシュは Grover で強度が半減する程度なので、長さを上げれば対応可能です。

公開鍵側の答えが、**格子問題 Module-LWE/SIS に依拠する ML-KEM（FIPS 203）と ML-DSA（FIPS 204）**です。LWE は「小さなノイズを混ぜて連立方程式を最近ベクトル探索に化けさせる」ことで量子耐性を得ており、量子計算機でも効率的な解法が知られていません。

実務では harvest-now-decrypt-later のため、鍵交換の X25519+ML-KEM ハイブリッド化が最優先。署名は猶予があるものの、証明書チェーン全体の移行を見据え、暗号アジリティを確保した設計で臨むべきです。土台となる鍵と署名の考え方は 暗号の基礎、暗号化とハッシュの役割分担は ハッシュと暗号化の違い、信頼の連鎖は PKI と証明書 と合わせて押さえてください。