几个重要的格简约概念

格理论 密码学 SVP

---

（文章中的引文会慢慢补充起来）

格简约基是格密码中常常出现的概念。不严谨地讲，一个格基是简约(reduced)的，意味着其其中各个向量都较接近正交。关于格简约的概念，有好几种定义。每种定义都各自适合某些情况。在许多算法中，比如SVP/CVP求解器，常常会以具有某种简约性质的格基作为输入，因为具有（合适的）简约性质的格基往往能够使算法更好的工作。

Orthogonality defect

如何衡量一个格基的正交状况？一个方法是使用Orthogonality defect（暂时翻译为：正交性探测）。

定义1. Orthogonality defect
设$\{b_1,...,b_d\}$为格$L$的基,这组的基的正交性探测定义为:

$$\frac{\prod_{i=1}^d ||b_i||}{vol(L)} (\ge 1)$$
等式成立当且仅当该基为正交基。

根据正交性探测的定义，很容易看出，在保持仍是格基的情况下，如果能减少$b_i$的长度，那么这个基就越正交。因此，想要得到一个好的“基”往往可以从减小基向量长度来入手。

在$\mathbb{R}^n$中，GS正交化能够把一组基转换成一组正交基。在格的情况下，GS正交化得到的基一般不会是原格的基，但这不妨碍GS变换在格基简约中的重要性。以下假设阅读者对GS正交化的概念已有一定的熟悉度。先简要回顾一些概念:

设 ${b_1,...,b_d}$是格$\mathcal{L}$的基。$b_j^*$为$b_j$对应的GS正交化向量.
定义2. GS系数 GS系数定义为

$$\mu_{ij} = \frac{<b_i,b_j^*>}{ \lVert b_j^* \rVert ^2}$$

引理1. 格的体积等于GS正交向量的乘积

$$vol(\mathcal{L}) = \prod_i^d \lVert b_i^*\rVert$$

size-reduced

第一个格简约概念形式简单，而且基本是后面reduction概念的基础。

定义3. size-reduced
设$B = \{b_1,...,b_d\}$为格$\mathcal{L}$的基. B是size-reduced的，当其GS系数:

$$|\mu_{ij}| \le \frac{1}{2}$$
对于所有$1\le i \le j \le d$成立.

任意的格基都存在与其等价的(生成同一个格并且GS正交向量相同)满足size-reduced基，并且转换的算法也非常简单.

algorithm 1:Size-reduction
输入:格基$B = \{b_1,...,b_d\}$
输出:满足size-reduced的格基

for i = 2 to d
    for j = i-1 downto 1
        bi = bi - cij*bj

其中 $c_{ij} = \lfloor \mu_{ij} \rceil$

然而，尽管size-reduced概念简单，并且容易达到，满足size-reduced的基并不一定是好的基，一个例子是：设$F_i$为第i个斐波那契数。那么下面的格基：

$$\left [ \begin{matrix} F_{i+1} & F_{i-1} \\ F_{i+2} & F_i \end{matrix} \right]$$
满足size-reduced的条件，但是正交探测值非常大(请自行验证，根据$F_{i-2}F_i - F_{i-1}^2 = (-1)^{i-1}$与$F_i \le \frac{F_{i+2}}{2}$)。

那么size-reduced能告诉我们什么呢？根据size-reduced和简单的计算可知，满足size-reduced的基$\{b_1,...,b_d\}$有以下的关系:

$$\lVert b_i \rVert^2 \le \lVert b_i^*\rVert^2 + (\frac{1}{4})\sum_{j=1}^{i-1}\lVert b_j^*\rVert^2 \tag{1}$$

上面的不等式表达了什么信息呢？1. 基对应的GS正交化向量决定了基中向量的长度。2. 指标越小的GS正交化向量，对整个基向量的长度的影响越大。

因此，降低小下标的GS正交化向量的长度会对整个基向量的长度产生影响。当然，根据引理1，降低一个正交化向量的长度必然会引起别的正交化向量的长度的增大($vol(\mathcal{L})$是格的不变量)。然而根据(1)式我们仍然可以确信，低下标向量长度的影响更大。所以，改进size-reduced的一个方法便是：适当降低低下标GS正交化向量的长度，同时控制好其他正交化向量长度的增长。

那么如何降低下标GS正交化向量的长度呢？回顾以下size-reduction算法，可以看出向量的长度很大程度上依赖于它们的下标。一个自然的想法就是：先进行一次size-reduction，然后进行一次置换(将基内某些向量的顺序进行调换)，而后再进行一次size-reduction。这样会不会改进基的质量呢？但是如果给出一定的置换条件，确实会让基有一定的改善。

LLL-reduced

LLL-reduced的定义

定义4 LLL-reduced
格基$B = \{b_1,...,b_d\}$满足$\delta(\delta \in (\frac{1}{4},1))$-LLL-reduced，如果:
1. $B$满足size-reduced条件。
2.

$$\delta \lVert b_i^*\rVert^2 \le \lVert b_{i+1}^* + \mu_{i+1,i}b_i^*\rVert^2$$
对于所有$1<i\le d$

LLL算法的描述（教科书版，实际上有更加高效的实现:github-fplll）

（图片来自Joop van de Pol的硕士论文）
根据size-reduction的描述，LLL-reduced的一个直观是，如果不满足LLL-reduced定义中的第二个条件，那么就两个向量的index交换一下，保证能够（可证明地）让低下标的向量对应的GS正交化向量的长度降低。LLL算法输出一个LLL-reduced基，并且运行时间是关于秩和格体积的多项式界。

满足LLL-reduced的格基有以下性质：

设$\delta \in (\frac{1}{4},1]$,令$\alpha = 1/(\delta-\frac{1}{4})$.设$B = \{b_1,...,b_d\}$是格$\mathcal{L}(\subset \mathbb{R}^n,d\le n)$的满足LLL-reduced的基，则：
1. $\lVert b_1 \rVert \le \alpha^{(d-1)/4}(vol(\mathcal{L}))^{1/d}$
2. $\lVert b_i \rVert \le \alpha^{(d-1)/2}\lambda_i(\mathcal{L}), 1\le i \le d$
3. $\prod_{i=1}^d\lVert b_i \rVert \le \alpha^{d(d-1)/4} vol(\mathcal{L})$

根据性质2，可以看出LLL算法求解了近似（近似系数指数大）最短向量问题。

Lovász condition

LLL-reduced非常重要的条件便是其定义中的第二个条件，即著名的Lovász condition.LLL算法的创始人之一Lenstra最初定义LLL算法的替换条件为:如果$j > i$且

$$\delta \lVert b_i^* \rVert^2 > \lVert b_j^* + \sum_{k = i}^{j-1} \mu_{jk} b_k^*\rVert^2$$
时(注意和Lovász condition的区别)，将$b_i$替换为$b_j$。然而这样子无法给出多项式时间的界。

Lovász指出在改善第i个向量的时候，用下标距离远的向量去替换会难以给出可证明的多项式界。Lovász条件的改善在于，它只会验证相邻两个向量是否满足条件，然后决定是否交换。只交换相邻的向量保证了$span\{b_1,...,b_i,b_{i+1}\} = span\{b_1,...,b_{i+1},b_i\}$，而这个性质有助于证明LLL算法会在多项式时间内结束。

float point LLL

LLL算法中的运算全是分数的算术运算，分数运算的耗费在当时显得太大了，因此Odlyzko等人第一次尝试用浮点数运算代替分数运算。

用浮点数运算，那么就需要考虑浮点数误差。不过有后人提出了可证明的高效浮点LLL.（以后补充）

DEEP

Schnorr和Euchner提出了另外一种LLL变种，称为DEEP。它要求输出的基满足：
$\delta \lVert b_i^*\rVert^2 > \lVert b_k^* +\sum_{j=1}^{k-1}\mu_{k,j} b_j^*\rVert^2 \tag{2}$

算法的做法是（简略描述），初始$i=1$，$k$从$i+1$开始$(i<k\le d)$，$i$从1开始自增，当然先第一个$i$使得(2)不满足，则将$\{b_1,...,b_k,...,b_d\}$重排为$\{b_1,...,b_{i-1},b_k,b_i,...,b_{k-1},b_{k+1},...,b_d\}$。

(2)式可以推出(1)式，因此DEEP输出的基也会是一个LLL-reduced基。然而，关于DEEP，尚未有可证明的多项式界（它的运行时间有可能是指数大的），并且关于其最短向量的近似系数也尚未有一个更好的界（当然显然会有LLL的界）。但是，DEEP在实际运行中的常常效果良好。

HKZ-reduced与BKZ-reduced

再给出另外两个reduced概念前，先给出一个投影操作的定义方便描述，更多关于格的投影，参考这里

定义5. 格的投影
设$B = \{b_1,...,b_d\}$是格$\mathcal{L} \subset \mathbb{R}^n$的基，且$\{b_1^*,...,b_d^*\}$是其对应的GS正交化向量。

定义投影操作$\pi_i$,其将$\mathcal{L}$中的向量投影到$span\{b_1,...,b_{i-1}\}$的正交补空间中。$\pi_i(\mathcal{L})$是一个格。

(该投影操作的直观含义: 由于$span\{b_1,...,b_d\}= span\{b_1^*,...,b_d^*\}$，因此对于任意的$v \in \mathcal{L}$可以写成$b_1^*,...,b_d^*$的一个（不一定是整数的）线性组合，而投影操作$\pi_i$会将$v$中的$b_1^*,...,b_{i-1}^*$分量消去。）

首先是HKZ-reduced概念。

定义6. HKZ-reduced
设$B = \{b_1,...,b_d\}$是$\mathcal{L} \subset \mathbb{R}^n$的基。
当B满足如下条件

$$\lVert b_i^* \rVert = \lambda_1(\pi_i(\mathcal{L}))$$
对于所有的$1\le i \le d$成立。则称$B$是HKZ-reduced的。

注意，HKZ-reduced是非常强的一个简约概念。根据$\pi_i$的定义,$\lVert b_1^*\rVert = \lambda_1(\pi_1(\mathcal{L})) = \lambda_1(\mathcal{L})$ 。即如果一个算法给出了HKZ-reduced的基，那么它本身就能解最短向量问题。不仅如此，它还要求解其他投影格的最短向量问题：对于$\beta$维的投影格，它也要求求解这个格的最短向量。而求解SVP（非近似解）的算法（可以称为SVP solver)都是指数时间复杂度，因此一个能给出HKZ-reduced基的算法几乎不可能是多项式时间复杂度的。

然而，如果不要求求解出所有$\beta$维的投影格的最短向量，而是求出固定$\beta$维投影格的最短向量（看不懂什么意思别急，下面BKZ-reduced的定义会解释清楚），那是否能有一个可证明的多项式时间界的算法呢？很可惜，有这样的算法，即BKZ算法，但是目前为止该算法只有指数时间复杂度的可证明界。

BKZ-reduced在HKZ-reduced定义的基础上进行了放松（如上段所述）。

定义7. BKZ-reduced
设$B = \{b_1,...,b_d\}$是$\mathcal{L} \subset \mathbb{R}^n$的基，令$2 \le \beta \le d$,$\beta$为一个整数。
如果$B$满足:

$$\delta \lVert b_i^*\rVert^2 \le \lambda_1(\pi_i(\mathcal{L(b_1,...,b_{min(i+\beta-1,d)})}))^2$$
对于任意的$1 \le i \le d-1$成立，则称$B$是:块大小为$\beta$的$\delta$-BKZ-reduced的。
($\mathcal{L(b_1,...,b_{min(i+\beta-1,d)})}$意思是由$b_1,...,b_{min(i+\beta-1,d)}$组成的格)

HKZ-reduced实际上和块大小为$d$的$1$-BKZ-reduced概念是等价。BKZ-reduced对HKZ-reduced的放松体现在:1. 引入了参数$\delta$. 2.不要求$b_i^*$是$\pi_i(\mathcal{L})$的最短向量，而是要求$b_i^*$在从i开始块大小为$\beta$的投影格中是最短向量即可。

关于LLL、DEEP、BKZ算法的细致描述、解释与比较，放在格简约算法实际运行的比较（待完成）中。关于格简约算法，有一个更好的讲解