格密码

约 560 字大约 2 分钟

2025-03-12

什么是格(Lattice)

在一个线性空间内确定两个线性无关向量，作为基底，它们进行线性组合后扫过的空间就是格。

在格密码中，我们一般设置基底前的系数为整数，因此形成的格都是离散的。

格在密码学中很有趣因为我们很少处理实数，而它们给我们提供了很多处理整数的工具。

就像向量空间一样，格也可以用不同的基表示为矩阵来描述。不过与矩阵表示习惯不同的是，我们在格理论中常把基向量作为矩阵的行向量。

下面定义一个格 L${\overrightarrow{b_1},\overrightarrow{b_2},\dots\overrightarrow{b_\omega}}$的行列式：

det(L):=\prod_{i=1}^{\omega}||\overrightarrow{b_i}||

~~(其实就是矩阵的行列式)~~

Lenstra-Lenstra-Lov´asz格基约简算法是一种一步一步的演算，可以在多项式时间内减少格基。晶格保持不变，但根据某些定义，其新基的行向量“更小”

Definition 1:设 L 是一个基 B 的格，在 L 的基 B 上应用 LLL 算法产生了 L 的一个新基: $B'=\{b1,\dots,b_n\}$ 满足以下条件：

\forall1\le j<i\le n~\text{有}~|\mu_{ij}|\le\frac{1}{2}\\ \forall1\le i<n~\text{有}~\delta\cdot||\overrightarrow{b_i}||^2\le||\mu_{i+1,i}\cdot\overrightarrow{b_i}+\overrightarrow{b_{i+1}}||\\ \text{同时}~\mu_{i,j}=\frac{b_i\cdot\overrightarrow{b_j}}{\overrightarrow{b_j}\cdot\overrightarrow{b_j}}~\text{且}~\overrightarrow{b_1}=b_1(\text{正交化})

LLL 给出了最短向量问题的近似解。这对我们很有用，因为如果我们把晶格基的行向量看作多项式的系数向量。我们可以找到系数“特别小”的多项式的线性组合。

设 L 是一个维数为 n 的格。在多项式时间内，LLL 算法输出约简基向量 $v_i$ ，对于 $1\le i\le n$ ，满足:

||v_1||\le||v_2||\le\dots\le||v_i||\le2^{\frac{n(n-1)}{4(n+1-i)}}\cdot det(L)^{\frac{1}{n+1-i}}

由此，我们可以通过修改格基的维数和行列式来修改向量的界。