理解 ML-KEM 與 ML-DSA 標準

理解 ML-KEM 與 ML-DSA 標準

1. 格點密碼學的興起

目前主導實務標準化的是格點基礎 (Lattice-based) 系統。這是因為從最壞情況 (worst-case) 到平均情況 (average-case) 存在強大的數學還原 (reductions)，且能進行高效實作 [S4]。另一方面，基於代碼 (Code-based) 或基於雜湊 (Hash-based) 的方式扮演著保守錨點 (conservative anchors) 的角色，具有更長的安全歷史或僅需最小化假設的特性 [S4]。

2. ML-KEM (Module-Lattice Key Encapsulation Mechanism)

ML-KEM 基於先前稱為 Kyber 的演算法。基於模組格點問題 (Module Learning With Errors, MLWE)，運作流程如下：

• KeyGen: 在模組格點內產生公開金鑰與私密金鑰。
• Encapsulation: 使用公開金鑰產生共享秘密值 (Shared Secret) 與封裝後的金鑰 (Ciphertext)。
• Decapsulation: 使用私密金鑰從封裝後的金鑰還原原始共享秘密值。

3. ML-DSA (Module-Lattice Digital Signature Algorithm)

ML-DSA 基於 Dilithium，使用「Fiat-Shamir with Aborts」技術。透過格點問題的困難度提供抗偽造性，是在簽章大小與公開金鑰大小之間取得平衡的實務標準。

4. 安全假設

格點基礎系統的安全性與尋找最短向量問題 (Shortest Vector Problem, SVP) 密切相關。與量子電腦的「Shor 演算法」能有效破解現有的 RSA 或 ECC 不同，格點問題被假設即使使用量子演算法也無法在多項式時間內求解。