基于格的密码学

基于格的密码学

1. 数学定义

在数学中，格是由一组线性无关向量，通过整数线性组合生成的点集。

给定基向量 b1,b2,…,bn∈Rm\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_n \in \mathbb{R}^m

格定义为： L(B)={∑i=1nzibi∣zi∈Z}\mathcal{L}(\mathbf{B}) = \left\{ \sum_{i=1}^n z_i \mathbf{b}_i \mid z_i \in \mathbb{Z} \right\}

直观理解

  • 在 2D：像无限延伸的“网格点”
  • 在 256 维 / 1024 维：无法可视化的高维结构
  • 同一个格可以有 无数种不同的基表示

2. “好基”和“坏基”

这是格密码学的关键直觉。

  • 好基：向量短、接近正交
  • 坏基：向量长、彼此夹角小、严重纠缠

但重要的是：

给定一个格，你很难从坏基计算出好基

这正是安全性的来源之一。

二、格密码的核心困难问题

1. SVP（Shortest Vector Problem）

最短向量问题

在一个格中，找到除零向量外长度最短的向量。

  • 在高维下是 NP-hard
  • 即使近似版本也极其困难

2. CVP（Closest Vector Problem）

最近向量问题

给定一个点，找到格中距离它最近的向量。

  • 比 SVP 更难
  • 破解很多格密码等价于解决 CVP

3. 为什么量子计算也帮不上忙？

  • Shor 算法只适用于：

    • 整数分解
    • 离散对数

  • 对 SVP / CVP：

    • 没有已知的多项式时间量子算法
    • 最优量子算法只提供多项式或常数级改进

三、从“纯格问题”到“可用密码”：LWE

直接用 SVP/CVP 太抽象，工程上不可用，于是引入：

1. LWE（Learning With Errors）

定义（核心）

给定若干样本： (ai,bi=⟨ai,s⟩+ei) mod q(\mathbf{a}_i, b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i) \bmod q

其中：

  • ai\mathbf{a}_i：随机向量
  • s\mathbf{s}：秘密向量
  • eie_i：小噪声
  • qq：模数

攻击者目标：

从这些样本中恢复 s\mathbf{s}

2. 为什么 LWE 很难？

  • 如果 没有噪声：

    • 线性方程组 → 高斯消元直接解

  • 加入噪声后：

    • 每个方程都“差一点”
    • 高维空间中误差指数级放大

关键定理（Regev, 2005）：

平均情况下的 LWE 问题 ≥ 最坏情况下的格问题（SVP/CVP）

这是密码学中极其重要的“最坏情况归约”。

3. 噪声是安全性的灵魂

  • 噪声太小 → 可线性求解
  • 噪声太大 → 解密失败
  • 工程上精确控制噪声分布（通常是离散高斯）

四、Ring-LWE / Module-LWE：工程化优化

1. 为什么需要 Ring-LWE？

原始 LWE 问题：

  • 向量维度大
  • 公钥、密文体积巨大
  • 计算慢

Ring-LWE 的改进

将向量换成多项式：

Zq[x]/(xn+1)\mathbb{Z}_q[x] / (x^n + 1)

  • 向量 → 多项式
  • 内积 → 多项式乘法
  • 可用 FFT / NTT 加速

2. Module-LWE（现代主流）

Module-LWE 介于：

  • LWE（安全性高，但慢）
  • Ring-LWE（效率高，但结构强）

Kyber、Dilithium 使用 Module-LWE

优势：

  • 平衡安全性与效率
  • 更易参数化
  • 抗结构攻击能力更强

五、基于格的密钥交换：KEM 原理

以 Kyber 为例说明。

1. 基本思想

  • 公钥中包含一个“带噪声的线性关系”
  • 私钥是噪声和秘密
  • 解密方可以“近似恢复”共享密钥
  • 攻击者无法消除噪声

2. 高层流程（简化）

KeyGen

  • 生成秘密多项式 ss
  • 生成噪声 ee
  • 公钥：A⋅s+eA \cdot s + e

Encapsulate

  • 生成随机消息 mm
  • 用公钥计算密文（再次引入噪声）
  • 从 mm 派生共享密钥

Decapsulate

  • 使用私钥消噪
  • 近似恢复 mm
  • 派生相同密钥

3. “近似正确”是允许的

  • 解密不是精确计算
  • 而是“在噪声容忍区间内”
  • 通过取整 / 比较阈值恢复比特

六、为什么基于格的算法“天生抗量子”

总结关键原因：

1. 数学问题不同

传统密码格密码
因数分解高维几何
离散对数噪声线性代数
代数结构强统计结构复杂

2. 无已知量子特攻算法

  • Shor 不适用
  • Grover 仅提供搜索加速
  • 目前最优攻击仍是 BKZ（经典/量子）

3. 安全性有理论背书

  • 最坏情况 → 平均情况归约
  • 非经验假设
  • 学术界信心高

七、工程层面的代价与挑战

1. 密钥和密文更大

  • ECC 公钥：32~64 字节
  • Kyber 公钥：800~1500 字节

2. 实现复杂

  • 噪声采样
  • 常数时间实现
  • 防侧信道攻击

3. 参数必须非常谨慎

  • 噪声分布
  • 模数选择
  • 维度选择
× Preview