lattice cryptography基础

这是Simons 2020 年格密码讲座 Lattices: Algorithms, Complexity, and Cryptography Boot Camp 的第 1 讲，所述内容。
主要是格密码的一些前置基本知识，并且对后面要讲的格密码学做个一个启发式。
本篇为学习记录+个人笔记。内容主要包含格的定义和一些基本量，基本困难问题、归约、对偶格以及对后面讲格密码的一些铺垫延伸式问题。

lattice definition（定义）

格的一种定义方式①

左边是简单定义，在整数格上。
右边是：任意格可以看做是在整数格Zn上做了一个线性变换B得到的集合

有些格算法确实是这样做的：
“先取一个格，然后施加线性变换到另一个格上，在另一个格上解决问题，然后再变换回原来的格”

更常见的定义方式②：

欧式空间上n个线性无关向量的整数线性组合的集合

在二维情况下，可以把线性变换B的列看做是一系列向量的集合
格上的点正好是基向量的线性组合，且系数都是整数
这就类似于向量生成的向量空间，但这里只取整数的线性组合

二维示意图：（由b1和b2就可以构成这样一个二维的格空间，其中的任意向量都可以由他两表示）

但是一个格可以有多组基

明确：这里的基向量，指的是Bi,Ci

值得注意的是：

在大多数应用中，作为问题中输入的格，是以基向量的形式来表示的

我们需要从输入的基向量出发来计算得到一些量

一个格可以有多种基向量表示，所以根据输入的基不同，问题可能会变难或变简单

格的第三种定义方式③

不用基向量来定义

把格定义为：欧式空间上点集的离散子群，这个子群对加法和减法而言是封闭的，且是离散的。

这样的好处在于：在研究格的几何性质时，如果不考虑基向量，而只把格看做具有这些性质的点集，只在需要计算格上问题的时候，再去考虑基向量。————“这种方法很有用”

格的一些基本量（fundamental quantities associated to a lattice）

1. 格的行列式（determinant）

definition：

格的determinant就是基本区域的volume
如下图所示，就是平行多面体的体积

注意：

1. 不同的基定义（会构成）不同的这样的基本区域（平行多面体）
2. 在某一组基向量下，可以得到不同的基本区域，但他们的体积都是一样的（所以，determinant不是某一组基向量的性质，而是格本身的性质）
3. 给定任意一组基向量，计算行列式也是很快的
   

从密度角度理解determinant（行列式）

来看一个例子：

格上有一个小球，这个球包含一定的格点（也可以说包含一定的基本区域/体积/行列式），随着小球的不断扩大，可以预测球内的格点能够趋近一个极限，这个极限的值就是球的体积除以格的行列式（也就是小圆的体积除以这些基本区域块中任意一块的体积）

小结：

1. 行列式只是根据空间中足够大的一块区域中格点的数量来定义的。
2. 行列式可以理解为格点的密度的定义。
3. 同一密度，格的行列式是一样的。
4. 所以行列式不依赖与具体基向量的取值。

关于行列式的计算！
给定一组基向量，可以很快求出格的行列式
比如可以看做类似于伸缩因子的量
在实际问题中，可以假设行列式的值是1，行列式可以看做归一化因子，如果行列式不是1，可以伸缩变换让它变成1，它可以用于把格点空间的密度归一化；
即使两个格的密度相同，他们的几何结构仍可能差别很大；
平均来说，两个格在单位体积内的格点数量可能相等，但这些点在n维空间中的位置排布还是可能大不相同。（but the position of the points can be arranged in very different ways in n dimension space）

关于以上记录，主要促进两个理解：
一个是行列式的伸缩变换计算；
另一个是n为空间的格点排布情况。

行列式是容易计算的，而以下的量却没有能很快计算出他们的已知方法。

2. minimum distance & successive minima（格的最小距离和连续极小）

格的最小距离（minimum distance），也叫格的第一连续极小（first minimum）

以下是一个二维例子：

格的连续极小（一系列）

用“人话”来说就是：
当球是这个样子的：

可以看到：

1. 除了一个minimum distance,还会有一个逆向量相对；
2. 此外，由这条线上，可以张成一个一维空间

进一步，球扩张了一些（取一个大一点的球）：

我们就可以找到其他的向量（和之前向量不在同一条直线上）
——也就是会得到一个稍长的，与之前格点线性无关的格点（linearly independent lattice）
这个大一点的球的半径就叫做格的第二连续极小，记作λ2

在二维空间中，到此就结束了！
（个人理解是：没有第三个向量是与前两个线性无关的了——第三个都可以用前两个线性表示）
但是在n维空间中，可以用类似的方法一直取到λn。

所以很明显：

1. Z^n可以视作n个长度为1的线性无关向量构成的格（也就是整数格的标准基）
2. 在这种情况下，n个连续极小的值都是相等的，而且都是等于1。
3. 但是这个规律不适用于一般的格（非标准的格）。如果在Z^n上施加线性变换，得到的格上n格连续极小λ1……λn是一个递增的序列。

练习：
尝试将λ1……λn设定为任意自己想要的值，选好后，尝试构建满足这些值的对应的格

Distance Function & Covering Radius

Distance Function

考虑目标点t和格点s的距离问题
对于每个目标点，考虑它与离它最近的格点之间的距离（distance function）

Covering Radius（覆盖半径）

先说距离函数的局部最大值

t是目标点，假设给它套上一个球，球面包含几个格点，我们可以扩大这个球（通过在空间里移动目标点t——即一定了球心，扩大了球的半径），只要这个球面没有囊括新的格点就行。假设如图所示，格点往下移动，这样他的距离函数就可能会包括下面这个格点。在某个位置时，我们就能得到局部最大值！此时不管往哪个方向移动球，要么会把格点吞入球中，要么就必须减小球的半径——由此也就减小了到格的距离。
而这个最大值仅仅是距离函数的局部最大值！

如果考虑整个空间中距离函数的最大值——那就是覆盖半径！

可理解为：从格点出发，能走到的离格点最远的距离。
也可以理解为：以每个格点为球心放置球，这些球在一开始是分开的，但是随着球半径的增大，球之间会出现交叠，最终会完全覆盖整个格空间，此时球的半径就是覆盖整个空间所需要的半径长度。顾名思义，覆盖半径。

直到完全覆盖：

Smoothing a lattice（光滑参数）（作者技术需要而定义）

这里启发自己做研究时，也要有这种思维，而且是很自然的才行。
简单先理解为：当半径取值大于覆盖半径，且加入某种噪声进去，使得整个空间的“覆盖颜色”趋于一致的这个参数——光滑参数。

Problems

Shortest Vector Problem（最短向量问题）（SVP）

给定一个基向量组为B的格，找到一个最短向量（加上松弛参数γ，也可以变为近似的求值结果——也就是至少要是一个短向量）
最短向量如图所示是内圈半径，松弛的是外圈半径。

Closet Vector Problem（最近向量问题）（CVP）

关于CVP问题，即在一组基向量下构成的格空间，要找到距离目标点最近的一个格点（如下图所示）

但是如果能够穷举（如下图画出所有点）b1和b2生成的所有格点，是能够轻易找到一个距离目标向量最近的格点的（如下图所示）

这个问题同样有近似版本，放松了对最近向量的要求（如下图所示）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

Shortest Independent Vectors Problem（最短线性无关向量问题）

同前面，也是有标准和松弛版本。
需要找到n个长度最大为λn的线性无关的格向量。
这些向量可以是都比λ1长的，也可以是更复杂的——需要找到一系列向量（长度正好是λ1、λ2………λn

“但一般来说，我们只需要找到长度不大于λn的向量就够了”

所以，这是个一般的格，输入是它的基向量，以原点为球心放置球，把半径增大到足够大，可以一直增大到λn，
此时球里就有n个线性无关的向量，我们就可以去找到它们，或者只是估计λn的值（同前）

此外，还有BDD和ADD问题（松弛了的）

困难问题之间的关系 & 归约

这里将由这个归约的例子，引出对偶格。

简单例子）ADD到SIVP的归约

如果能够算出格上n个线性无关向量，就能够估计出最近向量特定版本的解。

ADD问题：
给定格L和目标向量t，找到离t不太远的格点。

方法：可以先解出格上SIVP问题——找到n个线性无关的短向量。

具体简单思路：
找到一组好的基，可以将目标点t取整到格点上（用好基表示这个t）

1. 按基向量v1和v2计算t的坐标
2. 对坐标取整——》得到格上的一个点x
3. 这个格点到t的距离最多是基本区域的直径
4. 如果定义基本区域的向量长度最多是λn，直径最多就是nλn。（其中若向量是正交的，前面系数就为根号n，如果这些向量近似于平行，这个系数就近似于n）

以上是个不准确的归约，从一个问题归约到另一个时，放松了一个因子n；但是也可以反映出他们之间的关系。

BDD问题归约

下面，归约BDD问题——需要用到对偶格。
涉及到几个概念和技术，

1. size reduction（长度约简）

（这部分还不是很理解）
大约讲的是：
如果要在b1和b2生成的格中，使t向量最短，可以通过不断约减b1或b2向量实现。
阴影部分分别与b1和b2垂直，如图所示，t’就是那个阴影部分的宽度，不断用t-t’，直到最短。
至于他说为何会有这种正交性，后面回来再理解！

2. 施密特正交

（理解很浅，暂记）
用途：可以计算这些正交向量——》计算格的行列式
通过这些正交向量的长度的积来计算
但要注意，b2*不一定是基（不一定可以构成格）

3. lattice rounding(格的上界)

结合上图，若构成正交基生成的多面体
虽然这些向量不是格的基向量，但是他们也构成整个空间的一个划分。

在这个空间中，任取一点，都可以找到一定距离内的格点。（下图的任取一点用蓝色点表示，而格点为红线交叉区域）

而这个距离最多是这些正交的多面体直径的一半！——所以在这个区域内部的半径的一半以内，一定可以找到最近的格点。

所以，关于这个区域定义两个球，一个在区域内部，一个在区域外部。如果在内部，取整操作就能够找到CVP的准确解；如果在外部，就能找到一个解，这个解距离准确解不会太远。
在区域外部这种情况，这个点到格点的距离比在内部找到的远，“所以得到的是个近似解”——（个人不理解为什么）
如果是这个思路，就可以找到CVP问题在某个近似因子之内的近似解。这个近似因子与一个比例成正比（正交空间中最大和最小的正交向量的比例*根号n）。

以上所述有个前提：需要找到一组好基，这组基中每个向量之间的距离都很近（有时候是办不到的）。

4. the dual lattice（对偶格）

对偶空间

首先理解线性空间中的对偶空间，这一点在这个博客里说的很好：

注释几点：

1. 线性泛函（linear form）指的是“由向量空间到对应纯量域（标量）的线性映射”。
2. 下图这句解释一下
   

就是：ϕ是从线性空间到标量空间的映射，对于属于线性空间的x来说，有ϕy(x)=⟨x,y⟩，所有的ϕy(x)，即⟨x,y构成的向量空间就是原空间的对偶空间。——其实这个博文解释的已经很好了，这里只是顺带记录下我的理解阐述。

同样，也如下图所表述：

对偶格的定义

根据前述，自然也就很好理解对偶格的这个定义了。
翻译一下：格Λ的对偶格就是：所有属于格Λ生成子集的向量x的集合，其中x满足：对所有属于格Λ的v来说，<x,v>∈Z。

再翻译一下：这个集合中的向量和任意格点的乘法得到的结果都是整数。

到此为止，就理解了对偶格的定义了，但是为什么需要对偶格，也就是对偶格的性质或者应用会很有效，这个就需要后续学习继续体会了。

看以下例子：

1. 标准情况
   一个标准Z^n这个格，它的对偶格是：
   

上图的红点和黑点其实是重合的。只是为了展示故意显示出来。

2. 做个旋转
   上面的格就会变成如下：
   

但是注意：选择操作不会改变数量积（去两个向量，旋转同样的角度，计算数量积，所得结果是不变的）——由定义有下图：

对偶格也旋转了，还是得到了Z^n

3. 做个伸缩变换
   取一个格，乘上一个因子q：
   如果我们要满足定义——即数量积保持一致，那么原来的格伸展了q（q得>1），那么对偶格就得收缩，才能满足定义。如下图所示：
   

“这也体现出对偶格的行为在某种程度上是和原来的格相反的。但格不是数，所以这种相反不是数的求逆，而是一种相反的性质”

4. 如果考虑一个任意的格
   会得到如下图所示：（示意图，位置不一定十分准确）
   

若是去掉线条：

再细看，这就是两个格（每个都是由一组基生成的格）

and

可以看到，这是两个格，所以如果把格点和对偶格中的点加起来，这个操作是没有意义的！
因为他们所在的向量空间是不一样的，在同构意义上也是不一样的。
“最好的思考方式是：通过点和函数来理解，可以把函数作用于点，但他们是不同类型的量，即使他们都用向量表示，也不能进行这样的操作”。
但是！
我们能够取数量积，这里就是用了一个关键的性质！（每当使用对偶格时，我们都在使用这个性质）
这个性质后面说，现在先小结一下刚才的例子们：

小结

重要性质与变换定理

我们能够取数量积，这里就是用了一个关键的性质！（每当使用对偶格时，我们都在使用这个性质）
这个性质是：
格点可以用对偶格点来对偶格点给出了一种划分格的层次的方法）：
通过格点到对偶格点的距离来划分（距离为0，1，2等等），
在这个划分中，每层之间的距离正好等于对偶向量长度的逆！

如果取的对偶向量长一些，得到的划分层次就会不同，每个层次之间的距离更近，如下图所示：

通过每个对偶格点，都能得到格的划分。

很多算法都是使用对偶格来执行这样的划分，然后执行一些数值上的取整操作。
基于上述的简单性质“每层之间的距离正好等于对偶向量长度的逆”，
可以在两个分层的中间放一个球这个球位于两个分层中间，所以不会包含任何格点（因为格点都在分层上），如下图所示：

如上的方式么就给了我们覆盖半径的一个下界，如果我们能够在对偶格中找到短向量，这个短向量就能给出一个划分，其中每个分层之间的间隔很远，
所以我们就能在这些很远的间隔中间，放置半径尽量大的球
如果我们有短的对偶格向量，那么原来的格的覆盖半径就一定很大，也就是说：如果对偶格的λ1很小，μ（L）就会很大。
以上就是一个变换定理的例子！

变换定理：（定理证明无需理会）

解读：可以把格的λ1和对偶格的覆盖半径关联起来：这两个值的积总是在1-n之间，其中n是格的维数。
例如原格λ1和对偶格λ_（n-i+1）这两个值的积也在1到n之间。

所以，
利用变换定理的结论，可以证明一个coNP的结果，如何说明格没有短向量——》就去说明对偶格有n格线性无关的短向量。根据变换定理，这些短向量就会给出原格的λ1的一个下界

将BDD与SIVP问题联系起来

在格中找到距离目标点t最近的格点。
可以考虑用对偶格
就在对偶格中找到n个线性无关的向量，这些向量是短向量，他们在对偶格上

这样也就定义了格的一个划分，把格划分为各个分层

这里就可以通过取整，通过vi和t的点乘来找到哪些分层是离目标点最近的。
注意：二维空间中，每个分层就是一条线！如上图所示~而在n维空间，每个分层就是n-1维的超平面
也就是要找到距离目标点最近的n-1维超平面

如果对所有的对偶向量都使用这个方法，通过解SIVP问题找到所有短的对偶向量，每一个短向量都能给出一个n-1维的超平面，而解SIVP问题得到的是线性无关的向量组，所以这些超平面是线性无关的。
如果取这些超平面的交际，正好得到一个点！这个点就可以作为我们的解，如下图所示：

现在分析这个结果好坏与否？

如果目标点到格点的距离最多是λ1/2n，，就能说明我们得到了比唯一解码半径更好的结果——这是比限界距离稍微强一点的形式，带有一个近似因子n的解。
而根据变换定理可知：λ1/n^V，最多是SIVP问题中的解中的第i个向量长度，所以他们都比λn小，但这些项都在分母上，所以构成的是一个上界——即t在这个距离之内（λ1/2n），就可以得到这个上界（1/2*vi的范数）。
反过来，如果能给定一个在这个上界内的点，我们也能得到正确答案。
上述如下图所示：

working modulo a lattice（模格）

对偶格的应用

定义

“格上点和格点的距离函数，对这个函数周期性的取模（函数本身也具有周期性）——因此研究格问题的时候可以去模格
在欧式空间中去模格，很多点都是重复的——可以把他们视作相同的点”

1. R^n是一个加法群，格是它的一个子群

2. 所以可以通过标准的做法，取到这个子群的商群（quotient groups）

3. 商群（quotients）中的元素就是格的陪集（lattice cosets）——即对格的平移

4. 格中的每一个基本区域（fundemantal region），都提供了一套格和陪集的标准表示法

5. 如果取半开的区域，则每个点只属于一个区域。（边界上的点不会同时属于两个区域，每个基本区域中，每种颜色的点只会有一个（如下图）
   

6. 如果进行基变换，我们能够得到一套不同的表示法。但是每个陪集在每个基本区域中也只有一个点（如下图所示）
   

7. 存在能够表示陪集的不同方法：即求目标点和对偶格的基的数量积 。
   8.当我们求数量积的时候，一定会得到整数，所以不用考虑具体是哪个格点距离目标点最近，直接通过取模格，来得到这个最近的点。
   

小例子

1. 取数量积，然后把结果模1——即取结果的小数部分；
2. 同时t不是格点，所以得到的结果不是整数
3. 但是这个取到的结果，能够准确抓住目标点取模格后的值
   这在一些格问题中很有用！（如下面将要讲的）

CVP & lattice cosets

现在换一种定义CVP问题的方式——不找最近的格向量，而是考虑格的平移问题！

注意到：如果我们同时移动格点和目标点，移动相同的距离，那么他们之间的距离不变

基于上注意到的东西，
我们可以考虑平移版本的格
在平移后的格中找到距离原点最近的点

以上这两个问题是等价的，可以通过对偶格写成公式形式！

Random lattices in Cryptography（随机格）

考虑周期性模q的格，它包含Z/qZ，即q模的子格
可以使用固定精读的整数来表示坐标值

一点逻辑
密码学或者编码理论中都可以选这个格
如果我们要构建一个格，且它的坐标函数是好的（或者说是对的），那么这些都是很自然的选择（就像吃饭要拿筷子才好夹菜一样）

Example of q-ary lattices

定义这个格的标准方法如下：

1. 一种是取一个模q的矩阵，然后考虑矩阵的像（往往把这个矩阵写成转置矩阵）
   所以取A mod q的行向量生成的格，也就是A张成的格
2. 现在考虑A mod q的核，那么这个核就可以写成方程组AX = 0 mod q的形式
   这个A不是一组基，但这里定义的集合仍然是一个格，它是加法封闭的
   它具有格的所有结构

【这里补充一点前置知识抽象数学基础】

以上两种方法是定义q模格的通用方法，且两者是等价的

有三个等价的条件：（如下所示）

1. 格Λ是q模格，优势Z^{d的子集，同时包含qZ}d
2. qZ^d在q的倍数的地方周期性重复，可以表示为矩阵A mod q的像 或者是 另一个矩阵模q的核
3. 此外，对于这个固定的矩阵A来说，这两个格是不同的，一个是像，一个是核，但两种表示是等价的。——换句话说：“给定A可以找到A’，使得A的像等于A’的核”。类似的，给定A’也可以计算出对应的A。
   

对于A生成的格，它的像的对偶就是A的核经因子q伸缩的版本！
（因为当取某个模q的值，又用q除它，就能得到某个模1的值，此时所有的整数都消失了，得到的就应该是对偶格）——ps：此处还需再理解。
类似的，取模q矩阵的核，它的对偶就是A mod q生成的格的伸缩

模格可以干什么呢？
和格密码有什么关系呢？

格密码启发（初探）

Ajtai的函数定义(SIS）——密码角度

解读：
这个函数以短向量为输入，输出是模q的向量
换个角度来看：A的核是一个格
要找到这个函数的一个碰撞（即找到两个点映射到同一个输出），这个问题和在核中找到短向量的问题是等价的
具体：只需要用一个点减去另一个点，他们的差是非零的，而他们的差映射到0。
这个问题也可以看出是伴随解码问题 or 对偶格上的CVP问题。（函数的输出就是取x和对偶格向量的积，并取小数部分，所有的结果都伸缩了一个因子q，所以把结果模q）
（下图=上述）

小结：这里，输入x是0和1组成的二元向量，所以它是短向量，但还是比我们想要的最短格向量长的多（它比λn和覆盖半径长），这就得到了短整数解问题。——这是ADD问题的一种形式，但是对于随机选择的格来说，使用的格是由均匀随机矩阵A定义的

下面初看下LWE（容错学习问题/带着错误学习的问题）

Learning with Errors(lWE)

从某种程度来说，这两个问题的关系就是对偶关系。一个问题是CVP陪集表示的伴随译码，另一个是使用生成矩阵。
与前面的Ajtai对比，区别在于：LWE中输入和错误向量e都比Ajtai的函数短得多。得到的函数是单射，证明难度更大；函数的求逆仍然困难，但是应用更广。

对于上述所说，可以这么理解：
它是随机格中的一个问题，A是生成格的模q矩阵，给定随机格点As，但是它被错误项向量s扰动，错误e需要在最小距离之内，也就是格的唯一解码半径，在这个距离之内的话，解是唯一的。
所以着也可以把LWE理解为BDD问题在平均情况下的一个实例。

综上，LWE和SIS问题是平均情况下的对偶问题（如上所说），分别对应于BDD和ADD两个问题

reference

1. 官方：Lattices: Algorithms, Complexity, and Cryptography Boot Camp
2. B站字幕视频
3. 知乎：抽象代数|笔记整理（8）——序，代数几何引入，模
4. 知乎问答：核与像
5. 知乎问答：核与像

备注： 另外发现了“同学”，是个不错的对照