在密码学从 “传统抗经典计算” 向 “后量子抗量子计算” 演进的过程中，格（Lattice）凭借其独特的数学结构与计算困难性，成为支撑新一代安全算法的核心理论基础。从基于格的数字签名到加密方案，几乎所有后量子密码学（PQC）的实用化方案，其安全性都根植于格的数学特性。要理解这类算法的本质，需先揭开格的数学面纱。
一、格的直观认知与严格定义
格是一种贯穿 “几何直观” 与 “代数结构” 的数学对象，其核心是 “离散点集” 与 “线性组合” 的结合。
1. 从二维网格到 n 维格：直观理解
最朴素的格是二维平面上的 “整数网格”—— 以 (1,0) 和 (0,1) 为 “基准向量”，通过整数系数的线性组合（如 a×(1,0)+b×(0,1)，a、b 为整数）生成的所有点 (x,y)，构成了我们熟悉的平面整数点集。但格的范围远不止于此：
若基准向量变为 (1,1) 和 (0,1)，生成的点集仍是离散的（如 (0,0)、(1,1)、(0,1) 等），但点的分布密度与前者不同；
扩展到三维空间，以 (1,0,0)、(0,1,0)、(0,0,1) 为基，可生成三维整数格，即所有坐标为整数的三维点；
进一步推广到 n 维欧几里得空间（ℝⁿ），就形成了密码学中研究的 “高维格”—— 虽无法直观可视化，但其核心逻辑与二维、三维格一致。
简言之，格的本质是 “由一组基向量通过整数线性组合生成的离散点集”，其结构由 “基向量” 决定。
2. 格的严格数学定义
在数学中，格的定义可精确表述为：
设b₁, b₂, ..., bₙ是 n 维欧几里得空间ℝⁿ中一组线性无关的向量（称为 “格的基”，记为 B = {b₁, b₂, ..., bₙ}），则由这组基生成的格 Λ(B) 是所有整数线性组合构成的点集：
Λ(B) = { x₁b₁ + x₂b₂ + ... + xₙbₙ | x₁, x₂, ..., xₙ ∈ ℤ }
其中关键术语解析：
基（Basis）：格的 “生成元”，一组线性无关的向量，决定格的结构与分布；
维数（Dimension）：基向量的个数，即格所在空间的维数（n），密码学中常用高维格（n 通常≥256）；
离散性（Discreteness）：格中任意两个不同点的距离都有下限（不存在无限靠近的点），这是格区别于其他点集的核心特性；
周期性（Periodicity）：以基向量为周期，格的结构在空间中重复出现。
3. 格的基：短基与长基的关键差异
格的基并非唯一 —— 同一格可以由多组不同的基生成。例如二维格 Λ 既可以由基 B₁={(1,0), (0,1) } 生成，也可以由基 B₂={ (1,1), (0,1) } 生成。但不同基的 “向量长度” 差异极大，这一差异正是密码学的核心切入点：
短基（Short Basis）：基向量的长度（通常用欧几里得范数 ||・||₂衡量，即向量各分量平方和的平方根）较短，例如 B₁的基向量长度均为 1；
长基（Long Basis）：基向量的长度较长，例如将 B₁的基向量缩放 100 倍得到的基 {(100,0), (0,100) }，就是 Λ 的长基。
在密码学中，短基通常作为私钥的核心素材（拥有短基可高效完成签名、解密等操作），而长基或基于基生成的公开参数（如矩阵）则作为公钥—— 这种 “短基难寻、长基易获” 的不对称性，构成了格密码算法的安全基础。
二、格的核心数学性质：密码学应用的关键
格的数学性质中，有三类特性对密码学至关重要，它们直接决定了基于格的算法为何能抵抗量子计算攻击。
1. 基的等价性与转换难题
同一格的不同基之间存在 “等价关系”，但从一组基转换到另一组基的难度差异巨大：
若已知格的一组基 B，可通过 “初等基变换”（如交换基向量、给某基向量加上另一基向量的整数倍）生成新的基；
但从长基转换到短基是计算上困难的问题—— 即使知道格的长基，在高维空间中寻找短基，目前尚无高效算法（包括量子算法）。
这一性质直接对应密码学中的 “密钥生成逻辑”：公钥公开长基相关信息，私钥持有短基，攻击者无法从公钥推导出私钥，因为这需要解决 “长基转短基” 的困难问题。
2. 短向量问题：格密码的安全性根源
格中 “寻找短向量” 的系列问题，是所有基于格的密码算法安全性的 “归约目标”—— 即算法的安全性可严格证明为 “与寻找短向量的困难性等价”。其中最核心的两类问题是：
（1）最短向量问题（Shortest Vector Problem, SVP）
给定格 Λ 的基 B，寻找 Λ 中一个非零向量 v，使得 v 的长度 ||v||₂在 Λ 的所有非零向量中最短。
例如在二维格 Λ(B₁) 中，最短非零向量是 (1,0) 或 (0,1)，长度为 1；但在高维格中，SVP 变得极其困难 —— 随着维数 n 的增加，可能的向量组合呈指数级增长，即使量子计算机也无法在多项式时间内找到最短向量。
（2）最近向量问题（Closest Vector Problem, CVP）
给定格 Λ 的基 B 和一个不属于 Λ 的目标向量 t ∈ ℝⁿ，寻找 Λ 中一个向量 v，使得 v 与 t 的距离 ||v - t||₂最小。
CVP 可理解为 “格版本的 nearest neighbor 问题”，其困难性与 SVP 紧密相关 —— 解决 CVP 的高效算法通常也能用于求解 SVP，反之亦然。
在密码学中，SVP 和 CVP 的 “计算困难性” 是抵御攻击的核心：攻击者要破解算法，就必须求解这两类问题，而目前尚无任何量子算法能高效完成。
3. 格的离散性与紧致性
格的 “离散性”（点与点之间有最小距离）使其天然适合密码学中的 “随机性与确定性结合” 需求：
离散性确保格中的向量具有 “明确的整数特性”，可与模运算（如模素数 q）结合，构建满足 “有限域约束” 的密码方案；
同时，高维格的 “紧致性”（点集在空间中密集分布但仍离散）使得 “在格中嵌入秘密信息” 成为可能 —— 例如将明文编码为格中的向量，通过加密算法映射到另一个格向量，解密时再利用短基找回原始向量。
三、格与密码学的桥梁：核心困难问题变体
为适配不同密码算法（签名、加密、密钥交换）的需求，研究者基于 SVP 和 CVP，提出了两类更易工程实现的格困难问题变体，它们是当前后量子密码标准的核心：
1. 小整数解问题（Short Integer Solution, SIS）
问题描述：给定一个矩阵 A ∈ ℤ_q^(n×m)（q 为素数，n、m 为正整数）和一个小常数 β，寻找一个非零向量 x ∈ ℤ^m，满足：
A・x ≡ 0 mod q（向量乘积模 q 为零向量）；
||x||_∞ ≤ β（x 的无穷范数，即各分量绝对值的最大值不超过 β）。
与格的关联：矩阵 A 可视为格的 “公开基相关参数”，条件 1 定义了一个子格，条件 2 要求 x 是该子格中的 “短向量”—— 求解 SIS 本质上是在高维子格中寻找短向量，其困难性可归约到 SVP。
密码学应用：主要用于构造数字签名算法（如 Dilithium）—— 签名过程本质是生成满足 SIS 约束的短向量，验证过程则是检查该向量是否满足约束。
2. 学习错误问题（Learning With Errors, LWE）
问题描述：给定一个矩阵 A ∈ ℤ_q^(n×m)、一个秘密向量 s ∈ ℤ_q^n、一个服从 “小错误分布” 的向量 e ∈ ℤ_q^m，以及向量 b = A・s + e ∈ ℤ_q^m（b 是 A 与 s 的乘积加上小错误 e）。任务是从已知的 (A, b) 中恢复秘密向量 s。
与格的关联：b = A・s + e 可视为 “目标向量 t”，秘密 s 对应格中的某个向量，e 是 “小扰动”—— 求解 LWE 需在格中找到与 b 最接近的向量（即 CVP 的变体），其困难性同样归约到 SVP。
密码学应用：主要用于构造加密算法和密钥交换协议 —— 加密时将明文与错误向量结合，解密时利用私钥（短基）抵消错误，恢复明文。为提升效率，研究者还提出了 “环 LWE（Ring-LWE）” 和 “模块 LWE（Module-LWE）” 变体，通过多项式环运算降低计算复杂度。
四、格作为数学基础的核心价值：为何选择格？
在众多后量子密码候选方向（如基于编码、哈希、多变量多项式）中，格能成为最成熟的方案，根源在于其数学基础的独特优势：
1. 强量子抗性
格的核心困难问题（SVP、CVP、SIS、LWE）均被证明 “不存在多项式时间的量子算法”—— 这与传统密码依赖的 “大整数分解”“离散对数” 问题形成鲜明对比（后者可被 Shor 量子算法破解）。这种 “量子抗性” 是格成为后量子密码基石的根本原因。
2. 可证明安全性
基于格的密码算法，其安全性可 “严格归约” 到格的基础困难问题（如 SIS 的安全性等价于 SVP 的困难性），而非依赖 “经验性假设”（如 RSA 的安全性仅假设 “大整数分解困难”，未被严格归约）。这种 “可证明安全” 大幅降低了潜在安全风险，为算法的长期可靠性提供保障。
3. 结构灵活性
格的数学结构可轻松适配不同密码需求：
通过调整维数 n、模数 q、错误分布等参数，可灵活调节安全级别（从抵抗经典计算到抵抗超级量子计算机）；
基于格可构造几乎所有密码原语，包括签名、加密、密钥交换、盲签名、群签名等，而其他后量子方向（如基于哈希的签名）在扩展高级功能时难度极大。
4. 工程实现可行性
尽管格是高维数学对象，但通过 Ring-LWE、Module-LWE 等变体，以及快速多项式乘法（如 FFT）等优化技术，基于格的算法已能实现工程化落地 —— 例如 NIST 选定的 Dilithium 签名算法，其密钥长度、签名速度已能满足多数实际场景需求。
五、总结
格作为一种兼具几何直观与代数严谨性的数学对象，其 “基的转换难题” 与 “短向量问题的计算困难性”，为后量子密码算法提供了坚实的数学根基。从二维网格的简单概念，到高维格的复杂结构；从 SVP、CVP 的理论难题，到 SIS、LWE 的工程化变体，格的数学特性与密码学需求形成了完美契合。
正是这种 “数学基础扎实、安全可证、量子抗性强、工程可实现” 的综合优势，使格成为后量子密码学的核心支柱，支撑起未来信息安全的底层逻辑。理解格的数学本质，便理解了后量子密码算法为何能成为抵御量子攻击的 “安全盾牌”。
