密码学101：全同态加密

这是关于加密技术的一系列文章中的一部分。如果这是你看到的第一篇文章，我强烈建议你从本系列的开头开始阅读。

我们到了。旅程的最后。

在这一路上，我们学习了很多。最初的简单内容介绍变成了一系列完整的文章，我们探讨了许多加密领域的基础概念，以及一些非常接近先进水平的技术。我对此结果感到非常高兴。

然而，还有一个重要的话题我们至今未涉及。它可算得上是加密技术的一个圣杯。而现在，我们已经具备了理解现代技术如何解决这个问题的所有工具。

没错。是时候深入探讨_全同态加密_了。

继续吧，我忠诚的坐骑！

引言

同态 是一个我们应该已经熟悉的术语，因为我们专门撰写了一篇完整的文章来解释它的含义。不过，简短的复习总是有益的。

同态是一种函数，它具有一个简单的特性：

请注意操作不必是相同的这一微妙区别。

用简单的语言说：先将输入相加然后再应用函数的结果与先应用函数再相加的结果是相同的。

确实，我们说这个函数是相对于某个操作是同态的，在上述场景中，这个操作恰好是加法。

一些同态也可以是可逆的，这意味着，对于某个功能值 y = f(x)，存在某个逆函数使得：

在这种情况下，这个函数称为同构。

某些加密函数的行为类似于同构。能够_还原_加密是功能的要求，但其作为同态的表现则解锁了一些新的超能力。

具体来说，你可以对加密值进行加法，并确保在解密时，得到的结果与先对未加密值进行加法的结果相同。这非常酷——它允许应用程序对加密数据执行操作，从而保持隐私。

不过有个前提：在操作群体时，我们只能支持一种操作。

因此，我们可以创建基于群体的加密方法，这些方法可以相当轻松地处理加密值的加法（即ElGamal）。但是你想要乘法？不行。没法做到。

支持乘法是重要的——正如我们在简短的算术电路讨论中看到的，我们可以通过加法和乘法门计算几乎任何东西。这意味着，如果我们能够支持这两种操作，那么我们可以在加密数据上执行任意计算，同时保持数据隐私！

支持单一操作的算法家族被称为部分同态加密，或称PHE。

重要的是，这可能对某些类型的应用足够。例如，如果我们只需要保持加密余额并进行加法或减法，则我们不需要完整的FHE能力。

事实证明，支持加法和乘法的方法并不容易构思。很长一段时间，这对研究人员来说仍然是个难题。像Boneh-Goh-Nissim算法这样的努力基于配对，能够处理单一乘法。

这根本不够。支持两个操作仍然是遥不可及的。

但等等…… 两个操作？我们知道一个更好的结构！

通过环(Rings)进行加密

环听起来就像_全同态加密_应自然支持的代数结构。像NTRU这样的努力最初被提出，但只能处理_有限数量_的乘法。这是有充分理由的。

在上一篇文章中，我们研究了Kyber，它可以用来加密短消息。当我们查看解包步骤（想想解密），我们观察到恢复的消息并_不完全_是原始消息。

但它距离原始消息接近。只相差一个小误差。只要保持这个误差小，解密就会成为可能。

这就是一般所称的适度同态加密（SWHE）的思想：这意味着，当误差保持较小的时候，方法可以处理解密。

尽管Kyber不是一种同态加密方法，但思想大致相同。

乘法有让_误差膨胀_的趋势，这就是环基方法无法支持无限量乘法的原因。至少直到出现了一些更为显著的事件……

在_2009_年，Craig Gentry发表了他的博士论文，介绍了一些新的技术，从而解锁了第一次真正的_FHE_方案。

正如他的原始工作所示，研究从一个初步构造开始，在此之上应用了某些技术，将他的基本SHE方案转变为FHE。我认为在这里最好的方法是遵循相同的步骤！

基础构造

一切始于对适当的环的选择。我们将处理形式为𝔽 [X]/(f(X))_的环。同时我们也需要上述环的 理想(ideal)——请记住，理想(ideal)是 R 的一个子集，它在加法和乘法下是封闭的：

理想是_随机生成_的。我们抽取一个系数小的随机多项式 g(X) ——然后，理想就是 (g(X)) ，就像我们在这里中解释的那样。

接下来，我们需要再次讨论_基_的概念。我们在几篇文章前简要提到过这个概念。简单地说，基由一组_独立向量_组成，通过_线性组合_可以生成格点中的任何点。我们说一个基_生成_了一个格子Λ。

格子的基不是唯一的，我们可以选择多种有效的基。正如我们在上一篇文章中提到的，有_好基_和坏基——好的基允许我们快速解决最短向量问题，而坏基，即使生成同一个格子，也不适合有效地解决它。

一个好基（绿色）与一个稍微差的基（橙色）。

从图中，我们可以想象，一个好基应该是一组短的、非共线（如果可能的话是正交）的向量。另一方面，坏基则恰恰相反：长的、共线的向量。

因此，在我们即将关注的构造中生成了两个基——它们作为加密过程中的_秘密_和私钥：

秘密钥是一组“好”的基，而公开钥则是一组“坏”的基。

应该注意的是，这里我们提及的是理想J，而不是I。这不是错字——这背后是有充分理由的。我们慢慢来处理这个问题。

实际上，所有发生的事情就是，坏基仅适合计算加密值，但在解密时效率低下——而好基则在解密期间允许快速计算。对于我们来说，这里的细节已经足够——还有其他更迫切的概念等待我们理解！

加密

与往常一样，加密始于一个消息。我们常常避免明确定义的一个重点是有...