格密码基础-格基约化算法及相关困难问题

格

基础定义

LATTICE：

给定n个线性无关的向量$b_1, \dots, b_n \in \mathbb{R}^m$，由他们生成的格是

$$\mathcal{L}(b_1,b_2,\dots,b_n)=\{\sum x_ib_i | x_i \in \mathbb{Z}\}.$$

$b_1, \dots, b_n$是格中的一组基。（格向量是实数域上的）

SPAN：

格$\mathcal{L}(B)$的span是由其格向量张成的线性空间。

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

FUNDAMENTAL PARALLELEPIPED:

对于任意的格基$B$,

$$\mathcal{P}(B)=\{Bx | x \in \mathbb{R}^n, \forall i: 0 \le x_i \le 1\}.$$

幺模矩阵：

对于矩阵$U \in \mathbb{Z}^{n \times n}$, 满足 $\text{det}U=\pm 1$（矩阵元素都是整数）

DETERMINANT：

令$\Lambda=\mathcal{L}(B)$是一个秩为$n$的格

$$\text{det}(\Lambda) := \sqrt{\text{det}(B^TB)} (\text{或者}|\text{det}(B)|)$$

对于格 $\Lambda$ 来说，不同格基矩阵 $B$ 对应的基础区域是不同的，但基础区域对应多面体的体积是个定值。$\text{det}(\Lambda)$ 是格 $\Lambda$ 最为重要的不变量之一。

Gram-Schmit正交化:

给定一组线性无关的向量$b_1, \dots, b_n \in \mathbb{R}^n$, $b_1, \dots, b_n$的Gram-Schmit正交化是：

$$\tilde{b_i}=b_i-\sum_{j=1}^{i-1}\mu_{i,j}\tilde{b_j}, \\ \mu_{i,j}=\frac{\langle b_i, \tilde{b_j} \rangle}{\langle \tilde{b_j},\tilde{b_j} \rangle}$$

$\tilde{b_i}$ 是与 $\tilde{b_1}, \dots, \tilde{b_{i-1}}$ 正交的 $b_i$ 的分量。Gram-Schmit正交化有几个简单的性质：

1. $\forall i \neq j, \langle \tilde{b_i},\tilde{b_j}\rangle = 0$
2. $\forall 1 \le i \le n, \text{span}(b_1,b_2, \dots,b_i) = \text{span}(\tilde{b_1},\dots, \tilde{b_i})$
3. $\tilde{b_1},\dots, \tilde{b_i}$不一定是格的基。
4. $b_1,b_2, \dots,b_i$ 是一个序列而不是集合

successive minimum:

令$\Lambda=\mathcal{L}(B)$是一个秩为$n$的格,$\forall i \in \{ 1,\dots,n\}$，逐次最小长度$\lambda_i(\Lambda)$:

$$\lambda_i(\Lambda)=\text{inf} \{ r | \text{dim}(\text{span}(\Lambda \cap \overline{\bf{B}}(0,r))) \geq i\}$$

其中，$\overline{\bf{B}}(0,r)=\{ x\in \mathbb{R}^m | ||x|| \le r\}$是以0为圆心，半径为$r$的球。

在几何中可以理解为：第 $i$ 个逐次最小长度 $\lambda_i$ 为以原点为球心，包含 $i$ 个线性无关格向量的最小球半径。显然，$\lambda_i(\Lambda)$ 为格 $\Lambda$ 的最短非零向量长度。一些简单的性质如下：

1. 对任意格：$\lambda_1(\mathcal{L}(B)) \le \lambda_2(\mathcal{L}(B)) \le \cdots \le \lambda_n(\mathcal{L}(B))$, $\lambda_2(\mathcal{L}(B))$是与最短非0格向量线性无关的最短格向量长度
2. $\lambda_1(\mathcal{L}(B)) \geq \underset{i=1,\dots,n}{\text{min}} ||\tilde{b_i}|| > 0$
3. $\forall 1 \le i \le n , \exists v_i \in \Lambda, ||v_i||=\lambda_i(\Lambda)$
4. $\text{vol}(B(0,r)) \geq (\frac{2r}{\sqrt{n}})^n$

q-ary格:

格$\Lambda$称为 $q$-ary格，如果它满足

$$q\mathbb{Z}^n \subseteq \Lambda \subseteq \mathbb{Z}^n$$

• $\mathbb{Z}^n$是一个整数格
• $q\mathbb{Z}^n$ 在模$q$意义下是周期性的

给定矩阵${\bf A} \in \mathbb{Z}_q^{n\times m}$，可以定义两类$m$维q-ary格：

• $\Lambda_q({\bf A})=\{ {\bf y} \in \mathbb{Z}^m : {\bf y}={\bf A}^T{\bf s} \text{ mod }q \text{ for some }{\bf s}\in \mathbb{Z}^n\}$
• $\Lambda_q^\perp({\bf A})=\{ {\bf y} \in \mathbb{Z}^m : {\bf Ay}={\bf 0} \text{ mod }q \} $

  投影子格：

令$\bf{B} :=({\bf{b}}_1,\cdots,{\bf{b}}_n)$为$\mathcal{L}$的格基，定义投影算子$\pi_i$为向量在补空间$(\bf{b}_1,\cdots,\bf{b}_i)^\perp$上的投影。
投影格基${\bf{B}}_{[j,k]} :=(\pi_j({\bf{b}}_{j+1}),\cdots,\pi_j({\bf{b}}_k))$；投影子格 $\mathcal{L}_{[j,k]} := \mathcal{L}({\bf{B}}_{[j,k]})$。易知${\bf{B}}_{[j,k]}$张成的线性空间即为$(\tilde{\bf{b}_{j+1}},\cdots,\tilde{\bf{b}_k})$张成的线性空间。

• 对于高维格的格基约化，常见的策略是对其低维的投影子格进行格基约化，并将其提升回高维格。
• 对于$\mathcal{L}_{[j,k]}$中的格向量$\bf v’$，将其提升到格$\mathcal{L}$中，等价于找到$\bf v’$在$\mathcal{L}$中的（近似）最近向量。（Babai最近平面算法）
• 在投影子格的操作和另一个空间是互不影响的，因为是完全正交的。
• 投影子格不是格的子格。

基础定理

如何判断一组基是格基？
令$\Lambda$是一个秩为$n$的格，令$b_1,b_2,\dots,b_n \in \Lambda$是$n$个线性无关的格向量。则$b_1,b_2,\dots,b_n$是格$\Lambda$的一组基 $\leftrightarrow \mathcal{P}(b_1,b_2,\dots,b_n) \cap \Lambda = \{ 0\}$.

如何判断两组基生成的格是相同的？

• 两个基$B_1, B_2 \in \mathbb{R}^{m \times n}$是相等的 $\leftrightarrow B_2 = B_1U$
• 两个基$B_1, B_2 \in \mathbb{R}^{m \times n}$是相等的 $\leftrightarrow $ 一个基可以通过初等变换得到另一个基

如何预测格中最短向量的长度？
根据MINKOWSKI第一定理，$\lambda_1(\Lambda) \le \sqrt{n}(\text{det}\Lambda)^{1/n}$

MINKOWSKI第二定理: 对任意秩为$n$的满秩格$\Lambda$，

$$\lambda_1(\Lambda) \leq (\prod_{i=1}^n\lambda_i(\Lambda))^{1/n} \le \sqrt{n}(\text{det}\Lambda)^{1/n}$$

LLL算法

LLL约化基

LLL约化基: 一个基$B={b_1, \dots, b_n}\in \mathbb{R}^n$是一个$\delta-$LLL约化基,若满足：

1. $\forall 1 \leq i \leq n, j<i. |\mu_{i,j} \leq \frac{1}{2}|$
2. $\forall 1 \leq i \leq n. \delta || \tilde{b_i} ||^2 \leq || \mu_{i+1}\tilde{b_i} + \tilde{b_{i+1}} ||^2$

• 条件1: $\delta=\frac{3}{4}$, 事实上算法允许 $\frac{1}{4} \leq \delta\leq 1$. 这个条件使得格基向量之间变得更紧凑，以及尽可能接近正交。
• 条件2: $||\tilde{b_{i+1}}||^2 \geq (\delta-\frac{1}{4})||\tilde{b_i}||^2$, 这表明 $\tilde{b_{i+1}}$ 不会比 $\tilde{b_i}$ 短太多。如果短太多，那么会在算法中进行向量交换并重新进行约化，这也说明，短太多的基的约化效果并不好。
• 对于条件2，表明LLL约化基的正交向量的长度应该是差不多大的。同时，条件2保证了最短向量的界。

最短向量：令$b_1, \dots, b_n \in \mathbb{R}^n$是一个$\delta-$LLL约化基， $||b_1|| \leq (\frac{2}{\sqrt{4\delta-1}})^{n-1} \lambda_1(\mathcal{L})$.

当$\delta=\frac{3}{4}$， $||b_1|| \leq 2^{(n-1)/2}\lambda_1(\mathcal{L})$.

LLL算法

算法介绍：

输入：格基$b_1,\dots,b_n \in \mathbb{Z}^n$
输出：$\mathcal{L}(B)$的$\delta-$LLL约化基

• Start: 计算$\tilde{b_1},\dots,\tilde{b_n}$
• Reduction:
  for $i=2$ to $n$ do:
  $\quad$ for $j=i-1$ to $1$ do:
  $\quad \quad$ $b_i \leftarrow b_i-c_{i,j}b_j$, 其中 $c_{i,j}=\lceil \langle b_i, \tilde{b_j} \rangle / \langle \tilde{b_j}, \tilde{b_j} \rangle\rfloor$

• Swap：
  if $\exists i$ s.t. $\delta || \tilde{b_i} ||^2 > || \mu_{i+1}\tilde{b_i} + \tilde{b_{i+1}} ||^2$ then:
  $\quad$ $b_i \leftrightarrow b_{i+1}$
  $\quad$ 回到Start

• 输出$b_1,\dots,b_n$

算法分析：

1. 经过约化步后，GS基是不需要重新计算的。因为约化步对正交基没有影响。
2. 算法是多项式时间的。

LLL算法为什么能找到短向量：

1. 经过LLL约化后的基，$b_1$可证明是小于某个界的，这个界是和GS基的向量长度相关的，并且由于格中最短向量是大于最小的GS基向量的，因此可以得到一个短向量。 $$\lambda_1(\mathcal{L}(B)) \geq \underset{i=1,\dots,n}{\text{min}} ||\tilde{b_i}|| > 0$$
2. LLL约化算法限制了新旧向量的长度的比值，不让它减的太快，这样的基向量是更容易找到短向量的。

特殊形式的CVP

给定一个格 $\Lambda$，一个向量 $\vec{t}$ 和一个实数 $d$，找到一个格向量 $B\vec{x}(\vec{x} \in \mathbb{Z}^k)$ 满足

$$||B\vec{x}-\vec{t} || \leq d$$

有界距离解码问题（BDD）

如果 $d < \frac{\lambda_1(\Lambda)}{2}$，该问题称之为BDD，此时至多存在一个格点（格向量）满足条件。该解恰好是 $\vec{t}$ 的最近向量

绝对距离解码问题（ADD）

如果$d＞\mu(\Lambda)$，该问题称为ADD，此时该问题总有解。该解不一定是 $\vec{t}$ 的最近向量

困难问题的难度刻画

格困难问题：LWE问题

输入$A \in \mathbb{Z}_q^{m \times n}$ 和 $A \cdot \vec{s}+\vec{e}$, 其中$\vec{s} \in \mathbb{Z}^n_q$任取，$\vec{e}$ 服从高斯分布； 输出 $\vec{s},\vec{e}$

• 等同于：在随机 $q$-ary格$\Lambda(A^T)$ 上给定随机目标向量$\vec{t}=A\cdot \vec{s}+\vec{e}$，求解CVP
• 通常$\vec{e} < \frac{\lambda_1(\Lambda(A^T))}{2}$，并且给定样本 $A \cdot \vec{s}+\vec{e}$， $\vec{e}$唯一确定。
• LWE $\equiv$ 近似BDD

而CVP问题可以转换为SVP问题：

SVP和CVP发展历史：