【密码学百科】格密码数学基础：SVP、LWE 与格基约化
💡
原文中文，约20800字，阅读约需50分钟。
📝
内容提要
模格是后量子密码学的核心，NIST 2024年发布的标准中，ML-KEM和ML-DSA基于模格问题。理解模格的数学本质是掌握后量子密码的基础。文章讨论了模格的定义、困难问题及安全性评估，适合具备线性代数与概率论基础的读者。
🎯
关键要点
- 模格是后量子密码学的核心，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块大小。
- 格估计器是评估格密码安全性的标准工具，集成多种攻击算法的复杂度估计。
- 后量子密码正在加速进入生产环境，面临参数选取的动态调整压力。
❓
延伸问答
模格在后量子密码学中的作用是什么？
模格是后量子密码学的核心，NIST 2024年发布的标准中，ML-KEM和ML-DSA均基于模格问题。
什么是最短向量问题（SVP）？
最短向量问题（SVP）要求在给定的格基下找到一个非零格向量，使其长度最小。
LLL算法的主要功能是什么？
LLL算法用于将任意格基约化为'近似最短'的形式，是计算数论和密码分析的基础工具。
LWE问题在后量子密码学中的重要性是什么？
LWE问题的困难性与格问题的最坏情形相关，是后量子密码学中的重要问题。
格基约化的目标是什么？
格基约化的目标是将一组'坏'基变换为'好'基，以提高计算效率。
BKZ算法与LLL算法有什么区别？
BKZ算法通过在局部块上求解精确SVP来获得更好的全局约化质量，而LLL算法则是将任意格基约化为近似最短形式。
➡️
