【密码学百科】格密码数学基础：SVP、LWE 与格基约化

模格是后量子密码学的核心，NIST 2024年发布的标准中，ML-KEM和ML-DSA基于模格问题。

理解模格的数学本质是掌握后量子密码的基础。

文章讨论了模格的定义、困难问题及安全性评估，适合具备线性代数与概率论基础的读者。

格的定义是由一组线性无关的向量生成的离散加法子群。

格基的非唯一性意味着同一格可以有无数组不同的基。

格基约化的目标是将一组'坏'基变换为'好'基。

最短向量问题（SVP）和最近向量问题（CVP）是格密码学的经典困难问题。

量子计算对格问题的影响尚未明确，格密码成为后量子候选方案的核心理由。

LLL算法用于将任意格基约化为'近似最短'的形式，是计算数论和密码分析的基础工具。

BKZ算法通过在局部块上求解精确SVP来获得更好的全局约化质量。

LWE问题是后量子密码学中的重要问题，其困难性与格问题的最坏情形相关。

Ring-LWE和Module-LWE是LWE的变种，旨在提高效率和安全性。

NIST选择基于Module-LWE的ML-KEM作为首要密钥封装机制，因其安全假设更为保守。

格密码的安全性评估通常采用Core-SVP方法论，评估攻击所需的BKZ块大小。

格估计器是评估格密码安全性的标准工具，集成多种攻击算法的复杂度估计。

后量子密码正在加速进入生产环境，面临参数选取的动态调整压力。