本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

上一期文章中，我们一起学习了 全同态加密（FHE） 的定义和具体的几个阶段，并且也回顾了FHE的历史。到这里，大家应该对FHE系统已经有一个比较初步的了解了。

我们在上一篇文章的结尾提到了GSW系统，也就是我们所说的第三代全同态加密系统。GSW系统的构造主要是基于格密码学中有名的LWE问题假设。为了更加方便与我们来了解GSW系统的具体构造，我们这期文章来快速地学习一下，格密码学与LWE问题究竟是什么。

格密码学（Lattice-based Crypto）是现在比较火的一个密码学分支，而且本身拥有抵抗量子计算的特性。在即将到来的NIST后量子时代加密算法标准化讨论中，基于格的加密体系就是其中的一个选择之一。不过大家不要被这些定义吓到了，其实想要理解格密码学非常简单，我们只需要一些最基本的线性代数知识。

PS：如果对线性代数内容比较生疏的话，笔者强烈建议去看3Blue1Brown大神的视频合集线性代数的本质。视频里面非常生动的描述了线性代数的基本定理。

到底什么是格密码学？听了半天想必大家还没搞明白，其实格密码学就是基于格（Lattice ）和格上的一些问题而定义的一套密码学体系。所以我们需要先搞明白，格到底是什么。

在线性代数中，我们都知道，如果要描述一个线性空间的话，我们可以找到一个代表这个空间的一组基（Basis）。反过来说，如果我们知道一个线性空间拥有两个基向量（Basis Vector），那么在这个空间里的任意一个向量都可以被分解为这两个基向量的任意线性组合。

举个例子，假如线性空间拥有两个基向量，那么这个空间中的任何一个向量都可以被表示为：

这里可以是任何数字。我们也可以通过改变这两个数字的值来改变最后生成的向量。用这种方法可以生成的所有向量最后就会组成一个线性空间，我们称这个空间为两个基向量的线性生成空间（Span）。

我们日常生活中最常见的线性生成空间，就是XY坐标系（笛卡尔坐标系）了。笛卡尔坐标系的基向量就是两根坐标轴对应的单位向量。任何在XY坐标系中的向量，都可以用的线性组合来代表。

现在，如果我们再给这一个线性空间系统加上一个约束：所有的线性组合系数都必须是整数（Integer），那会和之前有什么不同呢？

如果所有的系数都只能用整数的话，那么我们不断的变动这两个系数的值，形成的向量就不能组成一个连续的线性空间了。反而，这些向量会构成一个密布的、网格状的离散集合。就想上面的图例所示，其中每一个点都代表一个可以被表达成基向量的线性组合的一个独特向量。

因为图片上看上去是网格状的，我们把这样的一个离散的基向量生成空间集合，称之为整数格（Integer Lattice）。

在这里，为了方便理解，我们举的例子仅仅是一个2维的格空间，但是其实我们可以扩展构造任意维度的格空间，唯一只需要把基向量的维度增加就好了。

了解了整数格是什么之后，我们不禁会想：这玩意有什么大不了的？不就是一个离散的线性生成集合嘛。但恰巧因为这个系统是离散的，并且只允许整数出现，我们会发现有很多有趣的问题。

首先，我们回到刚刚说的线性生成空间的问题上。在组成的连续的二维线性生成空间中，因为系数可以是任何数字，所以我们可以表达这个二维坐标系统里的任意向量。但假如我们把这个问题约束到一个整数格中，我们就没有办法这么做了。

之前举的笛卡尔坐标系的例子里，笛卡尔空间的基向量是。现在假设我们在构成的整数格中，想要表达一个向量。我们会发现没有任何办法可以表达它，因为在整数格中系数必须要是整数。

正因为我们无法完美的用整数格中的线性组合来表达我们想要得到的向量，这个问题衍生出了一个新的问题：是否可以找到一个最接近于想要表达的向量的值，并且恰好在这个整数格可以表达的范围当中？

结合我们的例子，重新转述一下这个问题的话，也就是说：能否找到一组整数系数，使得组成的向量在这个整数格中距离目标向量的距离最近？我们观察可以发现，在我们的例子中，如果，那么最后组合得到的向量距离我们目标的距离是最近的。

读到这里，想必大家应该对整数格已经有了一个大致的理解，并且也知道了整数格中的一个难问题：CVP问题。现在我们一起来看看，如何从CVP问题出发，衍生到我们的主角LWE问题上。为了更加方便理解LWE，我们不妨先来回顾一下中学数学～

我们在初中或者高中的数学课上应该都学过如何求解线性方程组（solve system of equations）。一般来说，我们会给到一组多元一次方程：

然后我们需要求解里面的每个未知数。求解这样的问题对于我们来说非常简单：我们只需要拿起一行的等式，再加上/减去另一行的等式，最终就可以得到这三个未知数之间的直接关系，然后得到他们的值了。比如如果我们用第一行减去第三行，我们就可以得到新的等式。

如果这个线性方程组题目出的比较好的话，那么一般我们重复的让这些等式相加/相减几次之后，就可以得到比较确定的答案了，比如之类的。最后我们就可以把这几个已知数再代入回去，然后求解剩下的未知数。

当我们系统性的学习了线性代数之后，我们可以把求解线性方程组的问题用矩阵来表达：

用矩阵的形式来表示之后，这个问题求解的方法也和之前的方法一样：我们可以把矩阵和的行与行之间相加或相减，然后最后得到未知数的结果。我们把这一类行与行之间操作求解未知数的方法统称为高斯消除法（Gaussian Elimination）。高斯消除法系统性的定义就是，给定一个矩阵和一个向量，能否找到一个向量，使得的关系满足。

当我们学会如何求解线性方程组之后，我们发现这其实并不是什么难的问题，只需要不停地在行与行之间相互使用高斯消除，就可以得到未知数的解。毕竟这也是中学的时候学的数学题，难不到哪里去。

现在，我们把这个高斯消除问题变化一下，给它增加一些难度：增加噪音。

假如这个问题变成，如果已知一个矩阵，并且我们还知道一个向量:

其中是我们在一个固定数值范围内随机采集的一个随机噪音向量，能否有效的通过和的值来还原最初的未知数向量？

加上这么一个随机噪音之后，我们线性代数的方法就已经不管用了，因为如果我们使用高斯消除法对每一行进行消除的时候，同时还会带着噪音进去，所以导致无法算出任何一个未知数的值。似乎唯一能够找到的方法就是暴力破解，一个一个猜的可能值，然后逐渐逼近。

总结一下，带上了噪音之后，这个问题就变成了已知一个矩阵，和它与一个向量相乘得到的乘积再加上一定的误差（error），即，如何有效的还原（learn）未知的向量。我们把这一类的问题统称为误差还原（Learning With Error， LWE）问题。为了方便表述，我们后面都称之为LWE。

如果细心的看LWE的问题描述的话，我们可以发现，这个LWE问题与我们之前提到的CVP最短向量问题有着惊人的相似。其实两个问题都一样，我们都是需要找到一组“系数”（我们可以用向量来表示），使得一组基向量（我们用矩阵来表示）的线性组合无限逼近我们想要的目标向量。这里我们使用误差噪音的大小来定义到底我们需要距离目标向量多近。

这样说来，如果CVP是一个复杂度很高（NP-hard） 的问题的话，那么相对应的，LWE问题也是一个 复杂度很高（NP-hard ）的问题了。

大家应该对LWE是什么有概念了吧？接下来，我们来看LWE的正式定义！

首先，我们需要熟悉一下，LWE问题里面需要用到的一些关键概念：

• 首先，为了密码学的应用以及方便计算，我们使用这么一个素数有限域。具体来说，也就是我们的世界里只存在这个范围内的所有整数。
• 为了更好的衡量噪音，我们定义为向量（维度为）的无限范数（Infinity Norm），具体操作就是看这个向量中的每一个值，然后返回最大的那个。
• 最后，我们定义就是为一个最大值封顶为的随机分布。也就是说，从这个随机分布中取出的每一个随机值都会小于。

是不是乍一看一堆符号有些难以理解？莫慌，让我们来逐一看看这个定义到底是什么意思。

简单的来说，在一个LWE问题当中，我们首先需要定义矩阵的维度为 。代表了这个线性方程组一共有多少组方程，而代表了每个方程中有多少个未知数。我们还需要定义整个有限域的大小，一般来说我们都会选择一个足够大的素数作为的值。最后，我们需要决定我们叠加的误差噪音的取值上限。的大小决定了我们LWE问题中需要找到的解距离实际的取值究竟可以相差多少。

定义了上面的这些参数之后，LWE问题就很好理解了：给定矩阵以及带有误差的乘积，还原出未知的向量。

我们发现LWE问题，不同于平常的密码学难题（比如离散对数问题），可以变的参数（）实在是太多了。我们可以再来仔细看一下每一个参数，试图理解一下改变每个参数会怎么改变这个问题的难度：

• 一般来说都被称为整个LWE问题的安全参数（Security Parameter）。如果一个系统中的未知变量越多（即越大），那么整个LWE问题会越难。
• 一般来说都是的一个多项式倍数，。如果可以用的方程组越多（即越大），那么代表整个LWE问题会越简单。
• 一般也是的一个多项式倍数。一般来说，我们可以设置为。
• 误差上限需要比小很多很多，。误差越小的话，那么问题相对来说越简单。

细心的读者会发现，我们上面描述LWE问题的时候，一直在前面加上了搜索两个字。这是因为这里LWE问题的定义是，给定矩阵与误差乘积，如何能够 搜索出（search）一个合理的，使得得到的向量和问题给定的之间的误差不能超过误差上限。

然而在密码学中，一般需要证明一个困难问题的安全性的时候，我们一般都会使用决策版本的LWE问题（Decisional LWE）。决策LWE（简称为DLWE）的设定和搜索LWE（简称为SLWE）基本相同。唯一不同的是，SLWE最后的问题是需要我们找到，而DLWE只需要让我们辨别看到的到底是LWE问题中的误差乘积还是一个随机生成的向量。

DLWE问题和我们在上一篇中讨论的语义安全有一点相似。我们只能看到两个值，即和，然后我们需要辨别出我们看到的到底是一个LWE的问题实例（即），还是一个随机向量。在密码学中，我们认为DLWE问题是困难的，我们称之为DWLE假设（DLWE Assumption）。

为什么DLWE这个问题是困难的呢？其实道理很简单，因为LWE问题本身就是困难的，所以我们没有办法从这么一个向量中提取出未知向量来。也就是说，在LWE问题中，在我们的视角里，这个向量和随机向量没有任何区别，不会给我们提供任何有价值的信息。

这样一来，我们无法分辨出看到的向量究竟是LWE中的还是一个随机的向量，正好符合DLWE假设。

看到这里，对密码学熟悉的朋友们可能会对一个问题的多种版本（如搜索、决策）等等并不陌生。没错，在我们学习Diffie-Hellman公钥交换问题的时候，我们也使用了相同的问题转换。如果不了解的朋友也不用着急，容我解释一波。

Diffie-Hellman（DH）协议是一个基于循环群幂运算的公钥交换系统。简单的来说，如果我拥有秘密输入，你拥有秘密输入，那么我们可以共享给对方，然后我们就同时拥有这个秘密值了。

DH协议的难度在于在循环群中如果给定一个元素，想计算这个元素的离散对数（Discrete Log，Dlog）是非常困难的。也就是说，如果我们在公钥交换的过程中，如果给第三方偷听到了我们之间的消息，即，那么第三方也 无法根据这些消息重新构建出交换的结果出来。如果存在一个很强大的第三方，可以通过这些信息重新构建的话，那么我们就可以通过与这个第三方交互，来构建出一个可以计算任意循环群元素的离散对数的算法。因为我们假设离散对数是困难的，所以这样可以有效还原的第三方是不可能存在的。

我们把这一类的问题，即给定，计算出的问题，统称为 计算Diffie-Hellman问题（Computational Diffie-Hellman，CDH）。在使用DH协议进行公钥交换的时候，我们假设CDH是困难的。

然而，当我们需要证明包括了DH协议的加密算法（如ElGamal）的语义安全的时候，往往为了证明的需求，我们需要把问题转换成决策性的——即决策性Diffie-Hellman问题（Decisional Diffie-Hellman，DDH）。

在DDH问题中，我们会看到和一个未知的第四个值，然后我们需要去分辨这第四个值究竟是DH协议交换之后的结果，还是一个循环群中的随机元素。在ElGamal等基于循环群的加密算法中，我们一般假设DDH问题是困难的。

然而，如果我们比较DDH和CDH问题的难度的时候，我们会发现，CDH问题其实比DDH问题难的多。具体的原因我们上期其实也稍微有所讲到——因为配对（Pairing）这一特殊属性的存在。

我们都知道，如果一个循环群支持Pairing的话，那么Pairing就可以把两个中的元素，把他们幂的乘积映射到另一个循环群当中。通过Pairing，我们可以非常轻松的秒杀DDH问题：

为什么我们要长篇大论的扯DDH问题呢？这是因为，了解了SLWE/DLWE与CDH/DDH这两对密码学中被认为困难的问题之后，我们可以来比较他们的困难度分布到底是怎么样的。

DDH假设其实非常的不完美，甚至于令人头疼。因为Pairing这个后门的存在，这直接给DDH问题设置了一个惊人的困难度下限——在Pairing存在的组中，DDH问题太简单了。所以我们在挑选群的时候，一定要精心挑选。DDH的大哥CDH却不一样，因为没有任何高效率的算法可以破解离散对数，所以在任何循环群中的复杂度都较为平均。这样一来，CDH就算再困难，对于DDH的困难度分布也没有太多实质性的帮助。我们往往需要使用平均困难度来定义DDH问题的困难度（因为下限太低了）。这在密码学中是一件非常膈应人的事情，就像是我送给你一辆车，但是告诉你这个车，有一定的可能性会一开就自动散架一样。

这一段其实多少都是密码学界大家的情怀，有一个干净的定义比搞一堆乱七八糟的假设来的舒服多了。这也就是为什么格密码学那么的吸引人的原因。 不过，这些关于困难度/复杂度的小情绪，对于我们理解全同态加密是无关紧要的。大家可以当作茶余饭后的趣闻，随便看看。

如果你成功的啃完了前面的干货，看到了这里，那么恭喜你，现在你已经掌握了LWE与格密码学的基础了！

现在，当我们学会了这么多知识之后，我们可以结合一下之前学习的内容，融会贯通一下， 来看看如何使用LWE问题来构建一个格密码学中常见的公钥加密系统——Regev加密算法。

Regev加密是一个叫Regev的大佬在2005年发明出来的，是一个非常类似于ElGamal类型的公钥加密系统，基于了DLWE的假设。我们来看看它的具体定义吧：

‍

如果对Regev做的事情还是一头雾水的话，不妨我们来看一下Regev当年论文中给到的一张图。因为我们在一个有限素数域中，所以所有的数字连起来是一个环状结构，这也对应了图上的环。当我们需要加密一个bit的时候，我们就把这个bit的值映射到这个环上来——0代表环的一头（即0），1代表环的另一头（即q/2）。我们叠加的噪音就等于是把这个映射的点往上或者往下位移了一部分，这样只要噪音的大小不过分（低于q/4），我们就可以通过看这个值到底在环的哪一侧来判断这个bit的具体取值了。

最后，我们来回顾一下这一期的内容～

首先，我们一起看到了整数格（Integer Lattice）的定义，然后基于整数格了解了NP-hard的最短向量问题（ CVP）。随后，我们重新回顾了高中时期学习的求解线性方程组问题，并且统一归纳为高斯消除问题。随后，我们给高斯消除问题本身加入了一个随机的误差噪音，从而构成了我们的主角，误差还原（LWE）问题。

长按二维码添加微信进群技术讨论

info@secbit.io

安比（SECBIT）技术社区