最后，我们往返首一下这一期的内容～
Regev加密的正确性
上一期文章中，我们一起进修了 全同态加密（FHE） 的界说和详细的几个阶段，而且也回首了FHE的汗青。到这里，各人应该对FHE系统已经有一个较量劈头的相识了。
有噪音的高斯消除问题（Gaussian Elimination with Noise）
此刻，我们把这个高斯消除问题变革一下，给它增加一些难度：增加噪音。
Learning With Error（LWE）问题
格暗码学（Lattice-based Crypto）是此刻较量火的一个暗码学分支，并且自己拥有抵挡量子计较的特性。在即将到来的NIST后量子时代加密算法尺度化接头中，基于格的加密体系就是个中的一个选择之一。不外各人不要被这些界说吓到了，其实想要领略格暗码学很是简朴，我们只需要一些最根基的线性代数常识。
假如你读到这里，而且乐成的领略了所有的内容的话，那么其实你已经把握了全同态加密80%的精华了！ 接下来，我们需要做的只是把这些部门像搭积木一样搭起来，就可以组成我们想要的全同态加密系统了。
实际上，假如我们需要把整数格设计成利便暗码学应用的系统的话，那么我们必然需要很高的维度，才气确保问题的坚苦度。这个我们后续再具体描写。
读到这里，想必各人应该对整数格已经有了一个大抵的领略，而且也知道了整数格中的一个难问题：CVP问题。此刻我们一起来看看，如何从CVP问题出发，衍生到我们的主角LWE问题上。为了越发利便领略LWE，我们不妨先往返首一下中学数学～
DDH假设其实很是的不完美，甚至于令人头疼。因为Pairing这个后门的存在，这直接给DDH问题配置了一个惊人的坚苦度下限——在Pairing存在的组中，DDH问题太简朴了。所以我们在挑选群的时候，必然要经心挑选。DDH的年迈CDH却纷歧样，因为没有任何高效率的算法可以破解离散对数，所以在任何轮回群中的巨大度都较为平均。这样一来，CDH就算再坚苦，对付DDH的坚苦度漫衍也没有太多实质性的辅佐。我们往往需要利用平均坚苦度来界说DDH问题的坚苦度（因为下限太低了）。这在暗码学中是一件很是膈应人的工作，就像是我送给你一辆车，可是汇报你这个车，有必然的大概性会一开就自动散架一样。
是不是乍一看一堆标记有些难以领略？莫慌，让我们来逐一看看这个界说到底是什么意思。
Regev加密算法的正确性（Correctness）其实挺好领略的，我们可以把解密部门所做的计较展开：
当我们学会如何求解线性方程组之后，我们发明这其实并不是什么难的问题，只需要不断地在行与行之间彼此利用高斯消除，就可以获得未知数的解。究竟这也是中学的时候学的数学题，难不到那边去。
PS：格暗码学中尚有另一个困难叫SVP问题（Shortest Vector Problem），和CVP差异但也是NP-hard的问题。我们在这里就不多表明白。
PS：假如对线性代数内容较量陌生的话，笔者强烈发起去看3Blue1Brown大神的视频合集线性代数的本质。视频内里很是活跃的描写了线性代数的根基定理。
如果这个问题酿成，假如已知一个矩阵A，而且我们还知道一个向量:
对比起来，LWE问题就完美很多。因为没有任何像Pairing一样的后门的存在，，所以DLWE问题其实和SLWE的坚苦度是沟通的。因为不管是办理DLWE照旧SLWE，我们城市被卡在如何还原未知向量这一步上面。像这一类就算问题形式被转换，可是巨大度担保大抵沟通的问题，在暗码学中是不行多得的宝物。对付DLWE问题的坚苦度，我们可以很优雅的利用最坏坚苦度（Worst Case Performance）来界说。
在这里，为了利便领略，我们举的例子仅仅是一个2维的格空间，可是其实我们可以扩展结构任意维度的格空间，独一只需要把基向量的维度增加就好了。
假如你乐成的啃完了前面的干货，看到了这里，那么恭喜你，此刻你已经把握了LWE与格暗码学的基本了！
此刻，当我们学会了这么多常识之后，我们可以团结一下之前进修的内容，交融意会一下， 来看看如何利用LWE问题来构建一个格暗码学中常见的公钥加密系统——Regev加密算法。
整数格（Integer Lattice）的结构
我们在初中可能高中的数学课上应该都学过如何求解线性方程组（solve system of equations）。一般来说，我们会给到一组多元一次方程：
此刻，假如我们再给这一个线性空间系统加上一个约束：所有的线性组合系数都必需是整数（Integer），那会和之前有什么差异呢？
这一段其实几多都是暗码学界各人的情怀，有一个清洁的界说比搞一堆参差不齐的假设来的舒服多了。这也就是为什么格暗码学那么的吸引人的原因。 不外，这些关于坚苦度/巨大度的小情绪，对付我们领略全同态加密是无关紧急的。各人可以看成茶余饭后的趣闻，随便看看。为什么我们要长篇大论的扯DDH问题呢？这是因为，相识了SLWE/DLWE与CDH/DDH这两对暗码学中被认为坚苦的问题之后，我们可以来较量他们的坚苦度漫衍到底是怎么样的。
这样说来，假如CVP是一个巨大度很高（NP-hard） 的问题的话，那么相对应的，LWE问题也是一个 巨大度很高（NP-hard ）的问题了。
适才属性的话题接头到一半，我们打了个岔。最后我们返来继承进修一下，Regev加密系统的安详性（Security）。
整数格（Integer Lattice）的结构
首先，我们一起看到了整数格（Integer Lattice）的界说，然后基于整数格相识了NP-hard的最短向量问题（ CVP）。随后，我们从头回首了高中时期进修的求解线性方程组问题，而且统一归纳为高斯消除问题。随后，我们给高斯消除问题自己插手了一个随机的误差噪音，从而组成了我们的主角，误差还原（LWE）问题。看到这里，对暗码学熟悉的伴侣们大概会对一个问题的多种版本（如搜索、决定）等等并不生疏。没错，在我们进修Diffie-Hellman公钥互换问题的时候，我们也利用了沟通的问题转换。假如不相识的伴侣也不消着急，容我表明一波。
Diffie-Hellman公钥互换中的离散对数问题（Dlog Problem）
相识了整数格是什么之后，我们不禁会想：这玩意有什么大不了的？不就是一个离散的线性生成荟萃嘛。但刚巧因为这个系统是离散的，而且只答允整数呈现，我们会发明有许多有趣的问题。
看到这里，想必有些伴侣大概会溘然名顿开——Regev加密中的这个噪音，和我们上一期提到的有限级数全同态加密的噪音观念很是相似！简直，全同态加密体系的实现，和我们这里提到的把一个bit映射到环上而且叠加噪音的场景很是相似。一旦叠加的噪音高出了临界值（q/4），我们就无法判定这个bit到底本来是1照旧0了，我们也就无法还原这段密文了。详细的内容留个悬念，我们下期继承接头～
Regev加密是一个叫Regev的大佬在2005年发现出来的，是一个很是雷同于ElGamal范例的公钥加密系统，基于了DLWE的假设。我们来看看它的详细界说吧：
为了越发利便的举例子，我们这里先容一个最简朴的格系统——整数格（Integer Lattice）。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
