概要
RSA や ECC といった、私たちが何十年も頼ってきた暗号アルゴリズムは、十分に高度な量子コンピュータによって破られる可能性があります。そうした量子コンピュータはまだ存在しませんが、予想より早く到来する可能性が高まっています。幸い解決策は既に存在します：ML-KEM 暗号化と ML-DSA 署名へ移行することです。これらは量子攻撃に耐えるよう設計されており、NIST（米国標準技術研究所）が 2024 年に 8 年に及ぶ公開国際競技ののち標準化しました。
ポスト量子暗号（PQC）への移行は現在進行中です。執筆時点で、Cloudflare が扱うトラフィックの大部分は既に ML-KEM 暗号化を使用しており、今すぐ取得して後で復号する（harvest-now-decrypt-later）攻撃に対するデータの保護は達成しています。しかし、暗号化は問題の一部分にすぎません：古典暗号を破ることのできる量子コンピュータに対して完全に安全であるためには、認証システムを不正アクセスから保護するためにポスト量子署名の配備も必要です。Cloudflare は 2029 年までに完全なポスト量子セキュリティを目指しています。
現状で最も汎用的なポスト量子署名スキームである ML-DSA には欠点があります：通信上でのサイズが大きく、RSA や ECC で行えていた多くの工夫が ML-DSA ではできません。より良いポスト量子署名スキームは目前にあります：先月、NIST は「signatures on-ramp」の第3ラウンドに 9 つのポスト量子署名を進めると発表しました。また、以前の競技から選ばれた Falcon（現 FN-DSA）の草案標準も間もなく公開される見込みです。
我々はポスト量子署名アルゴリズムの進展に強い関心を持っており、2021、2022、2024、2025 年にその進捗について記事を書いてきました。本記事では最新の展開を詳述しますが、まず部屋の中の象に触れなければなりません：これらの新しい署名アルゴリズムは PQ 移行に間に合うほど迅速には利用できない——のちに示す通り、まったく間に合わないわけです。問題は到来が早すぎて待てないという点です。ML-DSA は今日利用可能であり、最初の移行ではこれを使わざるを得ません。Eric Rescorla が 2024 年に書いたように:
You go to war with the algorithms you have, not the ones you wish you had.
それでも、より良いポスト量子署名アルゴリズムの探索は重要であり、NIST の限られたリソースを投入する価値があると我々は確信しています。まず署名アルゴリズムを詳細に見て、その後で利用可能になるまでのタイムラインと、なぜそれでも改良を追い求める必要があるのかを説明します。
署名アルゴリズム一覧
以下の表では、第3ラウンドに進んだ候補（🤔）と、量子攻撃に脆弱な古典アルゴリズム（❌）、既に標準化されたポスト量子アルゴリズム（✅）、間もなく標準化されるもの（📝）を比較しています。各候補は複数のバリアントを提案しており、ここでは TLS（インターネット上の接続保護に使われるプロトコル）に関連の深いバリアントを示しています。全バリアントを調べるには Thom Wigger の signatures zoo を参照してください。
| Family | Name variant | Public key | Signature | Signing | Verification |
|---|
| Elliptic curves | Ed25519 ❌ | 32 | 64 | 0.15 | 1.3 |
| Factoring | RSA 2048 ❌ | 272 | 256 | 80 | 0.4 |
| Lattices | ML-DSA 44 ✅ | 1,312 | 2,420 | 1 (baseline) | 1 (baseline) |
| Symmetric | SLH-DSA 128s ✅ | 32 | 7,856 | 14,000 | 40 |
| SLH-DSA 128f ✅ | 32 | 17,088 | 720 | 110 |
| SLH-DSA 128-24 📝 | 32 | 3,856 | 7,000,000 | ⚠️ 4 |
| LMS | M24_H20_W8 ✅ | 48 | 1,112 | 2.9 | ⚠️ 8.4 |
| Lattices | FN-DSA 512 📝 | 897 | 666 | 3 | ⚠️ 0.7 |
| Lattices | HAWK 512 🤔 | 1,024 | 555 | 0.25 | 1.2 |
| Proof of knowledge | MQOM L1-gf16-fast-5r 🤔 | 60 | 3,280 | 8 | 20 |
| SDitH | SDitH2-L1-gf2-fast 🤔 | 70 | 4,484 | 15 | 40 |
| FAEST | EM-128f 🤔 | 32 | 5,060 | 4.2 | 9 |
| Isogeny | SQIsign I 🤔 | 65 | 148 | 300 | ⚠️ 50 |
| Multivariate | MAYO one 🤔 | 1,420 | 454 | 2.1 | 0.4 |
| MAYO two 🤔 | 4,912 | 186 | 1.1 | 0.8 |
| QR-UOV I-(127 156 54 3) 🤔 | 24,225 | 200 | 9.3 | 20 |
| SNOVA (24,5,4) 🤔 | 1,016 | 248 | 1.2 | 1.7 |
| SNOVA (25,8,3) 🤔 | 2,320 | 165 | 1 | 1.5 |
| SNOVA (37,17,2) 🤔 | 9,842 | 124 | 0.8 | 1.3 |
| UOV | Is-pkc 🤔 | 66,576 | 96 | 0.3 | 2.4 |
| Ip-pkc 🤔 | 43,576 | 128 | 0.3 | 2 |
表に関する補足
- ほとんどの候補は各セキュリティレベルに複数のバリアントを持ちます。ここでは TLS に最も関連する 128-bit セキュリティレベルのバリアントを示しています。
- CPU 時間は 2026 年 6 月時点の signatures zoo に基づき、ラウンド 2 の提出文書やその後の改良から収集したものです。候補は第3ラウンドで変更を加えることが許されており、これらの数値は変動します。改善するものもあれば、新たな攻撃に対抗するために後退するものもあります。最新の数値は signatures zoo を参照してください。
- FN-DSA と SQIsign の署名は ⚠️ とマークしました。どちらも高速かつタイミング副チャンネル耐性のある実装が難しいためです。LMS の署名には ⚠️ が付いています。安全な LMS 署名は署名ごとに状態（state）を保持することが必要であり、表の署名時間は 32MB のキャッシュを仮定したものです。SLH-DSA の 128-24 バリアントは 2^24 未満の署名を生成することを前提にしているため ⚠️ を付けています。
「オールスター」アルゴリズムは存在しない
すぐに目につくのは、量子に脆弱な楕円曲線署名アルゴリズム Ed25519 が（量子脆弱性を無視すれば）ほとんどの指標で圧倒的に優れている点です：公開鍵サイズ、署名サイズ、署名時間などほぼすべての面で最良で、検証時間だけが他に劣るものの実用上は十分高速です。
ポスト量子アルゴリズムの顔ぶれはこれと大きく異なります。単一の「オールスター」アルゴリズムがあるのではなく、だいたい二つの系統に分かれます：
- ある指標では楕円曲線に近づくが、他の点で問題を抱える「スペシャリスト」たち。適切な運用シナリオでは優れる。
- ML-DSA のような「ジェネラリスト」たち。楕円曲線ほど全方位に優れるわけではないが、欠点が比較的バランスしており、汎用に使いやすい。
スペシャリスト
以下、代表的なスペシャリストをいくつか挙げます。
SQIsign：小さな署名 / 遅い署名作成
通信上のバイト数だけを見ると、SQIsign は楕円曲線暗号のほぼ完璧な代替に見えます。署名 148 バイト、公開鍵 65 バイトは RSA-2048 を上回ります。だが代償はあります。
弱点は三つあります。第一に、候補群の中で最も複雑なアルゴリズムであること。第二に、署名作成と検証がかなり遅いこと。第三に、署名作成をタイミング副チャンネルに耐性のある方法で実装するのが難しく、その場合は性能ペナルティが付くことです。
これだけでも厳しいのですが、2024 年に我々が確認したときはさらに深刻でした：当時はタイミング副チャンネル耐性のある実装が存在せず、署名検証は 20 倍遅かったのです。その後簡素化や性能改善の歓迎すべき進展がありましたが、それでも（副チャンネル耐性を考慮すると）近い将来にオンラインケース、たとえば TLS ハンドシェイクのような場面で十分に高速な署名ができるとは考えにくいです。しかし、CA 署名や DNSSEC のように署名時間より検証時間が重要なオフライン用途では有用かもしれません。
セキュリティ面も議論すべき点です。SQIsign は isogenies（同型曲線）に基づきます。SIKE という同種のアルゴリズムは、最初の NIST PQC 競技の後期に重大な破壊的攻撃を受けました。SIKE は突如として破られた例としてよく引き合いに出されますが、これは注意深い解釈を要します。まず SIKE には既にセキュリティ上の懸念があり、特に破壊につながったトーション点（torsion points）に関する問題が指摘されていました。そのため SIKE は標準化から外され、追加評価ラウンドに回された後で破られた経緯があります（NIST プロセスが正常に機能した例でもあります）。
SQIsign はトーション点を使っておらず、SIKE と同様の直接的な懸念はありません。また、SQIsign に対する既知の最良攻撃は汎用的な総当たりに近く、よく選ばれた楕円曲線に対する古典攻撃と似ています。これは、パラメータが徐々に大きくされてきた RSA や格子、multivariate といった系とは異なります。ただし、isogeny の数学は非常に豊かであり、他のアルゴリズムと比較して攻撃を試みうる数学的攻撃面が多いのも事実です。とはいえ、構造を持つ multivariate 系よりは堅牢に見えます。
SQIsign には大きな可能性がありますが、早まって標準化するのは惜しいとも言えます。著者陣に対して我々の要望は以下の通りです：
- 検証時間をさらに短縮してほしい（署名サイズや署名時間とトレードオフになってもよい）。SQIsign の署名は既に十分小さく、オフライン署名の時間には余裕がある。
- タイミング副チャンネル耐性のある実装をデフォルトにしてほしい。もし署名時間がさらに短縮されると、オンライン署名用途に使おうとする誘惑が強くなるためである。
- 何よりも、アルゴリズムの簡素化が望ましい。
UOV：小さな署名 / 巨大な公開鍵
UOV（unbalanced oil and vinegar）は 1999 年に提案された古典的な multivariate 署名アルゴリズムで、署名は非常に小さく 96 バイトです。代償は巨大な公開鍵（66kB）です。TLS サーバー証明書の公開鍵は接続確立時に送信されるため TLS の典型的なケースでは不利ですが、公開鍵を事前配布できるケースでは有利になります。
WebPKI を例に取ると、典型的なブラウザは約 100 個のルート証明書と 30 個の Certificate Transparency ログを信頼しており、これらの公開鍵を UOV で持つと合計約 8MB になります。ルート証明書はクライアントへアウト・オブ・バンドで配信されるため、ルートに UOV を使うという案は考え得ます。しかし、サイズのためにルートが中間としてクロスサインされる運用は現実的でなくなります。同時に、どの大きなポスト量子署名を使ってもクロスサインや中間の利用は魅力が薄れます。これはクライアントにより多くのルート証明書を直接組み込む傾向を促し、UOV の採用には一利があります。ただしルート証明書の数が 1,000 を超えると公開鍵だけで 66MB 以上になり、ブラウザのダウンロードサイズに占める割合が大きくなる（例：Firefox 151 で合計 90MB 程度）ため限界があります。
multivariate のセキュリティ
セキュリティ面ではどうでしょうか。UOV の公開鍵サイズを削減するために追加の数学的構造を持たせた変種が長年提案されてきました。これらの構造化された multivariate スキーム（たとえば Rainbow や GeMMS）は重大な破綻を起こした例があり、記録はまちまちです。UOV 自体は構造化変種ほど脆弱な実績はありませんが、完全に問題がないわけでもありません。
多くの暗号と同様に、初期には基礎的な攻撃やパラメータ設定の落とし穴が見つかり成長痛がありました。実際、UOV の "U" は unbalanced（アンバランス）の略で、これは UOV の元になった 1997 年の oil-and-vinegar スキームにおけるパラメータ設定ミスへの修正を示します。元のスキームは oil と vinegar の変数数が等しく設定されており、これが攻撃を許すことが判明しました。名前の由来に興味があれば：公開鍵を構成する二次方程式系は vinegar x vinegar と oil x vinegar 項は含むが oil x oil 項を含まない、まるで小さな油の粒が分離したビネグレットのような構造です。
歴史に戻ると、2005 年から 2020 年は multivariate 署名にとって静かな期間でした：UOV の理解は深まったものの、そこには…