同态加密Homomorphic Encryption介绍

阅读此文之前，请先阅读密钥分享Secret Sharing介绍，并一直向上追溯直至到达根节点或已访问节点。

好久好久木有更新啦~由于前端时间忙于毕业和工作事宜，以致写作近乎荒废，说来惭愧。这篇文章主要介绍同态加密（Homomorphic Encryption）相关概念及其实现方法。

相信经过前面几篇文章的介绍，大家已经对安全计算这个概念有比较清晰的了解了。其实严格来说，同态加密并非狭义的安全计算（MPC）的范畴，而是自成一体系。只是同态加密所实现目标与安全计算有诸多类似之处，因此广义上安全计算也可将其囊括在内。

相较于混淆电路和秘密分享，同态加密的思路其实更为直观：直接将原文加密，然后在密文上进行各种运算，最终得到结果的密文，形式化的表示为：

x_1, x_2, \dots, x_n \rightarrow [x_1], [x_2], \dots, [x_n]

f([x_1], [x_2], \dots, [x_n]) \rightarrow [f(x_1, x_2, \dots, x_n)]

这说明借助同态加密，直接在密文上操作和在明文上操作然后加密，效果是一样一样的！一个典型的应用场景是：数据持有者想对其持有的大量数据进行计算，奈何其拥有的计算资源不足，想借助云服务器的算力完成该计算。如果按照现在流行的做法，那当然是将数据传输到云服务器，然后运行事先写好的程序进行计算。但如此一来，敏感数据便在云服务器上暴露无遗。同态加密正好解决了此问题，数据持有者传输数据前先将数据加密，云服务器在接收到数据后照例计算，只不过这次是在密文上进行的，云服务器啥都看不到。待得到结果后再将结果的密文返还给数据持有者，数据持有者解开后即得最终结果。这也恰好呼应了我在此前一篇文章中提到的食神闭眼炒菜的比喻。

经过上面的介绍，大家是否发现同态加密的思路十分简单直接？那么这是否意味着同态加密技术已被学术界玩烂了呢？然而事实并非如此。真正可用的全同态加密要等到2009年才被当时的斯坦福博士Gentry提出，比可实用的支持通用算的混淆电路和秘密分享出现的都晚，甚至比差分隐私（2006年）都晚。当然这两年同态加密发展迅猛，这又是后话了。那么是不是学术界忘了同态加密这件事呢？其实也不是。很多众所周知的公钥加密方案其实都具有同态的性质，只是它们都只支持部分同态，也就是说它们只支持在密文上进行加法或乘法操作，但不能既做加法又做乘法。比如著名的RSA加密方案，支持的就是同态乘法：

[x]?x^e

[x]?[y]=(xy)^e

还有1999年出现的著名的Paillier加密方案支持的就是加法同态：

[x]?g^x r^n

[x]?[y]=g^{x+y }(r_x r_y )^n

但很明显我们没法对两个用RSA加密出来的密文进行操作使得其中的明文加起来，我们也没法使Paillier加密出来的密文中的原文乘起来。那是不是意味着部分同态加密就没用了呢？当然不是。现实场景并不都是需要进行复杂计算的，很多时候只需要求个和或算个均值。诸如做简单统计，或者机器学习中对多方得到的梯度进行加和等。

当然人们并不满足于这些只适用于简单场景的部分同态加密。所谓穷则思变，既然广为使用的加密方案并不支持全同态加密，那人们就构造出新的加密方案来，没有方案创造方案也要上。前面提到过 ，全同态加密说难也不难，其实就是需要某种加密方案既支持加法同态也支持乘法同态。然而就这样一个听起来并不复杂的要求，折腾了科学家们小半个世纪。不过凡事都不是能一蹴而就的，如果不能同时支持任意多的加法和乘法，那支持有限个加法和乘法行不行？Dan Boneh等于2005年基于双线性对构造出了一种同时具备乘法同态和加法同态。不过由于双线性对性质的原因，乘法只能做一次。但无论如何，这已经算是巨大的进步了。

直到2009年Gentry提出了基于bootstrapping的方案，全同态加密才有了实现的可能。其实全同态加密的方案的基础方案并不复杂。全同态加密无非是想既能在密文上做加法又能做乘法。在密码学中，一般是以位（bit）为单位进行讨论的，安全计算和同态加密亦是如此。数值操作中的加法和乘法分别对应位操作中的异或（XOR）和与（AND）操作。要掩盖一个位，最简单的方式就是加上一个随机数。

让我们先看一种最简单的方式：对于一个位 b ，我们将其加密为密文 c=b+2x+kp ，其中 p 为奇数且可视为加密 b 用的秘钥， x 为随机数且可视为掩盖 b 的噪音。我们可以看到，由于 2x 为偶数，而 p 又为奇数，所以只要 k 是随机的，则无论 b 是0是1， c 的奇偶性都随机的,那也就意味着 c 并不透露 b 的原始值。要使用秘钥 p 将密文 c 解密，只需要先计算 c\mod p 便可得到 b+2x \mod p ，而由于 2x 为偶数，按照我们通常的理解， 2x 不影响 b+2x \mod p 的奇偶性，所以我们无需知道 x 的值便可得知 b 是0还是1。以上分析很简单，但其实这种加密方式存在一个隐患： 2x 真的不影响 b+2x \mod p 的奇偶性吗？其实不是的。当 x 足够大的时候，其实是会导致 b+2x \mod p 的奇偶性翻转的。举个简单的例子，当 p=9 的时候， c \mod p 的范围是 [-4, 4] ，比如 3 \mod p = 3 ，而 6 \mod p = -3 。也就是说，如果 x 大到 b+2x 超过了 p/2 ，那么 2x 就会使得 b+2x \mod p 的奇偶性翻转，从而导致了解密结果不正确。因此现实使用中，无论我们是想将这种加密方法用于加密还是密文计算还是别的什么用途，我们都希望 x 的取值范围不太大，从而保证解密结果的正确性。但 x 也并非越小越好，过小的 x 会导致安全性降低。因此 x 的取值范围是需要仔细选取的服务器内容加密，具体此处就不展开了。这种根据一个或一组被噪音扰动的多项式回推原始数据的的问题叫做learning with errors问题（当然这里仅仅是粗略地举例，具体定义请自行搜索）。

现在让我们回到同态加密这里，前面的加密方法是如何做到同态的呢？现在我们假设有两个位 b_1 和 b_2 ，我们按照上面的方法将它们加密为 c_1=b_1+2x_1+k_1 p 和 c_2=b_2+2x_2+k_2 p 。那我们先来看看加法的同态性：

c_1+c_2=(b_1+b_2)+2(x_1+x_2 )+(k_1+k_2 )p=(b_1⊕b_2)+2x+kp

再来看看乘法的同态性：

c_1×c_2=(b_1×b_2)+2(b_1 x_2+b_2 x_1+2x_1 x_2 )+kp=(b_1×b_2)+2x+kp

是的，这种简单的加密方法似乎可以支持加法同态和乘法同态，但噪音 x 却会不停地增长。根据前面讨论的，加法还好，噪音是线性增长的，但乘法的噪音却会爆炸式增长。这也就意味着，随着计算的进行，噪音（error）会越来越大，待噪音增长到一定程度，就会使得算得的密文无法被解密，也就无法达到通用全同态的目的了。像这样只能进行一定次数的加乘操作的同态加密方法，我们唤其为somewhat homomorphic encryption（关于这个名词的中文，其实我还没有看到满意的翻译）。

Gentry针对上述问题想了个办法，叫做Bootstrapping。该方法顾名思义，就是引导或启动另一轮加密。前面不是有多算几轮就会噪音爆炸的问题吗？那就算几轮就更新一次密文，使得密文中的噪音降为0，然后继续用来计算，如此循环往复。那么最简单的去噪音的方法是什么？当然是先把密文解密为明文再重新加密，这样得到的新密文，噪音含量自然就低了。但直接解密违背了密文计算的初衷，因此不可取。Gentry的神来之笔在于想到了让解密过程本身也在密文情况下进行，也就是说，把解密过程当成是一种密文状态下的计算，输入是密文的密文以及秘钥的密文。这句话看上去有点绕，可能我们借助形式化的符号会更清晰一些：假设一个明文 b 被秘钥对 (pk_1,sk_1) 的公钥 pk_1 加密为 [b]_1 （那么我们其实可以用 sk_1 将 [b]_1 解密为 b ），此时 [b]_1 是新鲜出炉的，噪音含量极低。但 [b]_1 经过若干次计算后变为了 [b]_1' ，如果此时 [b]_1' 包含的噪音已经多到不能忍了，就需要启用Bootstrapping过程。我们首先生成一对秘钥对 (pk_2,sk_2) ，并使用 pk_2 分别加密 sk_1 和 [b]_1' 得到 [sk_1]_2 和 [[b]_1']_2 ，然后使用同态计算将解密电路 Dec 作用于 [sk_1]_2 和 [[b]_1']_2 ，得到 [Dec(sk_1,[b]_1')]_2 ，即 [b]_2 ，这样就在未解密出明文的情况下又得到了新鲜出炉的密文了。

当然这一切的前提是 Dec 被顺利执行了。但通常情况下 Dec 也不是一个省油的灯，有可能Dec还没执行完噪音量就爆了。所以我们在选取全同态加密方法、参数和时机时，都要以一次能顺利执行 Dec 电路为前提。 Dec 电路越复杂，为了能给 Dec 腾出足够的空间Bootstrapping之前能做的计算就越少，反之亦然。为了减少Bootstrapping时 Dec 的复杂度，可以考虑在加密时先把解密需要的操作能做多少是多少，毕竟不是所有的操作都必须等到Bootstrapping时才能做的。这就好像机器学习中的数据预处理过程有时候是可以在客户端发送数据前完成部分计算的，并不是所有的计算都必须等到计算服务器搜集齐了数据才能开始。这种思路就是Gentry方案的另一要点，Gentry唤其为Squashing。

上面提到了一种简单的可对一个位进行简单同态的加密方式，也介绍了实现全同态加密的基本思路。但实际上人们研究和使用的同态加密方式不会像前面那个方法那样简单。关于全同态加密的具体实现方法，由于牵涉到很多近代数学的知识，这里不想过多展开，这里只介绍一些相关的概念。Gentry在其2009年的论文中提到的方法是基于理想格的（ideal lattice）。理想（ideal）可视为环（ring）中的一个计算黑洞，一个理想是某个环的子集，且理想中的数据和环中数据相乘一定还留在理想中。格（lattice）是一组基底的系数为整数的线性组合得到的所有向量的集合，反映在二维就类似于蜘蛛网，反映在三维就类似于魔方。基于理想格的加解密方法纯由线性变换组成，因此很适合bootstrap。Gentry的方案就是使用理想格并基于learning with errors问题对数据进行加密的。但Gentry的原始方案也不是尽善尽美，虽然此方案向世人展示了全同态加密的可行性，但其计算效率说实话确实不够高，原因之一是Bootstrapping和Squashing计算量极大，原因之二是随着计算的进行，密文大小会不断膨胀，这会导致计算越来越慢。后来人们退而求其次，找到了一种基于环（ring）的somewhat homomorphic encryption方案，该方案将数字表示为多项式，所有操作都是多项式的加和乘。虽然这种方案只能进行一定次数的加法和乘法，但由于整系数多项式操作可比理想格中矩阵操作快多了，而且避开了Bootstrapping和Squashing过程，所以整体速度还能接受。现在同态加密是密码学研究的热门问题，近年来有不少有趣的结果，大家有兴趣可以多看论文。

（编辑：源码网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!