格密码笔记四

一、格

设 $v_{1}, \dots, v_{n} \in R^{m}$ 是线性无关向量组。称 v1,…,vn 生成(generate) 了 lattice L：

$L = a_{1} v_{1} + a_{2} v_{2} + \dots + a_{n} v_{n} : a_{1}, a_{2}, \dots, a_{n} \in Z$

即 L 中的元素是 $v_{1}, \dots, v_{n}$ 的整系数线性组合

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

二、lattice 中基的关系

假设 $v1,…,v_n $是 l a t t i c e L 的一个基，而$ w_1,…,w_n $是 L 中的一个向量组。将 w j 表示成 v i 的线性组合：$ 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_{i j}$ 全部是整数

用 $w_{j}$ 来组合出 $v_{i}$

U= $(\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix})$

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

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

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

例如， $Z^{n} = (x_{1}, x_{2}, \dots, x_{n}) : x_{1}, \dots, x_{n} \in 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{matrix} 2 & 1 & 3 \\ 1 & 2 & 0 \\ 2 & - 3 & - 5 \end{matrix})$

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

$w_{1} = v_{1} + v_{3}, w_{2} = v_{1} - v_{2} + 2 v_{3}, w_{3} = v_{1} + 2 v_{2}$

于是有变换矩阵

U= $(\begin{matrix} 1 & 0 & 1 \\ 1 & - 1 & 2 \\ 1 & 2 & 0 \end{matrix})$

从而可以计算出 $w_{1}, w_{2}, w_{3}$

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

我们注意到 U 的行列式是 −1，从而 $w_{1}, w_{2}, w_{3}$ 也是 L 的一个基。现在利用 $w_{j}$ 来组合出 $v_{i}$ ，系数是 U 的逆矩阵：

$U^{- 1}$ = $(\begin{matrix} 4 & - 2 & 1 \\ - 2 & 1 & 1 \\ - 3 & 2 & 1 \end{matrix})$

有 $v_{1} = 4 w_{1} - 2 w_{2} - w_{3}$ 。

python

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 \subset R^{m}$ 是一个 n 维的 lattice，那么它的一个基可以被写成 n×m 矩阵 A.

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

三、几何意义上的 lattice

加法子群(additive subgroup)：Rm 的一个子集 L，它是加法子群当且仅当其在加法、减法运算上封闭。离散加法子群(discrete additive subgroup) ：一个加法子群 L 为离散加法子群，当且仅当存在一个正的常数 $ϵ > 0 ，使得 \forall v \in L, L \cap w \in 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}, \dots, v_{n}$ 是一个基。则 L 对应这一组基的基本域是 $F (v_{1}, \dots, v_{n}) = t_{1} v_{1} + t_{2} v_{2} + \dots + t_{n} v_{n} : 0 \leq t_{i} \leq 1$

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

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

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

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

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

(Hadamard 不等式)：设 L 是一个 lattice，取其任意一个基 $v_{1}, \dots, v_{n}$ ，设 F 是 L 的一个基本域。那么有 $d e t L = V o l (F) \leq ‖ v_{1} ‖ ‖ v_{2} ‖ \dots ‖ v_{n} ‖$

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

$L \subset R^{n}$ 的维度恰等于 n 时的行列式

设 L⊂Rn 是一个 n 维 lattice，设 $v_{1}, \dots, 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 的协体积：

$V o l (F (v_{1}, \dots, v_{n})) = | d e t F |$

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

例如：之前代码里面的 lattice L，其协体积为 $d e t L = | d e t A | = | d e t$ $(\begin{matrix} 2 & 1 & 3 1 & 2 & 0 2 & - 3 & - 5 \end{matrix})$ |=|−36|=36

python

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)

格密码笔记四

一、格

二、lattice 中基的关系

三、几何意义上的 lattice

微信扫一扫：分享