lattice_learning

发表于 2021-07-27 更新于 2021-08-30 分类于 Crypto 阅读次数： Waline：本文字数： 1k 阅读时长 ≈ 1 分钟

有关格理论的学习记录。

格的定义

格的定义可以从向量空间引申出来：

一组线性无关的的向量v1，v2，...，vn，它们的线性组合a1v1+a2v2+...+anvn可以
表示一个空间，如果a1,a2，...，an全为整数，则生成了一个格L。则这组向量称为
格的基，向量个数称为格的维数。

基础区域

格的基础区域为即当a1，an，,,,，an为0或1组成的一个区域。格中任意一个向量可以由格的基础区域和唯一格外的一个向量表示。基础区域是格很重要的概念。

格的行列式

格的行列式就是基础区域的n维体积，记作： \[ det(L) \]

基的转换

设以v1，v2，...，vn为行向量构成的n阶矩阵为A，某一行列式等于1的n阶矩阵为 U，则矩阵B=UA中的行向量也是格L的一组基。从线性变换的本质来看，线性变换是对空间进行伸缩或者翻转的操作（可惜大多数高校的非数学专业是不会讲这些的，具体可以看b站3b1b的搬运，有关线性代数的本质的介绍，可以给我们很直观的理解），由于U的行列式为1，那么变换后的基础区域体积不变。

格的两大难题

均为NP完全问题

最短向量问题

简称SVP，在格中寻找一个非零向量，使它的范数最小。

重要定理

Hadamard不等式

格L的基础区域为F，对于它任意一个基 \[ v_1,v_2,...,v_n \]

有： \[ det(L)=vol(F)\leq||v_1||*||v_2||*...*||v_n|| \] 基向量越接近正交，则上式越接近等式

Hadamard比率

\[ H(L)=(\frac{det(L)}{||v_1||*||v_2||*...*||v_n||})^{1/n} \]

当这个值越接近1，则基越接近两两正交

Hermite定理

所有n维的格L都包含一个非0向量 \[ v\in L，满足||v||\leq\gamma_ndet(L)^{1/n} \] 对于给定的维度n \[ Hermite常量\gamma_n是一个最小值， \] 它可以使所有n维格L都包含非零向量 \[ v\in L满足上式。 \] 其中Hertmite常量 \[ \gamma_n满足：\frac{n}{2Πe}\leq\gamma_n\leq\frac{n}{Πe} \]

Minkowski定理

\[ 设L\subset R^n是一个n维的格，S\subset R^n是一个对称凸面集合，其体积满足： \]

\[ vol(S)>2^ndet(L)$ \]

如果S满足封闭性，则上式等式成立。