格密码笔记四

一、格

设$v_1,…,v_n∈R^m$ 是线性无关向量组。称 v1,…,vn 生成(generate) 了 lattice L：

$L={a_1v_1+a_2v_2+⋯+a_nv_n:a_1,a_2,…,a_n∈Z}$

即 L 中的元素是 $v_1,…,v_n$ 的整系数线性组合

基所包含的的向量个数称为 L 的纬度(dimension)

二、lattice 中基的关系

假设 $v1,…,v_n$ 是 lattice L 的一个基，而$ w_1,…,w_n$ 是 L 中的一个向量组。将 wj 表示成 vi 的线性组合：$w_1=a{11}v1+a{12}v2+⋯+a{1n}v_n$

$w2=a{21}v1+a{22}v2+⋯+a{2n}v_n$

⋮ ⋮

$wn=a{n1}v1+a{n2}v2+⋯+a{nn}v_n$

系数 $a_{ij}$ 全部是整数

用 $w_j$ 来组合出 $v_i$

U= $\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{pmatrix}$

显然 U⋅V=W，于是利用 $w_i$ 表达$ v_i$，系数是 $U^{−1}W$。但 lattice 中，线性组合的系数必须全都是整数，于是$U^{−1}$ 里面的元素也必须全部是整数。

由$1=det(I)=det(UU^{−1})=det(U)det(U^{−1})$，由行列式的定义式可以看出，如果一个矩阵元素全部是整数，那么行列式也必然是整数。从而$ det(U),det(U^{−1})$ 都是整数，而它们的乘积为 1。

lattice L 的任意两个基，其基变换矩阵中的元素均为整数，且行列式为 ±1.

例如，$Z^n={(x_1,x_2,…,x_n):x_1,…,x_n∈Z}$是包含了所有整数坐标向量的 lattice.

整格(integral lattice)：一个 integral(or integer) lattice，是指所包含的向量都拥有整数坐标的 lattice。或者说，一个 integral lattice，是 $Z^m$ 加法群的一个子群。

例如，$ L：v_1=(2,1,3),v_2=(1,2,0),v_3=(2,−3,−5)$

把它们作为行向量，写成矩阵：

A= $\begin{pmatrix} {2}&{1}&{3}\\ {1}&{2}&{0}\\ {2}&{-3}&{-5}\\ \end{pmatrix}$

接下来考虑 L 中的另一个向量组：

$w_1=v_1+v_3,w_2=v_1−v_2+2v_3,w_3=v_1+2v_2$

于是有变换矩阵

U= $\begin{pmatrix} {1}&{0}&{1}\\ {1}&{-1}&{2}\\ {1}&{2}&{0}\\ \end{pmatrix}$

从而可以计算出 $w_1,w_2,w_3$

B=UA= $\begin{pmatrix} {4}&{-2}&{-2}\\ {5}&{-7}&{-7}\\ {4}&{5}&{3}\\ \end{pmatrix}$

我们注意到 U 的行列式是 −1，从而 $w_1,w_2,w_3$ 也是 L 的一个基。现在利用 $w_j$ 来组合出$ v_i$，系数是 U 的逆矩阵：

$U^{−1}$= $\begin{pmatrix} {4}&{-2}&{1}\\ {-2}&{1}&{1}\\ {-3}&{2}&{1}\\ \end{pmatrix}$

有 $v_1=4w_1−2w_2−w_3$。

v1 = [2, 1, 3]
v2 = [1, 2, 0]
v3 = [2, -3, -5]

A = matrix([v1, v2, v3])
print(A)
# [ 2  1  3]
# [ 1  2  0]
# [ 2 -3 -5]

U = matrix([[1, 0, 1], [1, -1, 2], [1, 2, 0]])
print(U)
# [ 1  0  1]
# [ 1 -1  2]
# [ 1  2  0]
print(U.det())
# -1

B = U*A
print(B)
# [ 4 -2 -2]
# [ 5 -7 -7]
# [ 4  5  3]

inv_U = U.inverse()
print(inv_U)
# [ 4 -2 -1]
# [-2  1  1]
# [-3  2  1]

assert inv_U * B == A

总结

1、若 $L⊂R^m$ 是一个 n 维的 lattice，那么它的一个基可以被写成 n×m 矩阵 A.

2、L 的另一个基，可以通过 A 左乘一个 n×n 的基变换矩阵来得到，其中 U 必须是整系数矩阵，且行列式为 ±1. 满足这种条件的 U，称为 Z 上的一般线性群(general linear group)，记为$ GL_n(Z)$。它是满足“逆矩阵也为整系数矩阵”的整系数矩阵的群。

三、几何意义上的 lattice

加法子群(additive subgroup)：Rm 的一个子集 L，它是加法子群当且仅当其在加法、减法运算上封闭。离散加法子群(discrete additive subgroup) ：一个加法子群 L 为离散加法子群，当且仅当存在一个正的常数 $ϵ>0，使得∀v∈L,L∩{w∈R^m:‖v−w‖<ϵ}={v}$

上面这个式子的几何意义是：对于 L 中的每一个点 v，其附近 ϵ 的（欧几里得）距离范围内，不存在 L 的其他点。也就是说 L 是离散的，每两个点之间的距离都不小于某个（足够小的）ϵ.

格(lattice) 一个 Rm 的子集是 lattice，当且仅当它是离散加法子群。

一个 lattice 与线性空间是非常相似的，除了 lattice 必须由 basis 的整系数线性组合来生成，而线性空间可以用任意实数作为线性组合系数。lattice 可以视为 Rm 上的离散点集。
基本域的概念

基本域(fundamental domain, fundamental parallelepiped)：
设 L 是一个 n 维 lattice，$v_1,…,v_n$ 是一个基。则 L 对应这一组基的基本域是$F(v_1,…,v_n)={t_1v_1+t_2v_2+⋯+t_nv_n:0≤t_i≤1}$

几何上，基本域就是这组基围出的区域.

设 $L⊂R^n$ 是一个 n 维 lattice，F 是 L 的一个基本域。那么对于所有 $w∈R^n$，它都可以写成如下形式:$w=t+v$ for a unique t∈F and a unique v∈L。

这里的 t,v 都是唯一的。$F+v={t+v:t∈F}$在 v 取遍 L 中的每一个点时，恰好覆盖了整个 Rn。

L 的所有基本域，体积都是一样的

将 lattice 的协体积视为 $basis\ v _1,…,v_n $所围成的平行体 F 的协体积，若这些基向量长度固定的话，想要得到最大的协体积，必然各个向量之间都要正交（类比于，相同长度的四条线段围成平行四边形，当其恰好为正方形的时候面积最大）。于是我们得到了 lattice 协体积的上限：

(Hadamard 不等式)：设 L 是一个 lattice，取其任意一个基 $v_1,…,v_n$，设 F 是 L 的一个基本域。那么有$det\ L=Vol(F)≤‖v_1‖‖v_2‖⋯‖v_n‖$

其中，basis 的各个向量越像正交的，则协体积越接近上限。当 basis 各个向量恰好正交时，上面的 Hadamard 不等式取到等号。

$ L⊂R^n$ 的维度恰等于 n 时的行列式

设 L⊂Rn 是一个 n 维 lattice，设 $v_1,…,v_n$ 是基，F 是对应的基本域。

接下来我们写出各个基向量的坐标：

$vi=(r{i1},r{i2},…,r{in})$
把这些坐标写进矩阵里面：

$F=F(v1,…,v_n)$=$$\begin{pmatrix}
{r{11}}&{r{12}}&{\cdots}&{r{1n}}\
{r{21}}&{r{22}}&{\cdots}&{r{2n}}\
{\vdots}&{\vdots}&{\ddots}&{\vdots}\
{r{n1}}&{r{n2}}&{\cdots}&{r{nn}}\
\end{pmatrix}$$

则可以如下计算 F 的协体积：

$Vol(F(v_1,…,v_n))=|detF|$

如果 lattice 的维度与空间的维度恰好相等，则只需要计算基向量的系数矩阵的行列式，即可得到 lattice 的协体积。

例如：之前代码里面的 lattice L，其协体积为$detL=|detA|=|det$$\begin{pmatrix}
{2}&{1}&{3}\
{1}&{2}&{0}\
{2}&{-3}&{-5}\
\end{pmatrix}$|=|−36|=36

print(A)
# [ 2  1  3]
# [ 1  2  0]
# [ 2 -3 -5]
print(A.det())
# -36

print(B)
# [ 4 -2 -2]
# [ 5 -7 -7]
# [ 4  5  3]
print(B.det())
# 36

从一道CTF题初探NTRU格密码 - 先知社区 (aliyun.com)