初探全同态加密之二：格密码学与LWE问题
初探全同态加密之二：格密码学与LWE问题
上一期文章中，我们一起学习了**全同态加密（FHE）**的定义和具体的几个阶段，并且也回顾了FHE的历史。到这里，大家应该对FHE系统已经有一个比较初步的了解了。
我们在上一篇文章的结尾提到了GSW系统，也就是我们所说的第三代全同态加密系统。GSW系统的构造主要是基于格密码学中有名的LWE问题假设。为了更加方便与我们来了解GSW系统的具体构造，我们这期文章来快速地学习一下，格密码学与LWE问题究竟是什么。
格密码学（Lattice-based Crypto）是现在比较火的一个密码学分支，而且本身拥有抵抗量子计算的特性。在即将到来的NIST后量子时代加密算法标准化讨论中，基于格的加密体系就是其中的一个选择之一。不过大家不要被这些定义吓到了，其实想要理解格密码学非常简单，我们只需要一些最基本的线性代数知识。
PS：如果对线性代数内容比较生疏的话，笔者强烈建议去看3Blue1Brown大神的视频合集线性代数的本质。视频里面非常生动的描述了线性代数的基本定理。
格密码学快速入门
到底什么是格密码学？听了半天想必大家还没搞明白，其实格密码学就是基于**格（Lattice）**和格上的一些问题而定义的一套密码学体系。所以我们需要先搞明白，格到底是什么。
为了更加方便的举例子，我们这里介绍一个最简单的格系统——整数格（Integer Lattice）。
整数格（Integer Lattice）的构造
在线性代数中，我们都知道，如果要描述一个线性空间$ V $的话，我们可以找到一个代表这个空间的一组基（Basis）。反过来说，如果我们知道一个线性空间拥有两个基向量（Basis Vector）$ b_0, b_1 $，那么在这个空间里的任意一个向量都可以被分解为这两个基向量的任意线性组合。
举个例子，假如线性空间$ V $拥有两个基向量$ b_0, b_1 $，那么这个空间中的任何一个向量$ v $都可以被表示为： $$ v = c_0 \cdot b_0 = c_1 \cdot b_1$$ 这里$ c_0, c_1 $可以是任何数字。我们也可以通过改变$ c_0, c_1 $这两个数字的值来改变最后生成的向量$ v $。用这种方法可以生成的所有向量$ v $最后就会组成一个线性空间$ V $，我们称这个空间为$ b_0, b_1 $两个基向量的线性生成空间（Span）。
我们日常生活中最常见的线性生成空间，就是**XY坐标系（笛卡尔坐标系）**了。笛卡尔坐标系的基向量就是两根坐标轴对应的单位向量$ \hat{i} = \begin{bmatrix}1\0\end{bmatrix}, \hat{j} = \begin{bmatrix}0\1\end{bmatrix} $。任何在XY坐标系中的向量$ v = \begin{bmatrix}x\y\end{bmatrix} $，都可以用$ \hat{i}, \hat{j} $的线性组合来代表。
现在，如果我们再给这一个线性空间系统加上一个约束：所有的线性组合系数$ c_i $都必须是整数（Integer），那会和之前有什么不同呢？
如果所有的系数$ c_0, c_1 $都只能用整数的话，那么我们不断的变动$ c_0, c_1 $这两个系数的值，形成的向量$ v $就不能组成一个连续的线性空间了。反而，这些向量会构成一个密布的、网格状的离散集合。就想上面的图例所示，其中每一个点都代表一个可以被表达成基向量的线性组合的一个独特向量。
因为图片上看上去是网格状的，我们把这样的一个离散的基向量生成空间集合，称之为整数格（Integer Lattice）。
在这里，为了方便理解，我们举的例子仅仅是一个2维的格空间，但是其实我们可以扩展构造任意维度的格空间，唯一只需要把基向量的维度增加就好了。
实际上，如果我们需要把整数格设计成方便密码学应用的系统的话，那么我们一定需要很高的维度，才能确保问题的困难度。这个我们后续再详细描述。
整数格中的有趣问题
了解了整数格是什么之后，我们不禁会想：这玩意有什么大不了的？不就是一个离散的线性生成集合嘛。但恰巧因为这个系统是离散的，并且只允许整数出现，我们会发现有很多有趣的问题。
首先，我们回到刚刚说的线性生成空间的问题上。在$ b_0, b_1 $组成的连续的二维线性生成空间中，因为系数$ c_0, c_1 $可以是任何数字，所以我们可以表达这个二维坐标系统里的任意向量。但假如我们把这个问题约束到一个整数格中，我们就没有办法这么做了。
之前举的笛卡尔坐标系的例子里，笛卡尔空间的基向量是$ \hat{i} = \begin{bmatrix}1\0\end{bmatrix}, \hat{j} = \begin{bmatrix}0\1\end{bmatrix} $。现在假设我们在$ \hat{i}, \hat{j} $构成的整数格中，想要表达一个向量$ v = \begin{bmatrix} 2.6 \ 3.1 \end{bmatrix} $。我们会发现没有任何办法可以表达它，因为在整数格中系数$ c_0, c_1 $必须要是整数。
正因为我们无法完美的用整数格中的线性组合来表达我们想要得到的向量，这个问题衍生出了一个新的问题：是否可以找到一个最接近于想要表达的向量$ v $的值$ v’ $，并且$ v’ $恰好在这个整数格可以表达的范围当中？
结合我们的例子，重新转述一下这个问题的话，也就是说：**能否找到一组整数系数$ c_0, c_1 $，使得$ v’ = c_0 \cdot \hat{i} + c_1 \cdot \hat{j} $组成的向量$ v’ $在这个整数格中距离目标向量$ v $的距离最近？**我们观察可以发现，在我们的例子中，如果$ c_0 = 3, c_1 = 3 $，那么最后组合得到的向量$ \begin{bmatrix} 3 \ 3 \end{bmatrix} $距离我们目标$ \begin{bmatrix} 2.6 \ 3.1 \end{bmatrix} $的距离是最近的。
我们把这一类在离散线性集合中逼近目标向量的问题，统称为最近向量问题（Closest Vector Problem，CVP）。在复杂度理论中已经被证实，在一个足够复杂维度的空间里，CVP问题是非常难解决的（NP-hard）！也就是说，给定一组基向量$ b_i $，和一个目标向量$ v $，我们很难有效的找到一组整数线性组合$ c_i $，使得$ v’ \leftarrow \sum_i c_i \cdot b_i $所组成的向量$ v’ $距离我们的目标最近。
这个很难的问题，就是格密码学的开端了。基于CVP问题，我们可以从而衍生出一个新的难题：Learning With Error（LWE）问题。
PS：格密码学中还有另一个难题叫SVP问题（Shortest Vector Problem），和CVP不同但也是NP-hard的问题。我们在这里就不多解释了。
Learning With Error（LWE）问题
读到这里，想必大家应该对整数格已经有了一个大致的理解，并且也知道了整数格中的一个难问题：CVP问题。现在我们一起来看看，如何从CVP问题出发，衍生到我们的主角LWE问题上。为了更加方便理解LWE，我们不妨先来回顾一下中学数学～
我们在初中或者高中的数学课上应该都学过如何求解线性方程组（solve system of equations）。一般来说，我们会给到一组多元一次方程： $$ 3x_1 + 4x_2 + x_3 = 0\ 4x_1 + 2x_2 + 6x_3 = 1\ x_1 + x_2 + x_3 = 1$$ 然后我们需要求解里面的每个未知数$ x_1, x_2, x_3 $。求解这样的问题对于我们来说非常简单：我们只需要拿起一行的等式，再加上/减去另一行的等式，最终就可以得到这三个未知数之间的直接关系，然后得到他们的值了。比如如果我们用第一行减去第三行，我们就可以得到新的等式$ 2x_1 + 3x_3 = -1 $。
如果这个线性方程组题目出的比较好的话，那么一般我们重复的让这些等式相加/相减几次之后，就可以得到比较确定的答案了，比如$ x_1 = 1, x_2 = -3 $之类的。最后我们就可以把这几个已知数再代入回去，然后求解剩下的未知数。
当我们系统性的学习了线性代数之后，我们可以把求解线性方程组的问题用矩阵来表达： $$ Ax = b\ \begin{bmatrix} 3 & 4 & 1\ 4 & 2 & 6\ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} x_1\ x_2\ x_3 \end{bmatrix}
\begin{bmatrix} 0\ 1\ 1 \end{bmatrix}$$ 用矩阵的形式来表示之后，这个问题求解的方法也和之前的方法一样：我们可以把矩阵$ A $和$ b $的行与行之间相加或相减，然后最后得到未知数的结果。我们把这一类行与行之间操作求解未知数的方法统称为高斯消除法（Gaussian Elimination）。高斯消除法系统性的定义就是，给定一个矩阵$ A $和一个向量$ b $，能否找到一个向量$ x $，使得$ Ax = b $的关系满足。
有噪音的高斯消除问题（Gaussian Elimination with Noise）
当我们学会如何求解线性方程组之后，我们发现这其实并不是什么难的问题，只需要不停地在行与行之间相互使用高斯消除，就可以得到未知数的解。毕竟这也是中学的时候学的数学题，难不到哪里去。
现在，我们把这个高斯消除问题变化一下，给它增加一些难度：增加噪音。
假如这个问题变成，如果已知一个矩阵$ A $，并且我们还知道一个向量: $$ \hat{b} = Ax + e$$ 其中$ e $是我们在一个固定数值范围内随机采集的一个随机噪音向量，能否有效的通过$ A $和$ \hat{b} $的值来还原最初的未知数向量$ x $？
加上这么一个随机噪音之后，我们线性代数的方法就已经不管用了，因为如果我们使用高斯消除法对每一行进行消除的时候，同时还会带着噪音进去，所以导致无法算出任何一个未知数的值。似乎唯一能够找到$ x $的方法就是暴力破解，一个一个猜$ x $的可能值，然后逐渐逼近$ \hat{b} $。
总结一下，带上了噪音之后，这个问题就变成了已知一个矩阵$ A $，和它与一个向量$ x $相乘得到的乘积再加上一定的误差（error）$ e $，即$ Ax + e $，如何有效的还原（learn）未知的向量。我们把这一类的问题统称为误差还原（Learning With Error， LWE）问题。为了方便表述，我们后面都称之为LWE。
如果细心的看LWE的问题描述的话，我们可以发现，这个LWE问题与我们之前提到的CVP最短向量问题有着惊人的相似。其实两个问题都一样，我们都是需要找到一组“系数”（我们可以用向量$ x $来表示），使得一组基向量（我们用矩阵$ A $来表示）的线性组合无限逼近我们想要的目标向量$ \hat{b} $。这里我们使用误差噪音$ e $的大小来定义到底我们需要距离目标向量$ \hat{b} $多近。
这样说来，如果CVP是一个**复杂度很高（NP-hard）的问题的话，那么相对应的，LWE问题也是一个复杂度很高（NP-hard）**的问题了。
大家应该对LWE是什么有概念了吧？接下来，我们来看LWE的正式定义！
搜索LWE问题（Search LWE Problem）的正式定义
首先，我们需要熟悉一下，LWE问题里面需要用到的一些关键概念：
- 首先，为了密码学的应用以及方便计算，我们使用$ \mathbb{Z}_q $这么一个素数有限域。具体来说，也就是我们的世界里只存在$ (-q/2, q/2) $这个范围内的所有整数。
- 为了更好的衡量噪音，我们定义$ \mid\mid e \in \mathbb{Z}q^m \mid\mid\infty $为向量$ e $（维度为$ m $）的无限范数（Infinity Norm），具体操作就是看$ e $这个向量中的每一个值，然后返回最大的那个。$ \mid\mid e \mid\mid_\infty = max_i^m \mid e_i \mid $
- 最后，我们定义$ x_B $就是为一个最大值封顶为$ B $的随机分布。也就是说，从这个随机分布中取出的每一个随机值都会小于$ B $。$ \forall x \leftarrow x_B^m: \mid\mid x \mid\mid_\infty \le B $
结合上述的概念，搜索LWE问题的正式定义如下： $$ LWE(n, m, q, x_B): \text{ Search Version}\ \text{Let } A \stackrel{R}{\leftarrow} \mathbb{Z}_q^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_q, e \stackrel{R}{\leftarrow} x_B.\ \text{Given } (A, As + e) \text{, find } s’ \in \mathbb{Z}q^n \text{ s.t. } \mid\mid As’ - (As + e) \mid\mid\infty \le B$$
参数详细说明
是不是乍一看一堆符号有些难以理解？莫慌，让我们来逐一看看这个定义到底是什么意思。
简单的来说，在一个LWE问题当中，我们首先需要定义矩阵$ A $的维度为$ m \times n $。$ m $代表了这个线性方程组一共有多少组方程，而$ n $代表了每个方程中有多少个未知数。我们还需要定义整个有限域$ \mathbb{Z}_q $的大小$ q $，一般来说我们都会选择一个足够大的素数作为$ q $的值。最后，我们需要决定我们叠加的误差噪音的取值上限$ B $。$ B $的大小决定了我们LWE问题中需要找到的解距离实际的取值$ \hat{b} $究竟可以相差多少。
定义了上面的这些参数之后，LWE问题就很好理解了：给定矩阵$ A $以及带有误差的乘积$ As + e $，还原出未知的向量$ s $。
我们发现LWE问题，不同于平常的密码学难题（比如离散对数问题），可以变的参数（$ n, m, q, B $）实在是太多了。我们可以再来仔细看一下每一个参数，试图理解一下改变每个参数会怎么改变这个问题的难度：
- $ n $一般来说都被称为整个LWE问题的安全参数（Security Parameter）。如果一个系统中的未知变量越多（即$ n $越大），那么整个LWE问题会越难。
- $ m $一般来说都是$ n $的一个多项式倍数，$ m = poly(n) $。如果可以用的方程组越多（即$ m $越大），那么代表整个LWE问题会越简单。
- $ q $一般也是$ n $的一个多项式倍数。一般来说，我们可以设置$ q $为$ O(n^2) $。
- 误差上限$ B $需要比$ q $小很多很多，$ B « q $。误差越小的话，那么找到正确的解相对来说越简单。
一般来说，这么多参数一个一个设置的话太费劲，所以我们都会只指定一个参数$ n $，然后把其他参数$ m, q, B $都设置成一个函数$ f(n) $的输出。只要参数设置的符合问题定义的要求，我们就可以保证随后生成的LWE问题实例（跑roblem instance）很大概率会拥有一个唯一的解$ x $。
从搜索LWE（Search LWE）到决策LWE（Decisional LWE）
细心的读者会发现，我们上面描述LWE问题的时候，一直在前面加上了搜索两个字。这是因为这里LWE问题的定义是，给定矩阵$ A $与误差乘积$ As + e $，如何能够**搜索出（search）**一个合理的$ s’ $，使得$ As’ $得到的向量和问题给定的$ As + e $之间的误差不能超过误差上限$ B $。
然而在密码学中，一般需要证明一个困难问题的安全性的时候，我们一般都会使用决策版本的LWE问题（Decisional LWE）。决策LWE（简称为DLWE）的设定和搜索LWE（简称为SLWE）基本相同。唯一不同的是，SLWE最后的问题是需要我们找到$ s $，而DLWE只需要让我们辨别看到的$ \hat{b} $到底是LWE问题中的误差乘积还是一个随机生成的向量。 $$ LWE(n, m, q, x_B): \text{ Decisional Version}\ \text{Let } A \stackrel{R}{\leftarrow} \mathbb{Z}_q^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_q, e \stackrel{R}{\leftarrow} x_B, v \stackrel{R}{\leftarrow} \mathbb{Z}_q^m.\ \text{Distinguish } (A, As+e) \text{ from } (A, v).$$ DLWE问题和我们在上一篇中讨论的语义安全有一点相似。我们只能看到两个值，即$ A $和$ \hat{b} $，然后我们需要辨别出我们看到的到底是一个LWE的问题实例（即$ \hat{b} = As + e $），还是一个随机向量$ v $。在密码学中，我们认为DLWE问题是困难的，我们称之为DWLE假设（DLWE Assumption）。
为什么DLWE这个问题是困难的呢？其实道理很简单，因为LWE问题本身就是困难的，所以我们没有办法从$ As + e $这么一个向量中提取出未知向量$ x $来。也就是说，在LWE问题中，在我们的视角里，$ As + e $这个向量和随机向量没有任何区别，不会给我们提供任何有价值的信息。
这样一来，我们无法分辨出看到的向量$ \hat{b} $究竟是LWE中的$ As + e $还是一个随机的向量，正好符合DLWE假设。
Diffie-Hellman公钥交换中的离散对数问题（Dlog Problem）
看到这里，对密码学熟悉的朋友们可能会对一个问题的多种版本（如搜索、决策）等等并不陌生。没错，在我们学习Diffie-Hellman公钥交换问题的时候，我们也使用了相同的问题转换。如果不了解的朋友也不用着急，容我解释一波。
Diffie-Hellman（DH）协议是一个基于循环群幂运算的公钥交换系统。简单的来说，如果我拥有秘密输入$ a $，你拥有秘密输入$ b $，那么我们可以共享$ g^a, g^b $给对方，然后我们就同时拥有$ g^{ab} $这个秘密值了。
DH协议的难度在于在循环群中如果给定一个元素$ g^x $，想计算这个元素的离散对数（Discrete Log，Dlog）是非常困难的。也就是说，如果我们在公钥交换的过程中，如果给第三方偷听到了我们之间的消息，即$ (g, g^a, g^b) $，那么第三方也无法根据这些消息重新构建出交换的结果$ g^{ab} $出来。如果存在一个很强大的第三方，可以通过这些信息重新构建$ g^{ab} $的话，那么我们就可以通过与这个第三方交互，来构建出一个可以计算任意循环群元素的离散对数的算法。因为我们假设离散对数是困难的，所以这样可以有效还原$ g^{ab} $的第三方是不可能存在的。
我们把这一类的问题，即给定$ (g, g^a, g^b) $，计算出$ g^{ab} $的问题，统称为计算Diffie-Hellman问题（Computational Diffie-Hellman，CDH）。在使用DH协议进行公钥交换的时候，我们假设CDH是困难的。
然而，当我们需要证明包括了DH协议的加密算法（如ElGamal）的语义安全的时候，往往为了证明的需求，我们需要把问题转换成决策性的——即决策性Diffie-Hellman问题（Decisional Diffie-Hellman，DDH）。 $$ DDH(g):\ \text{Let } a, b, r \stackrel{R}{\leftarrow} \mathbb{Z}_q.\ \text{Distinguish } (g, g^a, g^b, g^{ab}) \text{ from } (g, g^a, g^b, g^r)$$ 在DDH问题中，我们会看到$ (g, g^a, g^b) $和一个未知的第四个值，然后我们需要去分辨这第四个值究竟是DH协议交换之后的结果$ g^{ab} $，还是一个循环群中的随机元素$ g^r $。在ElGamal等基于循环群的加密算法中，我们一般假设DDH问题是困难的。
然而，如果我们比较DDH和CDH问题的难度的时候，我们会发现，CDH问题其实比DDH问题难的多。具体的原因我们上期其实也稍微有所讲到——因为**配对（Pairing）**这一特殊属性的存在。
我们都知道，如果一个循环群$ \mathbb{G} $支持Pairing的话，那么Pairing就可以把两个$ \mathbb{G} $中的元素，把他们幂的乘积映射到另一个循环群$ \mathbb{G}_T $当中。通过Pairing，我们可以非常轻松的秒杀DDH问题： $$ e(g^a, g^b) = g(g^{ab}, g) = g^{ab}_T \ne g^r_T = e(g^r, g)$$ 如果我们面对一个DDH的问题，想要辨别第四个未知的元素究竟是$ g^{ab} $还是随机的$ g^r $的时候，我们可以通过Pairing运算把已知的$ g^a, g^b $转换为$ g^{ab}_T $。然后剩下的就是把第四个元素转换到$ \mathbb{G}_T $这个群里去，比较他们的幂是不是相等的。这也就是说，如果一个循环群拥有Pairing特性的话，DDH问题是非常容易的。所以如果我们要使用ElGamal来加密的话，切记一定要选择没有Pairing属性的循环群～
DLWE与DDH的困难度比较
为什么我们要长篇大论的扯DDH问题呢？这是因为，了解了SLWE/DLWE与CDH/DDH这两对密码学中被认为困难的问题之后，我们可以来比较他们的困难度分布到底是怎么样的。
DDH假设其实非常的不完美，甚至于令人头疼。因为Pairing这个后门的存在，这直接给DDH问题设置了一个惊人的困难度下限——在Pairing存在的组中，DDH问题太简单了。所以我们在挑选群的时候，一定要精心挑选。DDH的大哥CDH却不一样，因为没有任何高效率的算法可以破解离散对数，所以在任何循环群中的复杂度都较为平均。这样一来，CDH就算再困难，对于DDH的困难度分布也没有太多实质性的帮助。我们往往需要使用平均困难度来定义DDH问题的困难度（因为下限太低了）。这在密码学中是一件非常膈应人的事情，就像是我送给你一辆车，但是告诉你这个车，有一定的可能性会一开就自动散架一样。
相比起来，LWE问题就完美许多。因为没有任何像Pairing一样的后门的存在，所以DLWE问题其实和SLWE的困难度是相同的。因为不管是解决DLWE还是SLWE，我们都会被卡在如何还原未知向量$ s $这一步上面。像这一类就算问题形式被转换，但是复杂度保证大致相同的问题，在密码学中是不可多得的宝贝。对于DLWE问题的困难度，我们可以很优雅的使用**最坏困难度（Worst Case Performance）**来定义。
这一段其实多少都是密码学界大家的情怀，有一个干净的定义比搞一堆乱七八糟的假设来的舒服多了。**这也就是为什么格密码学那么的吸引人的原因。**不过，这些关于困难度/复杂度的小情绪，对于我们理解全同态加密是无关紧要的。大家可以当作茶余饭后的趣闻，随便看看。
DLWE的实战应用：格密码学与Regev加密算法
如果你成功的啃完了前面的干货，看到了这里，那么恭喜你，现在你已经掌握了LWE与格密码学的基础了！
现在，当我们学会了这么多知识之后，我们可以结合一下之前学习的内容，融会贯通一下， 来看看如何使用LWE问题来构建一个格密码学中常见的公钥加密系统——Regev加密算法。
Regev加密是一个叫Regev的大佬在2005年发明出来的，是一个非常类似于ElGamal类型的公钥加密系统，基于了DLWE的假设。我们来看看它的具体定义吧：
- $ KeyGen(1^\lambda) $：KeyGen算法首先要生成一个LWE问题的实例。具体来说，我们需要根据安全参数$ \lambda $确定$ n $的值，然后依次计算出$ m, q, B $的值。然后我们随机的选取LWE问题中所需的矩阵$ A \stackrel{R}{\leftarrow} \mathbb{Z}_q^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_q^n, e \stackrel{R}{\leftarrow} x_B^m $，并且计算出误差乘积$ b = As + e $。还有一个额外的约束条件是，我们这里选取的$ B $的值一定要符合$ q/4 > mB $这一条件，才可以使得Regev算法拥有正确性（Correctness）。最后，我们输出私钥$ sk = s $，公钥$ pk = (A, b) $。
- $ Encrypt(pk, x \in {0, 1}) $：Regev的加密算法其实是对每一个二进制位单独进行加密的，一次只可以处理一个bit。和ElGamal加密的思路相同，首先我们需要随机的选取一个nonce向量$ r \stackrel{R}{\leftarrow} \mathbb{Z}_2^m \in {0,1}^m $，然后计算出密文的第一部分$ c_0 \leftarrow r^TA $。随后，我们计算出密文的第二部分$ c_1 \leftarrow r^Tb + \lfloor q/2 \rfloor x $。最后我们输出$ (c_0, c_1) $作为最后的加密密文。
- $ Decrypt(sk, ct = (c_0, c_1)) $：如果要解密密文的话，我们只需要计算$ \hat{x} = c_1 - c_0 \cdot s $，然后我们可以检查这个结果的绝对值是否在一个预先设定好的范围内$ \mid \hat{x} \mid < q/4 $。如果在，那么输出$ x = 0 $，不然输出$ x = 1 $。
Regev加密的正确性
Regev加密算法的正确性（Correctness）其实挺好理解的，我们可以把解密部分所做的计算展开： $$ \tilde{x} = c_1 - c_0 \cdot s\ = r^Tb + q/2 \cdot x - r^TAs\ = r^T(As + e) - r^TAs + q/2 \cdot x\ = r^Te + q/2 \cdot x$$ 通过观察我们可以发现，其实我们最后还原得到的$ \hat{x} $，就是一开始的原文这个bit的值乘以$ q/2 $，然后加上了$ r^Te $这么多的误差噪音而已。我们还可以发现，$ r $就是一个随机的二进制向量，也就是说向量中每个值只能取值在$ {0, 1} $的范围之中。再加上$ e $这个误差向量中每一个值的最大上限就是$ B $，所以最坏的情况下，我们的误差噪音最大可以达到$ mB $这么大。因为我们在给出Regev加密的定义的时候就严格规定了$ q/4 > mB $ 的约束，所以我们的误差是不会改变解密算法的正确性的，因为就算噪音再大，最后的$ \hat{x} $也会掉落在可以被辨别的区间当中。
如果对Regev做的事情还是一头雾水的话，不妨我们来看一下Regev当年论文中给到的一张图。因为我们在一个有限素数域中，所以所有的数字连起来是一个环状结构，这也对应了图上的环。当我们需要加密一个bit的时候，我们就把这个bit的值映射到这个环上来——0代表环的一头（即0），1代表环的另一头（即q/2）。我们叠加的噪音就等于是把这个映射的点往上或者往下位移了一部分，这样只要噪音的大小不过分（低于q/4），我们就可以通过看这个值到底在环的哪一侧来判断这个bit的具体取值了。
看到这里，想必有些朋友可能会突然恍然大悟——Regev加密中的这个噪音，和我们上一期提到的有限级数全同态加密的噪音概念非常相似！的确，全同态加密体系的实现，和我们这里提到的把一个bit映射到环上并且叠加噪音的场景非常相似。一旦叠加的噪音超过了临界值（$ q/4 $），我们就无法判断这个bit到底原来是1还是0了，我们也就无法还原这段密文了。具体的内容留个悬念，我们下期继续讨论～
Regev加密的安全性
刚才属性的话题讨论到一半，我们打了个岔。最后我们回来继续学习一下，Regev加密系统的安全性（Security）。
为了证明Regev加密体系是语义安全的，我们需要使用密码学中的一种常见的证明工具：混合论证法（Hybrid Argument）。混合论证其实并不是什么黑科技，而是我们把要证明的问题划分成若干小步，然后逐步证明罢了。
首先，我们来看一下，假如一个第三方偷看到了Regev加密系统的加密密文的所有消息，那么他的世界观是这样的： $$ H_0 : pk = (A, b = As + e), c_0 = r^TA, c_1 = r^Tb + q/2 \cdot x$$ 接着，我们可以创建第二个相似的世界观： $$ H_1 : pk = (A, v \stackrel{R}{\leftarrow} \mathbb{Z}_q^m), c_0 = r^TA, c_1 = r^Tb + q/2 \cdot x$$ 我们知道，因为DLWE假设，所以第三方是无法分辨LWE实例与随机向量的。所以我们可以把$ As + e $这一部分替换为随机向量$ v $。接着，我们来构造第三个相似世界观： $$ H_2 : pk = (A, v \stackrel{R}{\leftarrow} \mathbb{Z}_q^m), c_0 \stackrel{R}{\leftarrow} \mathbb{Z}_q^n, c_1 \stackrel{R}{\leftarrow} \mathbb{Z}_q$$ 第三个世界观中，我们把其他所有的非随机参数，全部替换成了随机向量。由于一个特殊的叫做剩余哈希定理（Leftover Hash Lemma）的原因，我们可以认为世界观$ H_1 $和$ H_2 $是无法被第三方辨别的。
综上所述，因为第三方无法辨别$ H_0 $与$ H_1 $，并且他也无法辨别$ H_1 $与$ H_2 $，所以我们可以推导出第三方肯定也无法有效的辨别$ H_0 $与$ H_2 $。因为$ H_2 $当中已经没有任何和加密原文$ x $有关的信息了，全部都是随机生成的参数，所以我们可以下结论：Regev加密体系是语义安全的。
未完待续：构建有限级数全同态算法
最后，我们来回顾一下这一期的内容～
首先，我们一起看到了整数格（Integer Lattice）的定义，然后基于整数格了解了NP-hard的最短向量问题（ CVP）。随后，我们重新回顾了高中时期学习的求解线性方程组问题，并且统一归纳为高斯消除问题。随后，我们给高斯消除问题本身加入了一个随机的误差噪音，从而构成了我们的主角，误差还原（LWE）问题。
了解了LWE是什么之后，我们又详细学习了LWE问题的正式定义，以及其中的$ n, m, q, B $等参数。接着我们把搜索LWE（SLWE）转换为决策LWE（DLWE）问题，然后探讨了SLWE/DLWE的假设为什么比CDH/DDH更好。最后，我们结合了所有学习的知识，一起构建了格密码学中很经典的Regev加密算法，通过LWE的困难假设对密文（一个bit）进行加密。
如果你读到这里，并且成功的理解了所有的内容的话，**那么其实你已经掌握了全同态加密80%的精髓了！**接下来，我们需要做的只是把这些部分像搭积木一样搭起来，就可以构成我们想要的全同态加密系统了。
由于篇幅原因，我们这一期就写到这里。下一期，我们使用这期学到的知识，一起来构建一个有限级数全同态加密体系。