基础定义

LATTICE:

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

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

SPAN:

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

FUNDAMENTAL PARALLELEPIPED:

对于任意的格基$B$,

幺模矩阵:

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

DETERMINANT:

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

对于格 $\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}$ 是与 $\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)$:

其中,$\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格,如果它满足

  • $\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$,

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基向量的,因此可以得到一个短向量。
  2. LLL约化算法限制了新旧向量的长度的比值,不让它减的太快,这样的基向量是更容易找到短向量的。

特殊形式的CVP

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

有界距离解码问题(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发展历史: