最近我在斯坦福大学修了CS355(密码学专题)。这是一门关于高级密码主题的综合课程。
在为期3个月的课程中，讲师们涵盖了密码学历史上的各种主题，从单向函数、PRF一直到MPC、Zero-Knowledge和PIR等应用密码系统。这真的是一门很棒的课程，我肯定学到了很多关于现代密码系统的知识。
为了加强我对这些主题的理解，我决定开始发表一系列博客文章(温和地)介绍这些很酷的密码主题。我将总结课堂笔记，并把它们解释成我自己的话。希望它也能成为一本有趣的(而不是晦涩难懂的)读物，帮助您理解这些主题。
对于第一系列的帖子，我想谈谈完全同态加密(FHE)，这是安全行业中一个相当热门的话题。
请注意，我将尝试使我的解释尽可能简单，但是在继续…之前，仍然要确保您有一些安全/加密上下文。
我将以FHE(完全同态加密)的简要介绍开始这篇文章。
一种加密形式，允许对密文进行计算，生成加密结果，当解密时，该加密结果与操作结果相匹配，就好像它们是在明文上执行的一样。
定义是完全正确的-同态加密只是一种加密方案，在这种方案中，人们可以组合加密的密文，并在不知道实际加密密钥的情况下以加密的形式获得对原始明文的感兴趣的计算。
如果您熟悉密码/安全材料，您可能知道一些常见的加密方案，如AES和RSA。尽管对称加密方案和非对称加密方案之间存在差异，但是每个方案都可以概括为以下形式。
GRAPH LR；G((KeyGen))-.-PK(EncKey)G-.-SK(DecKey)PK-->；加密SK-->；解密明文-->；加密-->；密文-->；解密解密-->；Pt2[明文]。
有一种\(KeyGen\)算法可生成用于加密和解密的密钥。请注意，在对称方案中，两个密钥是相同的，而在非对称方案中，密钥是不同的。(一个称为公钥，另一个称为私钥)。
\(加密\)算法使用加密密钥对给定明文进行加密。然后，它产生密文，即加密的明文。
\(解密\)算法使用解密密钥反转对密文进行的加密。它将密文还原为原始明文。
这就是了。我们使用哪种算法(AES或RSA或其他算法)并不重要，总体结构总是相同的。
在密码学中，我们倾向于在介绍系统之后总是写它的属性。因此，为了完整起见，我也应该谈一谈。
首先，加密需要具有正确性。这意味着，使用从\(KeyGen\)派生的密钥对作为对某些明文\(pt\)应用加密的结果的密文进行解密将始终保证产生与以前相同的明文\(pt\)。为了用概率语言捕捉这种关系，我们使用以下表达式：
\[\forall pt\in pt，(k_{enc}，k_{dec})\leftarrow KeyGen(1^\lambda)：\\pr[deccryption(k_{dec}，cryption(k_{enc}，pt))=pt]=1\]这意味着使用适当密钥对加密密文应用解密的概率将始终与以前完全相同。
我们需要的第二个属性是语义安全。我不打算在这里做完整的证明，但基本思想是，给定两个对应于\(pt_0，pt_1\)加密的加密密文\(ct_0，ct_1\)，人们无法区分哪个密文是\(ct_0\)的加密。这基本上意味着加密的密文看起来是随机的，不会向其原始明文提供任何提示，因此确保该方案是安全的，不会被窃听。
如果加密的密文在任何观众看来都像是随机垃圾，这是否意味着除非有相应的解密密钥，否则密文是完全无用的吗？
有些加密方案实际上表现出一种惊人的性质，如果您获得了数字1和数字2的加密，虽然您不知道原始明文是什么，但您可以简单地将这两个密文相加，得到\(1+2=3\)的加密密文。
这一性质称为同态，其中明文上的代数关系也在密文中保留。因此，表现出该特性的加密方案被称为同态加密。
我们上面给出的例子只是同态加密的一个实例。也就是说，这是加性同态加密的一个实例，其中可以自由地将密文加在一起，并以加密形式获得原始明文的任何线性组合。当然，还有与AHE对应的乘法同态加密。在MHE方案中，人们可以自由地将密文相乘，并获得原始明文的任何乘积。
很有趣，对吧？不过，如果大家觉得这个概念仍有些含糊，请容许我举一个例子。
我们都知道投票是如何运作的--例如，当一群人想要对某件事进行投票时(比如他们是否想要点日式午餐)，他们可以开始投票。
在投票过程中，每个人都会向主机提交去(1)或不去(0)的选择。然后，主机简单地将每个人的份额加在一起，并比较最终结果是否大于人口的\(1/2\)。
然而，该方案的问题在于轮询过程不是匿名的。这意味着，任何能看到数据流量的人都会知道谁喜欢谁不喜欢日本食物-只需查看每个人的分享。
在加性同态加密的帮助下，我们可以很容易地将该协议转换为匿名协议。
首先，主机将运行\(KeyGen\)算法，该算法生成一对加密密钥\(PK\)和解密密钥\(SK\)。(这里，我们使用的是非对称加密方案。)。然后，主机将加密密钥\(PK\)分发给公众。
现在投票开始了。每个参与者都将使用\(ENCRYPTION\)算法在加密密钥\(PK\)下加密他们的选择(1或0)。然后它们都会将它们的密文发送给主机。
\[ct_i=加密(pk，pt_i)：pt_i\in\{0，1\}]主机将所有加密密文相加，形成一个密文\(\hat{ct}\)。最后，主机对密文运行解密算法，并获得轮询结果。
\[解密(sk，\sum_i ct_i)=\sum_i pt_i\]这可能无法充分发挥HE的真正能力。但这应该是一个可靠的例子，它允许我们进行某种类型的安全委托计算-这意味着我们可以委托某个第三方通过使用HE方案加密我们的输入来计算我们拥有的秘密输入。然后，第三方将任何计算直接应用于密文，并获得结果密文，即计算结果的加密。最后，我们可以解密该密文并接收结果。
我们应该对他是什么以及它能让我们做什么样的应用感到很舒服。现在，我想简要介绍一下最终将引导我们实现完全同态加密的HE的不同级别(或阶段)。
这是他的第一个阶段。如果存在部分同态的加密方案，这意味着该方案或者是加法同态的，或者是乘法同态的。
换句话说，假设在委托计算示例中，我们希望远程服务器计算某些功能\(F\)。如果我们选择的HE方案只是部分同态的(例如，加法同态)，这意味着我们对密文唯一能做的就是获得明文的加密线性组合。
因此，如果我们有对应于\(pt_0，pt_1\)的输入\(ct_0，ct_1\)，该HE方案允许我们计算\(Enc(pk，c_0\CDOT pt_0+c_1\CDOT pt_1)\)，其中\(c_0，c_1\)是一些常数。然而，使用此方案不可能计算两个明文\(Enc(pk，pt_0\cdot_pt_1)\)或类似内容的乘积。
综上所述，如果HE方案只是加性同态的，则第三方可以计算的泛函\(F\)限于所有函数，其中它们的输出可以表示为所有输入的线性组合。
对于只有乘法同态的方案来说，这是完全相同的-那么功能性\(F\)将被限制到其输出可以表示为其输入的乘积的所有函数。
下一类让我们更接近我们的理想世界。如果我们说HE方案在某种程度上是同态的，这意味着HE方案可以对原始明文进行加法和乘法，但其能力是非常有限的。
一个典型的HE方案示例是，假设有一个有点同态的HE方案，在该方案中，您可以对密文执行无限的加法，但只能执行一级乘法。在这样的方案中，给定\(ct_0，…，ct_2\)，我们可以得到类似\(Enc(pk，c_0\CDOT pt_0\CDOT pt_1+pt_2)\)的结果，但不能进一步得到像\(Enc(pk，c_0\CDOT pt_0\CDOT pt_1\CDOT pt_2)\)这样的结果。
再次总结一下，在某种程度上同态的方案中，功能性\(F\)限于所有函数，其中它们的输出可以表示为明文和单轮乘积的线性组合。
现在我们离得更近了。如果在这一类中存在HE方案，那么我们可以自由地获得对明文的加法和乘法。我们如何将密文组合在一起不会有任何限制。
然而，这个类别之所以被称为“Leved”，是因为它为功能\(F\)引入了复杂度上限\(L\)。如果函数F可以用布尔回路C来表示，使得(MID C MID L)(电路的深度小于界限L)，那么它可以在分层的FHE方案中进行评估。
理解分层方案的一个好方法是考虑HE加法和乘法运算不可避免地在密文中引入一些“噪声”。噪声电平随着功能\(F\)的布尔电路的深入而增加。当F的复杂度接近L时，噪声最终爆发，破坏了密文的可观测状态，不能再从密文中恢复出原始明文。
最终，我们达到了我们的最终目标，也就是最后一个类别--FHE。在FHE方案中，我们可以通过对密文进行操作来对明文进行任意计算。对功能\(F\)没有复杂性要求。此外，FHE方案总是将密文噪声选通在一个可管理的门限上，这样它就不会炸毁它的可观测状态。
在此阶段，我们可以真正启用安全委托计算。如果我们能找到有效和实用的FHE方案，那么我们基本上可以安全地将所有计算卸载到远程服务器，而不会损害一丁点数据！
在我们转换话题之前，让我们先给出一个FHE方案的正式定义。正确的FHE方案的语法应该有四个基本算法：
\(KeyGen(1^\lambda)\right tarrow SK\)：这是生成密钥的密钥生成算法。(这可能会有所不同，具体取决于它是对称的还是不对称的。)。
\(enc(sk，\mu\in\{0，1\})\right tarrow ct\)：这是按位加密算法，将单个位加密成一些密文。
\(dec(sk，ct)\right tarrow\µ\)：这是从密文恢复位\(\µ\)的解密算法。
\(eval(F，ct_1，.，ct_l)\right tarrow\hat{ct}\)：这是将\(l\)密文组合在一起以获得原始\(l\)明文下的功能评估\(F\)的加密表示。这里，功能\(F\)由\(l\)输入上的布尔电路表示。
除了每个加密方案都需要具备的正确性和语义安全属性外，这里还需要一个属性：紧凑性。准确地说，该方案需要满足：
[\for all F，sk，ct_i\leftarrow Enc(sk，\mui)：\MID Eval(F，ct_1，.，ct_l)\MID=poly(\lambda)\]换句话说，来自评估算法的输出大小需要独立于功能的复杂性\(F\)。
为什么这个属性很重要？事实上，如果没有这个性质，我可以断言存在一个完全有效的FHE方案的超平凡构造。此构造的操作方式如下：
当我们要评估一组密文的功能性\(F\)时，\(Eval\)算法将简单地输出密文\(HAT{ct}=(F，ct_1，.，ct_i)\)。请注意，我们在这里没有限制输出大小，因此这个大小可以与输入加上功能描述\(F\)一样大。
最后，当我们要解密结果密文\(\hat{ct}\)时，解密算法\(dec\)只需读取功能\(F\)的描述，逐个解密后面的所有密文，然后对解密的明文应用\(F\)。
现在您应该明白了-如果我们不限制Eval算法的输出大小，那么这个方案基本上可以通过根本不做任何计算来“作弊”。它所需要做的就是不断地将功能\(F\)的描述附加到密文中，并让解密密文的人来做所有的工作。
在我们深入到理论领域之前，我想让我们一起回顾一下FHE的简史：)。
FHE的概念是在70年代末提出的。1978年，里维斯特、阿德尔曼和德图佐斯共同提出了一种方案，该方案通过只处理密文而不知道解密密钥来实现明文的秘密评估-基本上就是fhe！而且，这距离1976年提出Diffie-Hellman公钥交换只有两年的时间。
这个想法提出后，整个学术界和产业界都开始寻找具有这种神奇属性的理想人选。不幸的是，人们找不到一个既满足FHE要求又不被密码分析攻击破坏的有价值的方案。
直到2009年，克雷格·金特里(斯坦福大学的博士)在FHE上取得了重大突破。在他的博士论文中，他给出了第一个基于理想格假设的有效的FHE方案的构造。
在这篇论文中，他还介绍了这一新颖的自举思想。有了这个自举技巧，他就能把一个平坦的FHE方案变成一个完整的FHE方案。这个技巧的本质是使用一些“黑魔法”以某种方式“刷新”和改善噪声密文的噪声电平，以便在计算任意复杂的函数\(F\)时噪声永远不会爆炸。我们将在接下来的帖子中回到这一点。
金特里发现后，整个行业开始了第二轮大规模寻找理想人选的工作。
2011年，Vaikuntanathan的Brakerski提出了一个新的FHE方案--一个基于格密码假设的方案，称为有错学习(LWE)。后来，Brakerski，Gentry，Vaikuntanathan结束了这项工作，正式提出了BGV FHE方案。该方案是水平FHE方案，并且与Gentry 09‘相比基于更好的格子假设。通常，我们将BGV方案称为第二代FHE方案。
2013年晚些时候，绅士们再次发起反击！Gentry，Sahai，Waters共同提出了第三代FHE方案-GSW方案。GSW方案再次基于LWE格密码假设(但略有改进)，并使用自举使其本身成为真正的FHE方案(能够评估任意大小的功能\(F\))。
在2013年后，业界会有更多的跟进工作，以进一步改善宽免计划和政府资助计划，使其更切合实际。IBM参与了HElib项目，这是一个基于BGV方案的开源FHE库。另一个小组开发了TFHE项目，该项目源于GSW计划。这两个项目都得到了积极的维护和优化，以提高性能和实用性。
也有一些使用硬件加速FHE方案的尝试。像cuFHE这样的项目旨在使用基于CUDA的GPU加快评估速度。也有人尝试将其移植到FPGA和ASIC芯片上，以进一步提高其性能。
今天我们站在一条铺得很好的道路上，这条道路是由这一领域的先锋们修建的。今天的主要焦点仍然是性能。有了最先进的技术，我们在评估中等配置的机器上的有用功能时，仍然会考虑秒的单位。
在我们继续解释绅士的FHE方案是如何工作的之前，我认为回顾一下一些值得一提的建立FHE方案的尝试会很有趣。
如果您已经了解RSA，请随时跳过本简介部分！但如果不是，请允许我用几句话简要总结一下这个算法。
RSA的工作原理是对循环有限域(或群)中的消息求幂。它可以分为几个步骤：
首先，确定一个大数\(N=p\CDOT q\)，其中\(p，q\)是大素数。
然后，找出一对数字\(e，d\)，使\(e\cdotd=1\text{mod}\phi(N)\)。这里，\(\φ(\cdot)\)是欧拉函数，\(\φ(N)=(p-1)(q-1)\)。
将\((N，e)\)设置为公钥，将\((N，d)\)设置为私钥。
加密消息\(m\)时，只需计算\(Enc(pk，m)\right tarrow m^e\text{mod}N\)。
解密密文\(c\)时，只需计算\(dec(pk，c)\right tarrow c^d\text{mod}N\)。
((m^e)^d=m\text{mod}N\)保证了该方案的正确性。
由于RSA的加密只是简单的求幂，我们可以在这里立即看到一些HE属性。假设我们有消息\(m_0，m_1\)的加密，即\(c_0，c_1\)。我们很容易看到：
[\hat{c}=c_0\cot c_1=m_0^e\cot m_1^e=(m_0\cdot m_1)^e\]通过简单地将两个密文相乘，我们就得到了原始明文乘积的加密。事实上，我们可以断定RSA是乘性HE。
但是，我们在RSA中找不到附加的HE属性。因此，RSA算法是一种部分HE算法。
有几个著名的循环群，如整数有限域和椭圆曲线群。但是，我们不需要了解这些组实际上是如何实现的。
我们只需要知道有一个组\(\mathbb{G}\)，它包含一组元素。在该组内部有一个生成器\(g\in\mathbb{G}\)，它的幂运算产生\(\mathbb{G}\)的每个元素。如果这听起来仍然有点模糊，就试着认为每个元素\(h\in\mathbb{G}\)都可以表示为生成器的某个指数\(x\)：
[h=g^x\in\mathbb{G}\]ElGamal加密是一种在一般循环群上工作的加密方案。它的工作方式如下：
首先，采样一个小于\(\mathbb{G}\)大小的随机元素整数\(\alpha\)，并将其设置为私钥。我们将\(g^\alpha\in\mathbb{G}\)设置为公钥。
当我们想要加密一条消息\(m\)时，我们将首先采样一个随机整数\(\beta\)，然后我们将输出密文\(ct=(v=g^\beta，e=pk^\beta\CDOT g^m)\)。
稍后，当我们。
..