格密码

因为学习背包密码的过程中发现涉及格的知识但是我还不会，恶补一下知识

主要看到是dexterjie的笔记

定义

给定$n$维空间中$n$个线性无关向量：$\vec{b_1},\vec{b_2},…,\vec{b_n}$,并把这$n$个向量称为基。

这组向量存在线性组合$x_1\vec{b_1}+x_2\vec{b_2}+…+x_n\vec{b_n}$

把整系数的线性组和构成的集合称为格即$x_i\in \mathbb{Z} $

记为：$\mathcal{L}(b_1, b_2, \ldots, b_n) = {\Sigma x_i b_i \mid x_i \in \mathbb{Z}}$

格基的等价变换

顾名思义这些变换产生的格基形成的格都是一样的

列向量交换，即$\vec{b_i} \longleftrightarrow \vec{b_j}$
向量取反，即$\vec{b_i}\longleftrightarrow -\vec{b_i}$
整系数线性组合，即$\vec{b_i}\longleftrightarrow \vec{b_i}+k\vec{b_j}$

->两个格基产生相同格的条件

如果格基矩阵$B_1,B_2$满足$B_2=B_1U$则两格基产生的格是一样的

什么样的向量集可以构成格的“basis”

先认识一个引理

引理 1. 设 $\Lambda$ 为秩 $n$ 的格，设 $b_1, b_2, \dots, b_n \in \Lambda$ 为 $n$ 个线性无关的格向量。$b_1, b_2, \dots, b_n$ 表示为 $\Lambda$ 的 “basis”，当且仅当 $\mathcal{P}(b_1, b_2, \dots, b_n) \cap \Lambda = {0}$。

根据引理

就是生成的基本趋于不包含除了原点外的任何格点。

格的基本区域

给定格基$B$产生的格，可以确定基础平行多面体

设为$\mathcal{P(B)}$

$\mathcal{P(B)}={a_1\vec{b_1}+a_2\vec{b_2}+…+a_n\vec{b_n}|(0\leq a_i<1)}$

可以理解成最小重复单元

在一个基本区域中，不存在两个等价的点

灰色区域就是这个格的基本区域

当把在每个格点放置一个基本区域，就会铺满整个空间。

行列式

格的行列式指的是基本区域的体积

行列式越小，格点的密度越大

延展空间

格$\mathcal{L}(B)$中基向量的所有线性组和形成的集合，就是这组基向量所张成的空间（SPAN）

$span(\mathcal{L}(B)=span(B)={By|y\in \mathbb R^n})$

施密特正交化

GSO(Gram-Schmidt Orthogonalization)，施密特正交化

GSO 是线性代数^★中的一个基本运算过程，它接受任意一组 $ n $ 个线性无关向量 $ b_1, b_2, \dots, b_n $，并以此向量组创建新的一组 $ n $ 个正交向量 $ \tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_n $。

对于$n$个线性无关向量$b_1,b_2,…,b_n$序列，我们将它们GSO为$\tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_n$向量序列

$\tilde{b}i = b_i - \sum{j=1}^{i-1} \mu_{i,j} \tilde{b}j, \text{where } \mu{i,j} = \frac{\langle b_i, \tilde{b}_j \rangle}{\langle \tilde{b}_j, \tilde{b}_j \rangle}.$

$<b_i,b_j>$表示向量$b_i,b_j$的内积

线代是有这个知识点的

基本和易于验证的特性

对于任意 $i \neq j$，我们有 $\langle \tilde{b}_i, \tilde{b}_j \rangle = 0$，
对于所有 $1 \le i \le n$，$\text{span}(b_1, b_2, \dots, b_n) = \text{span}(\tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_n)$，（关于 span，请查看上一篇文章），
$\tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_n$ 不需要是 $\mathcal{L}(b_1, b_2, \dots, b_n)$ 的基。事实上，他们一般甚至不包含在 lattice
向量 $b_1, b_2, \dots, b_n$ 的顺序很重要：这就是为什么我们认为它们是一个序列而不是一个集合。

QR分解

对格基间接使用施密特正交化得到近似正交基

写成矩阵

在m=n的情况下，明显这是一个上三角矩阵

该矩阵是上三角行列式所以行列式 $det(B) = \prod_{i=1}^{n} ||\tilde{b}_i||$
我们能得到 $\lambda_1$ 的下界，即 $\lambda_1 \ge min(||\tilde{b}_i||)$

Successive Minima(连续极小)

由于格上的点是离散的，所以除了零向量外肯定纯在一个非零向量，其长度是最短的

定义$\lambda_1(\mathcal{L})$为格$\mathcal{L}$中最短非零向量的长度（不考虑零向量）（长度指的是欧几里得范数）

不过应该是一个向量集->最短非零向量集，因为有一个最短非零向量就有两个（取反）

所以$n$维格中，我们有2n个最短向量，每个轴上都有两个最短向量

定义

在格$\mathcal{L}$中，第$i$连续极小值（$i=1,2,…,n$）,为$\lambda_i=minr:dim span($$\mathcal{B}$)∩$\mathcal{L}$

格中难题

Hermite定理

对于$n$维的格$\mathcal{L}$都包含一个非零向量$\vec{v} \in \mathcal{L}$，满足 $ |\vec{v}| \leq \sqrt[n]{\det(\mathcal{L})} $

SVP（Shortest Vector Problem）

SVP,最短向量问题本质最短非零向量

定义

给定一个基为$B$的格$\mathcal{L}(B)$,找到一个这个基构成的格点，使得这个点离0坐标点的距离最近即$||Bx||\le \lambda_1$,因为$\lambda_1$是格点之间的最短距离，所以Bx距离0点的距离最短就是$\lambda_1$,是存在上界的。

$$Bx:x\in \mathbb{Z}^k\||Bx||\le \lambda_1$$

eg：

$B=[b_1,b_2]$，可以找到一个点Bx,$5b_1-2b_2$对应这个点就是最短向量，这种是理想情况。

当然也有拿到的基不好的时候，找到$\lambda_1$是困难的

->宽松版本$SVP_\gamma$

在$SVP_\gamma$中，本质差别不大，唯一不同在于$Bx$不一定需要恰好的最短向量$\lambda_1$,而只需要满足小于等于$\lambda_1$的一个倍数$\gamma$就行

$$Bx:x\in \mathbb{Z}^k\||Bx||\le \gamma\lambda_1$$

当$\gamma=2$时就有多个解了

CVP(Closest Vector Problem)

格中另一类问题，最近向量问题CVP

定义就是：给定连续空间中的一个$t$,找到距离这个点最近的格点$Bx$

$$Bx:x\in \mathbb{Z}^k\||Bx-t||\le \mu$$

$\mu$:Lattice的覆盖半径（即所有可能的$t$中距离格点最长的距离）

当然肯定也不可能都是恰好最近距离$\mu$，还有宽松版$CVP_\gamma$

$$Bx:x\in \mathbb{Z}^k\||Bx-t||\le \gamma\mu$$

多了$\gamma$参数后，CVP问题就会变得简单一些，解的数量也变多了

SIVP（Shortest Independent Vectors Problem）

Lattice中第三大重要问题，最短独立向量问题

定义：给定一个Lattice$\mathcal{L}(B)$,找到n个独立的向量$Bx_1,…,Bx_n$并且这些向量的长度都要小于等于最长的最短向量$\lambda_n$

$\max_{i} |\mathbf{B}\mathbf{x}_i| \leq \lambda_n$

同样的也有$SIVP_\gamma$

只需要注意$\gamma\lambda_n$在范围内就行

LLL算法

目的：在n维空间中，LLL算法要做的就是让施密特正交化的程度最大化

本质施密特正交化

性质：

|$\mu_{i,j}$|$\le \frac{1}{2}$
向量关系满足：$ \frac{3}{4} ||\vec{b}i||^2 \le ||u{i+1,i}\vec{b}i + \vec{b}{i+1}||^2 $

两者性质结合就是：$ ||\tilde{b}_{i+1}||^2 \ge \frac{1}{2} ||\tilde{b}_i||^2 $