こんにちは！と書こうとしたらこんばんはになってしまった...
GMOコネクトの名もなきエンジニアです。
よろしくお願いします！
日刊IETFは、I-D AnnounceやIETF Announceに投稿されたメールをサマリーし続けるという修行的な活動です！！
今回は、2025-10-26（UTC基準）の投稿をまとめたいところですが...0件でした。
- Internet-Draft: 0件
- RFC: 0件
何もしないと不安になるので気になるInternet-Draftを解説します！笑
Post-Quantum Algorithms guidance（draft-prabel-pquip-pqc-guidance）解説
Draftの位置づけ
draft-prabel-pquip-pqc-guidance-01は、IETFのPQUIP(Post-Quantum Use In Protocols)WG向けに提出されたInternet-Draftで、Huaweiの4名の著者が2025年10月20日に発表し、2026年4月23日まで有効となります。
Draftには "Intended status: Standards Track" と記載されているんですが、内容的に Informationalが適切なステータスと考えられます。本ドキュメントも規範的要件を定義するのではなく、既存のPQCアルゴリズムに関する情報を集約し、選択のための助言を提供することを目的としています。WGでのレビューを経て、最終的にはステータスが修正される可能性が高いと思います。
このDraftの目的
3つの明確な目的があります。第一に、広く研究されているPQCアルゴリズムのパラメータサイズ、セキュリティ仮定、対象セキュリティモデルといった一般情報を提供すること。第二に、実装者やプロトコル設計者、標準開発者、政策立案者が適切なPQC暗号プリミティブを理解し選択できるよう支援すること。第三に、統一されたフォーマットで情報を集約し、PQC移行における意思決定と相互運用性を促進することのようです。
対象アルゴリズムの全体像
本Draftが取り上げるのは、主要なセキュリティ機関や標準化団体(NIST、ISO、欧州各国のセキュリティ機関)が推奨し、CRQC(Cryptographically Relevant Quantum Computer:暗号解読に使える実用的な量子コンピュータ)に対して安全と考えられている暗号方式です。
具体的には、KEM(Key Encapsulation Mechanism:鍵カプセル化メカニズム)として5種類、デジタル署名方式として5種類を扱っています。
KEMと鍵交換プロトコルの区別
KEMは、鍵確立プロトコル内の構成要素として使える暗号プリミティブです。従来の鍵交換と同じ目的を達成できるものの、KEM自体は対話的な手順やメッセージフロー、認証ステップを定義しません。
- KEM: 共有秘密を安全に導出してカプセル化する仕組みを提供
- 鍵交換プロトコル: 1つ以上のKEMを使って、当事者間で秘密鍵を安全に確立する対話的な手順を定義
この区別は実装者と開発者にとって混乱を避けるために明確化されています。
KEM(鍵カプセル化メカニズム)
ML-KEM(旧CRYSTALS-Kyber)
NISTが最初に標準化したPQC KEMです。構造化格子ベースの方式で、Module Learning with Errors(Module LWE)問題、つまり「誤差付き学習問題を格子の部分構造に適用した数学的問題」の計算困難性を安全性の根拠としています。
NISTはSecurity Level 3(AES-192相当)をデフォルトとして推奨しており、欧州のセキュリティ機関も同水準を最低ラインとしています。パラメータセットは512、768、1024の3種類があり、それぞれSecurity Level 1、3、5に対応します。
NIST標準仕様(FIPS 203)は2024年8月に公開されています。
ML-KEM-768のパラメータサイズ:
- 公開鍵: 1,184バイト
- 秘密鍵: 2,400バイト
- 暗号文: 1,088バイト
- 共有秘密: 32バイト
- Claimed Security Level: 3
なお、仕様では64バイトのseedで秘密鍵を表現することも認められています。
FrodoKEM
構造化格子ではなく、プレーンなLWE(Learning with Errors)困難性仮定に基づきます。構造を仮定しない分、ML-KEMより保守的な設計と言えます。ISOで標準化が検討されており、欧州のセキュリティ機関も推奨しています。
各セキュリティレベルで、基礎となる対称プリミティブにAESまたはSHAKEを選べます。AES variantはAESハードウェアアクセラレーションを持つデバイスで性能を発揮し、SHAKE variantはハードウェア支援がない環境で優位となります。なお、保守性とのトレードオフとして、ML-KEMと比べて鍵サイズは大きくなります。
FrodoKEM仕様の最新版は2024年12月5日付けです。
FrodoKEM-976-AESのパラメータサイズ:
- 公開鍵: 15,632バイト
- 秘密鍵: 31,296バイト
- 暗号文: 15,744バイト
- 共有秘密: 24バイト
- Claimed Security Level: 3
Classic McEliece
1978年のオリジナルMcEliece暗号システムをベースとした、保守的なコードベースKEMです。数十年にわたる広範な暗号解析に耐えてきた実績があります。複数の欧州セキュリティ機関がその安全性に信頼を表明しており、ISOで標準化が検討されています。
他のKEMと比較して公開鍵サイズが極めて大きい(最大1MB超)一方、暗号文は比較的コンパクト(96〜208バイト)です。各セキュリティレベルには'f' variantが存在し、内部処理は複雑になりますが鍵生成を高速化できます。
仕様書は2022年10月23日版が最新となっています。
Classic-McEliece-460896のパラメータサイズ:
- 公開鍵: 524,160バイト
- 秘密鍵: 13,608バイト
- 暗号文: 156バイト
- 共有秘密: 32バイト
- Claimed Security Level: 3
HQC
Quasi-Cyclic Syndrome Decoding(QCSD:準巡回シンドローム復号)困難性仮定に基づくコードベースKEMで、NISTによる標準化が予定されています。
公開鍵と暗号文のサイズが比較的小さく、ML-KEMよりは大きいものの他のコードベースKEMと比べてコンパクトです。
HQC仕様は2025年2月19日版が参照されています。
HQC-192のパラメータサイズ:
- 公開鍵: 4,522バイト
- 秘密鍵: 4,586バイト
- 暗号文: 8,978バイト
- 共有秘密: 64バイト
- Claimed Security Level: 3
NTRU
長い歴史と広範な分析実績を持つ構造化格子ベースKEMです。ISOで標準化が検討されています。NTRU仕様はIETFのInternet-Draft(draft-fluhrer-cfrg-ntru-02)として2025年3月版が投稿されています。
ntruhps2048677のパラメータサイズ:
- 公開鍵: 930バイト
- 秘密鍵: 1,235バイト
- 暗号文: 930バイト
- 共有秘密: 32バイト
- Claimed Security Level: 3
デジタル署名方式
デジタル署名は、メッセージやデータの真正性、完全性、否認防止を提供する暗号プリミティブです。PQCの文脈では、量子コンピューティング能力を持つ攻撃者に対しても安全性を保つよう設計されています。プロトコルメッセージの認証、コード署名、証明書などさまざまな場面で使われ、安全な通信プロトコルでは鍵確立メカニズムと組み合わせて用いられることが多くなっています。
ML-DSA(旧CRYSTALS-Dilithium)
NISTが標準化した構造化格子ベースの署名方式です。Module LWE問題とSelfTargetMSIS問題(Module Short Integer Solution問題の変種)の計算困難性を安全性の根拠としています。
欧州のセキュリティ機関は最低でもSecurity Level 3を推奨しています。SUF-CMA(Strong Existential Unforgeability under Chosen-Message Attack:選択メッセージ攻撃下での強い存在的偽造不可能性)セキュリティを提供します。パラメータセットは44、65、87の3種類です。
NIST標準仕様は、FIPS 204として2024年8月に公開されています。
ML-DSA-65のパラメータサイズ:
- 公開鍵: 1,952バイト
- 秘密鍵: 4,032バイト
- 署名: 3,309バイト
- Claimed Security Level: 3
仕様では32バイトのseedで秘密鍵を表現することも認められています。
FN-DSA(旧Falcon)
NISTが標準化に選定した格子ベースの署名方式です。浮動小数点演算に依存しており、特にサイドチャネル攻撃に対して安全に実装することが困難とされています。
EUF-CMA(Existential Unforgeability under Chosen-Message Attack:選択メッセージ攻撃下での存在的偽造不可能性)セキュリティを提供し、署名サイズはコンパクトですが、実装の複雑さがあります。
Falcon仕様は2020年10月1日版が参照されています。
Falcon-1024のパラメータサイズ:
- 公開鍵: 1,793バイト
- 秘密鍵: 2,305バイト
- 署名: 1,462バイト
- Claimed Security Level: 5
Falcon-512とFalcon-1024それぞれに、署名サイズを固定長にパディングした'padded' variantも存在します。
SLH-DSA(旧SPHINCS+)
NISTが標準化したステートレスハッシュベース署名方式です。ステートレスとは「内部状態の管理が不要」という意味で、後述するLMSやXMSSのようなステートフルな方式と対照的です。
各セキュリティレベルで2つのハッシュ関数ファミリー(SHA-2またはSHAKE)を選択でき、それぞれに2つの特定variantがあります。's' variantは署名サイズが小さく、'f' variantは署名生成が高速です。
SUF-CMAセキュリティを提供すると広く信じられていますが、形式的な証明はまだ存在しません。
NIST標準仕様は、FIPS 205として2024年8月に公開されています。
SLH-DSA-SHA2-192sのパラメータサイズ:
- 公開鍵: 48バイト
- 秘密鍵: 96バイト
- 署名: 16,224バイト
- Claimed Security Level: 3
LMS(Leighton-Micali Signatures)
Merkleハッシュツリーに基づくステートフルハッシュベース署名方式です。ワンタイム署名にLM-OTSを使用します。
ステートフルとは「署名ごとに内部状態を更新する必要がある」という意味で、状態管理を誤ると安全性が損なわれます。draft-ietf-pquip-hbs-state-00(2025年6月17日版)がステートフルハッシュベース署名の状態管理に関するガイダンスとセキュリティ考慮事項を提供しています。
複数のハッシュ関数variant(SHA-256、SHA-256/192、SHAKE256/256、SHAKE256/192)に対応しており、Winternitzパラメータ(W)の値によって署名サイズが変化します。
NIST標準仕様は、SP 800-208としては2024年8月に公開されています。
LMS_SHA256_M32_H10のパラメータサイズ(一例):
- 公開鍵: 56バイト
- 秘密鍵: 57,348バイト
- 署名: 1,456〜8,848バイト(Wの値により変動)
- Claimed Security Level: 5
XMSS / XMSS^MT
eXtended Merkle Signature Scheme(XMSS)は、ワンタイム署名にWOTS+を使用し、Merkleハッシュツリーに基づくステートフルハッシュベース署名方式です。XMSS^MTは複数のハッシュツリーを持つvariantで、より多くの署名が可能になります。
LMSと同様に慎重な状態管理が求められます。パラメータセットは高さとマルチツリー構成の組み合わせで多数存在し、SHA-2とSHAKE256の両variantが用意されています。
NIST標準仕様は、SP 800-208として2020年10月に公開されています。
XMSS-SHA2_16_256のパラメータサイズ:
- 公開鍵: 64バイト
- 秘密鍵: 2,093バイト
- 署名: 2,692バイト
- Claimed Security Level: 5
セキュリティ分類の枠組み
NISTのPQCセキュリティレベル
本ドキュメントでは、NISTのPost-Quantum Cryptography評価基準に基づいた「Claimed Security Level」を使用しています。この分類では、既存の対称鍵暗号やハッシュ関数への攻撃コストを基準として、PQCアルゴリズムの安全性を5段階で評価します。
| Category | 攻撃タイプ | 相当する既存暗号 |
|---|---|---|
| 1 | 128ビット鍵ブロック暗号への鍵探索 | AES-128 |
| 2 | 256ビットハッシュ関数への衝突探索 | SHA-256 |
| 3 | 192ビット鍵ブロック暗号への鍵探索 | AES-192 |
| 4 | 384ビットハッシュ関数への衝突探索 | SHA3-384 |
| 5 | 256ビット鍵ブロック暗号への鍵探索 | AES-256 |
詳細はNIST IR 8547(2024年11月版)に記載されています。
量子アルゴリズムに脆弱な現行暗号
量子計算機に対して脆弱となる将来的に非推奨または使用禁止となる公開鍵暗号も整理されています。
draft-prabel-pquip-pqc-guidance-01 の "Table 15: Quantum-Vulnerable Asymmetric Cryptographic Schemes"を抜粋します。
| Scheme | Hardness assumption | Disallowed (NIST) |
|---|---|---|
| ECDSA | Discrete Logarithm | after 2035 |
| EdDSA | Discrete Logarithm | after 2035 |
| RSA | Factorisation | after 2035 |
| (EC)DH | Decisional Diffie Hellman | after 2035 |
って書かれていたのですが...これって間違えてますよね汗
正しくは、次のとおりかなと思います。
| Scheme | Hardness assumption | Disallowed (NIST) |
|---|---|---|
| ECDSA | Elliptic Curve Discrete Logarithm Problem (ECDLP) | after 2035 |
| EdDSA | Elliptic Curve Discrete Logarithm Problem (ECDLP) | after 2035 |
| RSA | Factorisation | after 2035 |
| DH | Computational Diffie-Hellman (CDH) / DLP | after 2035 |
| ECDH | EC Computational Diffie-Hellman (CDH) / ECDLP | after 2035 |
EUのPQC移行タイムライン
EU PQC Workstreamは量子リスクレベルを高・中・低の3段階に区分し、段階的な移行タイムラインを提示しています(2025年6月発行の"A Coordinated Implementation Roadmap for the Transition to Post-Quantum Cryptography"より)。
- 高リスクユースケース: 2031年前に移行完了
- 中リスクユースケース: 2036年前に移行完了
- 低リスクユースケース: 2036年前に可能な限り移行完了
セキュリティ特性の比較
KEMの安全性
すべての主要KEMはIND-CCA2(適応的選択暗号文攻撃下での識別不可能性)セキュリティモデルを対象としています。
保守性の観点:
構造化格子を使わないFrodoKEMは、ML-KEMやNTRUといった構造化格子ベース方式と比べてより保守的な安全性を持つと考えられています。構造を仮定しない分、数学的仮定が単純で攻撃表面が少ないためです。
署名方式の安全性
ハッシュベース署名(SLH-DSA、LMS、XMSS)は、ML-DSAやFN-DSAのような格子ベース方式と比較して、より保守的な安全性を提供すると考えられています。ハッシュ関数の衝突耐性や第二原像耐性という、長年研究されてきた性質に依存しているためです。
セキュリティモデル:
- ML-DSA: SUF-CMA(強い存在的偽造不可能性)を達成
- FN-DSA: EUF-CMA(存在的偽造不可能性)を達成
- ハッシュベース署名: SUF-CMAに対する既知の攻撃はなく、広くSUF-CMA安全と信じられていますが、形式的な証明は未完成
実装時の考慮点
パラメータサイズのトレードオフ
実装者が直面する主なトレードオフを以下に示します。
鍵サイズと暗号文/署名サイズ:
Classic McElieceは公開鍵が極めて大きい(最大1MB超)反面、暗号文は小さい(96〜208バイト)です。対照的にML-KEMはバランスが取れており、公開鍵も暗号文も1KB程度に収まります。
- Classic McEliece-460896: 公開鍵524KB、暗号文156バイト
- ML-KEM-768: 公開鍵1.2KB、暗号文1.1KB
- FrodoKEM-976-AES: 公開鍵15.3KB、暗号文15.4KB
署名サイズでも同様のトレードオフがあります。
- SLH-DSA-SHA2-192s: 署名16KB(ハッシュベース)
- ML-DSA-65: 署名3.3KB(格子ベース)
- FN-DSA-Falcon-1024: 署名1.5KB(格子ベース)
安全性と効率性:
FrodoKEMはより保守的な設計ですが、大きな鍵サイズを必要とします。ML-KEMは効率的ですが、構造化格子という数学的構造の仮定に依存しています。将来的にこの構造に対する効率的な攻撃が発見される可能性はゼロではありません。
実装の複雑度:
FN-DSAは浮動小数点演算が必要で、サイドチャネル攻撃に対する安全な実装が難しくなっています。異なるハードウェアやコンパイラで動作の一貫性を保つことも課題となります。
ステートフルハッシュベース署名(LMSやXMSS)では慎重な状態管理が求められます。状態の複製や巻き戻しが発生すると、同じ鍵で複数の署名を生成してしまい、安全性が完全に破綻する可能性があります。
選択の指針
用途や要件に応じた選択の目安を示します。
セキュリティ要件重視:
- Security Level 3以上を選択(欧州セキュリティ機関の推奨に沿う)
- 具体的には ML-KEM-768、ML-DSA-65 など
保守的アプローチ:
- KEMならFrodoKEM、Classic McEliece
- 署名ならSLH-DSA、LMS、XMSS
バランス重視:
- KEMならML-KEM-768
- 署名ならML-DSA-65
サイズ最適化:
- KEMならHQC、NTRU(ML-KEMより小さいが、Classic McElieceよりコンパクト)
- 署名ならFN-DSA(ただし実装の複雑さに注意)
ステートレス要件:
- 署名でステートレスが必須ならSLH-DSA、ML-DSA、FN-DSA
- ステートフル(LMS、XMSS)は状態管理が確実にできる場合のみ
本ドキュメントの意義
draft-prabel-pquip-pqc-guidanceは、PQCアルゴリズムの選択と実装に関する包括的なリファレンスとなっています。主要なKEMと署名方式の詳細なパラメータ情報を統一フォーマットで提供し、セキュリティレベル分類によって異なるアルゴリズム間の比較を容易にしています。
このようなガイダンスドキュメントは、以下の理由から今後さらに価値が高まると考えられます。
移行期限の明確化:
NIST IR 8547が示す2035年の量子脆弱暗号使用禁止期限、そしてEUの段階的移行ロードマップ(高リスクは2031年、中・低リスクは2036年)により、実装者は具体的なタイムラインを持って移行計画を立てる必要があります。
選択肢の複雑さ:
NIST標準化アルゴリズムだけでも複数のパラメータセットがあり、さらにISO検討中のアルゴリズムを含めると選択肢は膨大です。統一された比較情報がなければ、適切な選択は困難になります。
相互運用性の確保:
異なる組織やプロトコルで異なるPQCアルゴリズムを採用した場合でも、パラメータサイズやセキュリティレベルの情報が共有されていれば、相互運用性を考慮した設計が可能になります。
PQUIP WGにおけるPQC統合の標準化活動の一環として、プロトコル設計者や実装者にとって有用なリファレンスとなるでしょう。ただし、"guidance"というタイトルが示す通り、規範的な要件ではなく情報提供や助言といったポジションでの目的としたドキュメントとして理解する必要があります。
参考文献
本ドキュメントが参照している主な標準文書:
- NIST FIPS 203 (ML-KEM) - 2024年8月
- NIST FIPS 204 (ML-DSA) - 2024年8月
- NIST FIPS 205 (SLH-DSA) - 2024年8月
- NIST SP 800-208 (LMS, XMSS) - 2020年10月/2024年8月
- NIST IR 8547 (PQC移行ガイダンス) - 2024年11月
- draft-ietf-pquip-pqt-hybrid-terminology-04 - 2024年9月
- draft-ietf-pquip-hbs-state-00 - 2025年6月
- EU PQC Roadmap - 2025年6月
本解説は2025年10月27日時点のdraft-prabel-pquip-pqc-guidance-01に基づいています。ドラフトは今後更新される可能性があり、最新版は https://datatracker.ietf.org/doc/draft-prabel-pquip-pqc-guidance/ で確認できます。
最後に、GMOコネクトでは研究開発や国際標準化に関する支援や技術検証をはじめ、幅広い支援を行っておりますので、何かありましたらお気軽にお問合せください。