量子コンピュータによる暗号解読リスクに備え、より良い署名アルゴリズムを待てない理由

RSA および ECC は、過去数十年にわたり私たちが依存してきた暗号化アルゴリズムですが、十分に高度な量子コンピュータによる攻撃に対して脆弱です。そのような量子コンピュータはまだ存在していませんが、予想よりも早く登場する可能性があります。幸いにも解決策はすでに利用可能です：量子攻撃に対する耐性を備えた ML-KEM 暗号および ML-DSA 署名へ移行することです。これらは 2024 年、米国国立標準技術研究所（NIST）によって、8 年にわたる公開国際競争を経て標準化されました。

ポスト量子暗号への移行は現在、本格的に進行中です。執筆時点では、Cloudflare が処理するトラフィックの大部分がすでに ML-KEM 暗号を使用しており、「今 Harvest して後で Decrypt」という攻撃によるデータ脅威から保護されています。しかし、暗号化は課題の一部に過ぎません：古典的な暗号を破る能力を持つ量子コンピュータに対して完全に安全であるためには、認証システムを不正アクセスから守るためにポスト量子署名の導入を目指しています。Cloudflare が完全にポスト量子セキュリティを実現する目標年は 2029 年です。

今日標準化されているオールラウンド型の量子耐性署名方式である ML-DSA には欠点もあります：通信上でのデータサイズが非常に大きく、RSA や ECC では可能だった多くのトリックは ML-DSA では実行できません。より優れた量子耐性署名方式も今後登場します：先月、NIST は「signatures on-ramp」の第 3 ラウンドへ 9 つの量子耐性署名方式を推進すると発表しました。また、前回のコンペティションで選ばれた FN-DSA（旧 Falcon）のドラフト規格は間もなく策定される見込みです。

私たちは量子耐性署名アルゴリズムの進展に非常に興味を持っており、2021 年、2022 年、2024 年、そして 2025 年の進捗について記事を書いてきました。今回のブログ投稿では、最新の動向を詳しくご紹介します。

しかしまず、直面しなければならない現実があります：これらの新しい署名アルゴリズムは、PQ（量子耐性）移行の期限までに間に合いません—後ほど詳述しますが、その差は甚だしいです。問題は、私たちが待っている時間がないほど問題が迫っていることです。ML-DSA は今日すでに利用可能であり、最初の移行にはこれを使うしかありません。Eric Rescorla が 2024 年に記した通り：

「戦うのは、欲しいアルゴリズムではなく、実際に手元にあるアルゴリズムで行うものだ」

それでもなお、より優れた量子耐性署名アルゴリズムの探索は、いくつかの理由から極めて重要であり、私たちは NIST の限られたリソースをこれに投入することが最善であると確信しています。

それでは、署名アルゴリズムの詳細を見ていきましょう。その後、利用可能な時期のタイムラインと、なぜ依然としてそれらが必要なのかという理由について考察します。

署名アルゴリズム

以下の表では、第 3 ラウンドまで進出した候補署名アルゴリズム（🤔でマーク）、量子攻撃に対して脆弱な古典的アルゴリズム（❌でマーク）、およびすでに標準化されている（✅）または間もなく標準化される予定のポスト量子アルゴリズム（📝でマーク）を比較しています。各候補は複数のバリアントを提案しており、ここではインターネット上の接続を保護するために使用されるプロトコルである TLS に関連する最も重要なバリアントをリストアップします。すべてのバリアントを検索するには、Thom Wigger の署名動物園（signatures zoo）をご覧ください。

Sizes (bytes) | CPU time (lower is better)

Family | Name variant | A | Public key | Signature | Signing | Verification

楕円曲線

Ed25519

❌

32

64

0.15

1.3

因数分解

RSA 2048

❌

272

256

80

0.4

格子暗号

ML-DSA 44 (Lattice-based Digital Signature Algorithm 44)

✅

1,312

2,420

1 (ベースライン)

1 (ベースライン)

対称

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

知識の証明

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

UOV Ip-pkc

🤔

43,576

128

0.3

2

この表に関するいくつかの補足：ほとんどの候補には、すべてのセキュリティレベルにおいて複数のバリアントが存在します。ここでは TLS にとって最も関連性の高いバリアントを、セキュリティのゴールドスタンダードである 128 ビット・セキュリティ・レベルで示しています。CPU 処理時間は、2026 年 6 月の「シグネチャー・ズー（signatures zoo）」から取得したものであり、これは第 2 ラウンドの提出文書およびその後の進展から収集されたものです。候補者は第 3 ラウンドに向けて変更を加えることが許可されており、これがこれらの数値に影響を与えます。一部のアルゴリズムは計算量とサイズにおいて改善される一方、新たな攻撃に対抗するために性能が後退するものもあります。最新の数値については「ズー」をご確認ください。FN-DSA と SQIsign の署名には ⚠️️ を付記しました。これらは高速かつタイミングサイドチャネル耐性を備えた形で実装することが難しいためです。LMS 署名には ⚠️ を付記しています。これは、安全な LMS 署名では署名間を跨いで状態を保持する必要があること、また記載された署名時間は 32MB のキャッシュを前提としていることによるものです。SLH-DSA の 128-24 バリアントにも ⚠️️ を付記しました。これは 2^24 回未満の署名作成を意図しているためです。

「オールスター」アルゴリズムは存在しない

一目で際立っているのは、量子耐性を持たない楕円曲線署名アルゴリズムである Ed25519 が、量子脆弱性を無視すれば圧倒的に最も優れた総合的な選択肢だということです。公開鍵サイズ、署名サイズ、署名時間を含むほぼすべての指標において最良の数値を誇ります。検証時間においては劣りますが、绝大多数のアプリケーションにとって十分すぎるほど高速です。

これはポスト量子アルゴリズムのリストとはかなり異なります。単一の「オールスター」アルゴリズムがあるのではなく、おおよそ 2 つのカテゴリーがあります。「スペシャリスト」と呼ばれるもので、いくつかの指標では信頼できる楕円曲線署名に迫るものの、他の指標では問題があり、適切な展開シナリオであれば非常に優れたものになります。もう一つは「ジェネラリスト」で、ML-DSA（Machine Learning Digital Signature Algorithm）などがこれに該当します。これはすべての指標において楕円曲線ほど性能が良くありませんが、欠点の面ではこれまでのところバランスが取れています。

スペシャリスト

まずはスペシャリストから始めましょう。

SQIsign: 署名サイズは小さい / 署名作成が遅い

ワイヤー上のバイト数だけを見れば、SQIsign は楕円曲線暗号（Elliptic Curve Cryptography）のほぼ完璧な差し替え候補のように見えます。署名が 148 バイト、公開鍵が 65 バイトで、RSA-2048 を上回ります。残念ながらタダ飯はありません。SQIsign には 3 つの弱点があります。第一に、これは現在検討されている中で最も複雑なアルゴリズムです。第二に、署名の作成と検証が遅いです。最後に、タイミングサイドチャネル攻撃に対して安全な形で署名を作成する実装が難しく、そうした場合にもパフォーマンス低下を伴います。

これまではあまり良い話ではありませんでしたが、実際にはもっとひどい状況でした。2024 年を振り返った時点では、まだタイミングサイドチャネルに対する安全な実装が存在せず、署名の検証速度は 20 倍も遅かったのです。さらに、このスキームを簡素化する上で歓迎すべき進捗も見られています。

これらの劇的な改善にもかかわらず、予見可能な将来において、(サイドチャネル耐性のある)署名処理が TLS ハンドシェイクのような典型的なオンラインケースで実用できるほど高速になる可能性は低い。しかし、CA 署名や DNSSEC のようなオフラインケースでは、署名時間よりも検証時間が重要となるため、SQIsign は適用の余地があるかもしれない。

しかし、私たちが本当に議論すべきはセキュリティの問題である。SQIsign は等方性 (isogenies) に基づいている。非常に有名な話として、ML-DSA を標準化する最初の NIST PQC 競争の最終段階で大きく破られた SIKE という別の等方性ベースのアルゴリズムがある。SIKE は、ポスト量子暗号が突然崩壊する可能性があることを示す教訓としてよく引き合いに出される。これにはいくつかのニュアンスが必要である。第一に、SIKE のセキュリティ、特にその破綻につながったトーションポイント (torsion points) についてはすでに懸念があった。これらの懸念により、SIKE は標準化のために選定されず、破られる前に追加の評価ラウンドへ延期された。(実際、これは NIST プロセスがうまく機能している好例である。) SQIsign はトーションポイントを使用せず、SIKE の場合のような類似の懸念はない。

もう一つの注目すべきセキュリティ特性は、SQIsign に対する既知の最良の攻撃が、よく選ばれた楕円曲線に対する古典的な攻撃と同様に、一般的な総当たり攻撃であるということです。これは、攻撃アルゴリズムが徐々に改善され、パラメータをより大きな署名へと押しやっている RSA、格子暗号、多変数暗号とはかなり異なります。それでも、等分写像の背後にある数学は非常に豊かで、他のアルゴリズムと比較すると、数学的な攻撃面は非常に広いです。しかしながら、そのセキュリティ性は、後ほど議論する構造化された多変数アルゴリズムよりもむしろ健全であるように思われます。

SQIsign は莫大な可能性を秘めたアルゴリズムです。それを早すぎた時期に標準化するのは惜しいことです。著者の方々には、以下のウィッシュリストをお伝えしたいと考えています。

理想的には、署名時間や署名サイズとのトレードオフが生じる場合でも、検証時間をさらに短縮することです：SQIsign の署名はすでに十分に小さく、またオフラインでの署名時間は多少の余裕があります。

タイミングサイドチャネルに対する安全な実装がデフォルトとなるべきであり、特に署名時間がさらに短縮されることで、一部のオンライン署名アプリケーションを誘発する可能性がある場合にはなおさらです。

しかし何よりも、私たちの願いは SQIsign を簡素化することです。

UOV: 極めて小さな署名 / 巨大な公開鍵

UOV（非対称オイル・ビネガー）は、1999 年に最初に提案された古典的な多変数署名アルゴリズムです。その特徴として、署名サイズが極めて小さく、わずか 96 バイトしかありません。ただし、その代償として公開鍵のサイズが膨大で、66 キロバイトに達します。これは、接続設定時にワイヤー上で送信される TLS サーバー証明書の公開鍵には適していませんが、公開鍵を事前に配布するケースでは有益です。

WebPKI を例にとりましょう。一般的なブラウザは約 100 のルート証明書と 30 の証明書透明性ログを信頼しており、これら UOV を使用した場合の公開鍵の合計サイズは約 8 メガバイトに達します。

一般的な TLS 接続における公開鍵と署名。

ルート証明書は帯外（out of band）でクライアントに送信されるため、そこで UOV 署名を使用するというアイデアがあります。しかし、これは確実な解決策ではありません。そのサイズの問題から、UOV ルート証明書を中間局として使用する場所での相互署名（cross-signing）は現実的ではないからです。同時に、より大きなポスト量子署名が採用されれば、相互署名や中間局の価値はそもそも低下します。これにより、ルート証明書をクライアントに直接含める傾向が強まります。これも UOV を有利にする方向には働きますが、限度があります。もしルート証明書の数が 1,000 を超えると、鍵材料の総量が 66MB を超え、ブラウザのダウンロードサイズ（例：Firefox 151 では 90MB）に占める割合が非常に大きくなってしまうからです。

多変数暗号のセキュリティについて

セキュリティはどうでしょうか。過去数年間で、公開鍵のサイズを縮小するために追加の数学的構造を利用する UOV の多くの派生型が提案されてきました。しかし、これらの構造化された多変数方式は、Rainbow や GeMMS などの方式が非常に深刻な形で破られたように、実績にむらがあります。これらを区別することが重要です