暗号理論の論文でよく見るMenezesさん(権威)のYoutube動画に最近ハマってる。

視聴したメモ、そこから派生して気になったことなどをまとめる。

今回の動画

NIST標準アルゴリズム

2022年にNISTが耐量子計算機暗号(PQC)であるML-KEMとML-DSAを標準化した。

KEM（鍵共有）

KEM（Key Encapsulation Mechanism）は、共有鍵を「カプセル化」して相手に送る方式。
従来のDHやECDHの代替として使われる。

ML-KEM（CRYSTALS-Kyber）

NISTで標準化された格子ベースKEM。

  • ML-KEM-512 → Security Level 1（≒128bit安全性）
  • ML-KEM-768 → Security Level 3（≒192bit）
  • ML-KEM-1024 → Security Level 5（≒256bit）

よくAES256やRSA3072といったように、鍵長を付すことがあるのが、 ML-KEMにおける512/768/1024は鍵長ではなく行列のサイズである。
多項式の次数$n=256$は固定であり、可変パラメータは行列のサイズ$k$。
ML-KEM-512は$k=2$のため、$k\times n=512$となる。

Approved parameter sets for ML-KEM from NIPS203

鍵サイズや暗号文サイズは以下のとおりである。
鍵サイズの単位はBである

SchemeEncapsulation KeyDecapsulation KeyCiphertextShared Secret Key
ML-KEM-512800163276832
ML-KEM-76811842400108832
ML-KEM-102415683168156832
required RBG strengthとは

PQCに限った話ではないが、乱数生成が非常に重要である。
基本的にはNIST SP800-90やBIS AISのような暗号利用に適した方式で生成されたものを利用するべきである。

ML-KEMではセキュリティレベルに応じて乱数生成の強度が要求されている。
ML-KEM-512では少なくとも128ビット、ML-KEM-768では192ビット、ML-KEM-1024では256ビットのセキュリティ強度を持つ乱数生成器を利用するべきである。

過去の暗号実装においても、乱数生成の不備で秘密鍵が漏洩する事例が報告されているため、それも考慮して明示的に組み込まれたのかもしれない。（個人の推測）（日本とアメリカのチェックリストの違いみたいな）

署名

ML-DSA（CRYSTALS-Dilithium）

  • ML-DSA-44 → Level 2
  • ML-DSA-65 → Level 3
  • ML-DSA-87 → Level 5

ここでのパラメータ44や65は、行列の行数$k$と列数$\ell$を示している。

ML-DSA parameter sets from FIPS204 参照：FIPS-204

鍵サイズや署名サイズは以下のとおりである。
鍵サイズの単位はBである

SchemePrivate KeyPublic KeySignature Size
ML-DSA-44256013122420
ML-DSA-65403219523309
ML-DSA-87489625924627

その他（NIST標準・候補）

アルゴリズム種別ベース特徴
SLH-DSA (SPHINCS+)署名ハッシュベースステートレス、サイズ大
Falcon署名格子ベース高速・小サイズ、実装が難しい
LMS / XMSS署名ハッシュベースステートフル署名
HQCKEMコードベースNIST候補
FrodoKEMKEM格子ベース非構造格子（安全寄り）
Classic McElieceKEMコードベース鍵サイズが非常に大きい

PQCの実装エコシステム

Open Quantum Safe（OQS）

https://pqca.org/

Linux Foundationによって立ち上げられた、PQCの実用化を加速するためのプロジェクト。

PQCの実験・評価を目的としたOSSプロジェクト。
実質的なリファレンス環境。

liboqs

https://github.com/open-quantum-safe/liboqs QOSが規格した、複数のPQCアルゴリズムを統一APIで扱えるライブラリ。
アルゴリズム比較やプロトタイピングに便利。

PQCP（Post-Quantum Code Package）

https://github.com/pq-code-package

形式検証済みの高信頼実装。
プロダクション投入を前提とした品質。
検証されたコードはAWSなどの実運用に採用される。

SUPERCOP

暗号アルゴリズムの性能評価フレームワーク。

Curve25519で著名なdjb氏を中心としたベンチマークフレームワーク。

単にアルゴリズムを実装するのではなく、統一した測定環境・手順で性能を比較できる。
具体的には、異なるCPUアーキテクチャやコンパイラ環境に対して自動的にビルドと実行を行い、スループットやレイテンシを測定する。 これにより、例えば同じKyber実装でも、x86とARMでどの程度性能差があるか、あるいは最適化の効果がどれほどかを定量的に比較できる。

https://bench.cr.yp.to/results-kem.html

ライブラリ実装

近年、TLSでもx25519とML-KEMのハイブリッド方式が利用されている。

GoogleはMK-KEM768とx25519のハイブリッドを利用している GoogleはMK-KEM768とx25519のハイブリッドを利用している

Cloudflare Pagesで運用しているこのWebサイトもML-KEMのハイブリッド方式 CloudflareもML-KEMを利用(ワイのサイト)

これを実現するために多くの暗号ライブラリでPQCが実装されている。

OpenSSL（libcrypto）

https://github.com/openssl

有名な暗号ライブラリ。
デファクトスタンダードで、バグが発見されると大騒ぎになるやつ。

OepnSSL 3.5からPQCがサポートされた。
https://openssl-library.org/post/2025-04-08-openssl-35-final-release/

Bouncy Castle

https://github.com/bcgit

Java / C# / Kotlin向けの実用実装。 (初めて知りました…)

BoringSSL（Google）

https://github.com/google/boringssl

ChromeやAndroid用の内部で利用されている暗号ライブラリ。
API互換性が保証されていない一般用途には不向き、とのこと。

Chromium系のブラウザやAndroidのライセンスを見ると、 このライブラリが利用されている。
OpenSSLの表記はない。

chrome-using-boringssl

Firefoxでは Network Security Services (NSS) の freebl が暗号実装の中枢となっているようだ。

CIRCL（Cloudflare）

https://blog.cloudflare.com/introducing-circl/

Go製ライブラリ。
このWebサイトもきっとこれで動いている。

OpenSSLがPQC対応に遅かった2022年当初、CIRCLはいち早く実装していたと記憶する。
とくに標準化されていない同種写像系(SIDHやCSIDH)は私はCSIDHの高速化実装をやっていたときからすでにあった。
https://github.com/cloudflare/circl/tree/main/dh

AWS-LibCrypto + s2n-tls

https://github.com/aws/s2n-tls

AWSの暗号基盤。
クラウド規模でPQCハンドシェイクを実装。

CryptoKit（Apple）

https://developer.apple.com/documentation/cryptokit

X-WingというハイブリッドKEMがある。

詳しい解説記事がありました：
https://qiita.com/satokan3/items/eb91e759631c793845c9

wolfCrypt（組込み）

https://wolfssl.jp/products/wolfcrypt/

組み込み向け暗号ライブラリとして有名。

以前に業務でwolfCryptをリサーチしたことがあったが、FIPS対応版が欲しい場合にも対応できる、とのこと。
https://wolfssl.jp/products/wolfcrypt-fips/

プログラミング言語レベルでの対応

Java

JEP 496 , 497 により ML-KEM, ML-DSAが標準APIに統合されている。

Rust

RustCryptoなどで純Rust実装が進行。
メモリ安全性の観点で有利。

商用ライブラリ

OSSでは保証が不足するケース向けにFIPS等の認証を取得したライブラリ。

PQShield（PQCryptoLib-Core）

https://pqshield.com/products/pqc-cor/

FIPS 140-3認証済み。

ISARA（Radiate）

https://www.isara.com/products/isara-radiate-quantum-safe-toolkit.html

政府・金融向け統合ソリューション。

まとめ

既存の公開鍵暗号が解けるような量子コンピュータがすぐにできるかについては疑問が多いが、 不確実性に対処するためにPQCが研究・実装・発展することは良いと思う。
セキュリティ（特に暗号）については頭にアルミホイルを巻く勢いで徹底したほうがいいと思う。(小並感)

参考文献

  • National Institute of Standards and Technology (NIST),
    FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM),
    Federal Information Processing Standards Publication 203, 2024.
    DOI: https://doi.org/10.6028/NIST.FIPS.203

  • National Institute of Standards and Technology (NIST),
    FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA),
    Federal Information Processing Standards Publication 204, 2024.
    DOI: https://doi.org/10.6028/NIST.FIPS.204