初探全同态加密之二：格密码学与LWE问题
上一期文章中，我们一起学习了 全同态加密（FHE） 的定义和具体的几个阶段，并且也回顾了FHE的历史。到这里，大家应该对FHE系统已经有一个比较初步的了解了。
我们在上一篇文章的结尾提到了GSW系统，也就是我们所说的第三代全同态加密系统。GSW系统的构造主要是基于格密码学中有名的LWE问题假设。为了更加方便与我们来了解GSW系统的具体构造，我们这期文章来快速地学习一下，格密码学与LWE问题究竟是什么。
格密码学（Lattice-based Crypto）是现在比较火的一个密码学分支，而且本身拥有抵抗量子计算的特性。在即将到来的NIST后量子时代加密算法标准化讨论中，基于格的加密体系就是其中的一个选择之一。不过大家不要被这些定义吓到了，其实想要理解格密码学非常简单，我们只需要一些最基本的线性代数知识。
PS：如果对线性代数内容比较生疏的话，笔者强烈建议去看3Blue1Brown大神的视频合集线性代数的本质。视频里面非常生动的描述了线性代数的基本定理。
格密码学快速入门
到底什么是格密码学？听了半天想必大家还没搞明白，其实格密码学就是基于格（Lattice ）和格上的一些问题而定义的一套密码学体系。所以我们需要先搞明白，格到底是什么。
为了更加方便的举例子，我们这里介绍一个最简单的格系统——整数格（Integer Lattice）。
整数格（Integer Lattice）的构造
现在，如果我们再给这一个线性空间系统加上一个约束：所有的线性组合系数都必须是整数（Integer），那会和之前有什么不同呢？
因为图片上看上去是网格状的，我们把这样的一个离散的基向量生成空间集合，称之为整数格（Integer Lattice）。
在这里，为了方便理解，我们举的例子仅仅是一个2维的格空间，但是其实我们可以扩展构造任意维度的格空间，唯一只需要把基向量的维度增加就好了。
实际上，如果我们需要把整数格设计成方便密码学应用的系统的话，那么我们一定需要很高的维度，才能确保问题的困难度。这个我们后续再详细描述。
整数格（Integer Lattice）的构造
了解了整数格是什么之后，我们不禁会想：这玩意有什么大不了的？不就是一个离散的线性生成集合嘛。但恰巧因为这个系统是离散的，并且只允许整数出现，我们会发现有很多有趣的问题。
这个很难的问题，就是格密码学的开端了。基于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）。一般来说，我们会给到一组多元一次方程：
有噪音的高斯消除问题（Gaussian Elimination with Noise）
当我们学会如何求解线性方程组之后，我们发现这其实并不是什么难的问题，只需要不停地在行与行之间相互使用高斯消除，就可以得到未知数的解。毕竟这也是中学的时候学的数学题，难不到哪里去。
现在，我们把这个高斯消除问题变化一下，给它增加一些难度：增加噪音。
假如这个问题变成，如果已知一个矩阵A，并且我们还知道一个向量:
这样说来，如果CVP是一个复杂度很高（NP-hard） 的问题的话，那么相对应的，LWE问题也是一个 复杂度很高（NP-hard ）的问题了。
大家应该对LWE是什么有概念了吧？接下来，我们来看LWE的正式定义！
搜索LWE问题（Search LWE Problem）的正式定义
首先，我们需要熟悉一下，LWE问题里面需要用到的一些关键概念：
参数详细说明
是不是乍一看一堆符号有些难以理解？莫慌，让我们来逐一看看这个定义到底是什么意思。
从搜索LWE（Search LWE）到决策LWE（Decisional LWE）
Diffie-Hellman公钥交换中的离散对数问题（Dlog Problem）
看到这里，对密码学熟悉的朋友们可能会对一个问题的多种版本（如搜索、决策）等等并不陌生。没错，在我们学习Diffie-Hellman公钥交换问题的时候，我们也使用了相同的问题转换。如果不了解的朋友也不用着急，容我解释一波。
然而，如果我们比较DDH和CDH问题的难度的时候，我们会发现，CDH问题其实比DDH问题难的多。具体的原因我们上期其实也稍微有所讲到——因为配对（Pairing）这一特殊属性的存在。
DLWE与DDH的困难度比较
为什么我们要长篇大论的扯DDH问题呢？这是因为，了解了SLWE/DLWE与CDH/DDH这两对密码学中被认为困难的问题之后，我们可以来比较他们的困难度分布到底是怎么样的。
DDH假设其实非常的不完美，甚至于令人头疼。因为Pairing这个后门的存在，这直接给DDH问题设置了一个惊人的困难度下限——在Pairing存在的组中，DDH问题太简单了。所以我们在挑选群的时候，一定要精心挑选。DDH的大哥CDH却不一样，因为没有任何高效率的算法可以破解离散对数，所以在任何循环群中的复杂度都较为平均。这样一来，CDH就算再困难，对于DDH的困难度分布也没有太多实质性的帮助。我们往往需要使用平均困难度来定义DDH问题的困难度（因为下限太低了）。这在密码学中是一件非常膈应人的事情，就像是我送给你一辆车，但是告诉你这个车，有一定的可能性会一开就自动散架一样。
相比起来，LWE问题就完美许多。因为没有任何像Pairing一样的后门的存在，所以DLWE问题其实和SLWE的困难度是相同的。因为不管是解决DLWE还是SLWE，我们都会被卡在如何还原未知向量这一步上面。像这一类就算问题形式被转换，但是复杂度保证大致相同的问题，在密码学中是不可多得的宝贝。对于DLWE问题的困难度，我们可以很优雅的使用最坏困难度（Worst Case Performance）来定义。
这一段其实多少都是密码学界大家的情怀，有一个干净的定义比搞一堆乱七八糟的假设来的舒服多了。这也就是为什么格密码学那么的吸引人的原因。 不过，这些关于困难度/复杂度的小情绪，对于我们理解全同态加密是无关紧要的。大家可以当作茶余饭后的趣闻，随便看看。
DLWE的实战应用：格密码学与Regev加密算法
如果你成功的啃完了前面的干货，看到了这里，那么恭喜你，现在你已经掌握了LWE与格密码学的基础了！
现在，当我们学会了这么多知识之后，我们可以结合一下之前学习的内容，融会贯通一下， 来看看如何使用LWE问题来构建一个格密码学中常见的公钥加密系统——Regev加密算法。
Regev加密是一个叫Regev的大佬在2005年发明出来的，是一个非常类似于ElGamal类型的公钥加密系统，基于了DLWE的假设。我们来看看它的具体定义吧：
Regev加密的正确性
Regev加密算法的正确性（Correctness）其实挺好理解的，我们可以把解密部分所做的计算展开：
如果对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加密系统的加密密文的所有消息，那么他的世界观是这样的：
未完待续：构建有限级数全同态算法
最后，我们来回顾一下这一期的内容～
首先，我们一起看到了整数格（Integer Lattice）的定义，然后基于整数格了解了NP-hard的最短向量问题（ CVP）。随后，我们重新回顾了高中时期学习的求解线性方程组问题，并且统一归纳为高斯消除问题。随后，我们给高斯消除问题本身加入了一个随机的误差噪音，从而构成了我们的主角，误差还原（LWE）问题。
了解了LWE是什么之后，我们又详细学习了LWE问题的正式定义，以及其中的等参数。接着我们把搜索LWE（SLWE）转换为决策LWE（DLWE）问题，然后探讨了SLWE/DLWE的假设为什么比CDH/DDH更好。最后，我们结合了所有学习的知识，一起构建了格密码学中很经典的Regev加密算法，通过LWE的困难假设对密文（一个bit）进行加密。
如果你读到这里，并且成功的理解了所有的内容的话，那么其实你已经掌握了全同态加密80%的精髓了！ 接下来，我们需要做的只是把这些部分像搭积木一样搭起来，就可以构成我们想要的全同态加密系统了。
由于篇幅原因，我们这一期就写到这里。下一期，我们使用这期学到的知识，一起来构建一个有限级数全同态加密体系。
