一、背景

在前面的技术分享”全密态数据库保序加密技术分析”一文中，我们提到了使用全同态技术的难处。对于非密码学的开发者来说，同态加密算法是一个比较陌生的词汇，本次我们就来介绍一下同态加密算法的基本概念。

贝格迈思在研发高性能智能数据库AiSQL中，充分运用了全密态数据库的保序加密技术，已实现数据可查询加密，并不断迭代结合同态加密技术，将数据在存储、计算和传输过程中保持加密状态，为数据提供了强大的保护措施，实现了金融级的数据库安全能力。

由于同态加密算法经常与隐私计算联系起来，本次我们将从隐私计算中一个比较常用的技术PSI(Private Set Intersection)说起，串联起密码学及同态加密的常用知识点，希望能让大家对同态加密算法有一个初步的认识。

二、什么是PSI

PSI 即 Private Set Intersection，中文一般叫做隐私求交。其意思是持有数据集合的两方，能够通过计算得到双方集合的交集，但不暴露交集以外的任何信息。

上图中Alice持有数据集A，Bob持有数据集B。如果Alice想知道Bob的数据集和自己的数据集的交集，传统的方式是Alice将自己的数据集A发送给Bob，然后Bob遍历数据集A，对数据集A中的每个元素，都在自己的数据集B中进行搜索，如果存在则放入交集集合Intersection中；等遍历完数据集A后，Intersection中就存放好了Alice想要的结果，最后Bob将Intersection发送给Alice，就完成了集合A和集合B求交的目的。但是这种传统的方式，只能叫做SI，即Set Intersection；因为在这个过程中，Bob知道了Alice集合中的所有元素，但对Alice而言，自己的数据相当于泄露给了Bob。

而在PSI中，Alice对Bob发起查询请求后，最后只有Alice知道了集合A和集合B之间的交集，Bob对Alice的集合A毫不知情。如果Alice不想将交集的结果共享给Bob，则Bob在这个计算中得不到任何信息；当然Alice也不能知道Bob的集合B的任何信息。在这个过程中，Alice又叫做查询方，Bob又称作数据的提供商。一般来说，数据的提供方提供了PSI的这项服务，可以向查询方进行收费。

三、加密算法简介

PSI能够在参与双方数据集可用不可见的情况下，得到双方数据集的交集，其手段就是加密。加密从其模式上可以分为对称加密和非对称加密。

对称加密又称私钥加密，即使用同一个密钥(私钥)进行加密和解密；AES就是一种常见且著名的对称加密算法；国密算法SM4也是一种对称加密算法。

非对称加密又称公钥加密，即在加密的过程中使用公钥，在解密的过程中使用私钥。这样任何持有公钥的参与方都可以加密数据，但是只有持有私钥的参与方才能解密数据；RSA， 国密算法SM2都是非对称加密算法。

从效率上来讲，对称加密比非对称加密高。但非对称加密因为其更高的安全性，被广泛用于网络通信中，比如HTTPS的认证环节。

这里还需要澄清一点，像一些安全散列算法，比如MD5、SHA1、SHA2、HMAC等，不能算作是加密算法，因为这些算法是不可逆的，它们一般被用在数字签名中。

同态加密算法也属于非对称加密。与非同态加密算法不同的是，经过同态加密算法得到的密文，能够进行有限的算数运算(如加法、乘法)。比如，现在我们要计算 1 + 2的结果，先对1加密变成enc(1)，再对2加密变成enc(2)，接着在密文状态下计算enc(1) + enc(2)，(注意，此处非同态加密算法无法进行这个加法运算)，得到了结果enc(result)；这个结果也是密文，最后对enc(result) 进行解密，会得到明文状态的3。这个结果就跟明文状态下计算1 + 2得到的结果一样，这就是这种加密算法为何被叫做同态加密算法的原因。

这个例子演示了加法同态。既然有加法同态，那么是不是还有乘法同态呢？这就得看同态加密算法支持的程度了。因为有的同态算法只支持密文间的加法，不支持密文间的乘法；而有的同态算法既支持密文间的加法，也支持密文间的乘法。那么接下来我们看看同态算法有哪些分类。

四、同态算法的分类

根据对加法和乘法的支持程度，同态加密算法可以分为:

1. 半同态加密：只支持加法或乘法中的一种运算。

ElGamal加密方案是基于离散对数的公钥加密方案，在其实现上满足乘法同态，其加密运算满足随机性，因此是ISO同态加密国际标准中唯一指定的乘法同态加密算法。

在半同态加密算法中，Paillier算法由于效率较高，安全性证明完备等特点，在众多有同态加密需求的场景中得到了应用，比如PSI，联邦学习等。Paillier算法支持明文和密文之间的加法，明文和密文之间的乘法，密文和密文之间的加法，但不支持密文和密文之间的乘法。因此Paillier算法属于加法同态加密算法，同时也是ISO同态加密国际标准中唯一指定的加法同态加密算法。

另外值得一提的是, 经典的非对称加密算法RSA，在不对明文进行填充的情况下，满足乘法同态特性。但此时的RSA由于在加密过程中没有使用随机因子，因此使用相同密钥加密相同数据会得到相同的结果，所以使用RSA作为乘法同态会存在严重的安全弱点。RSA并非为了同态而设计的，所以在需要使用同态的应用中，不会考虑将RSA作为同态算法。RSA只是恰好满足了乘法同态而已。

2. 部分同态加密：可同时支持加法和乘法的运算，但支持的计算次数有限。

部分同态加密算法中，比较有代表性的是BGN算法；这种算法同时支持加法同态和一次乘法同态运算。

3. 全同态加密：支持任意次的加法和乘法运算。

全同态算法中，比较著名的算法要属BFV，BGV，CKKS。这些算法从理论上支持任意次的加法和乘法运算，但在工程实现上，只支持有限次的乘法运算。目前只有Concrete的全同态库实现了真正意义上的全同态，但是只支持单比特的加密，因此效率极低。

五、同态算法的优缺点

1. 同态算法的优点：

由于能够在密文上进行运算，使得数据可用而不可见成为可能，因而同态加密算法有着广阔的应用场景。

试想，在拥有海量数据的大厂之间应用联邦学习，由同态加密算法保证各自数据的安全性，使得各方都获得了自己想要的模型，这样数据孤岛问题将得以解决。但对同态算法的应用也带来了很多挑战。

2. 同态算法的主要缺点：

(1) 密文膨胀

存储一个密文所需的空间比单独存储一个明文要大的多。以Paillier算法为例，对于一个32bits的整形数进行加密，如果密钥长度设为2048bits，加密的过程首先要进行encode，32bits的整形数变成了用2048bits表示的明文；接下来进行加密， 2048bits的明文变成了4096bits的密文。可以看到，密文相对明文的膨胀系数达到了 4096 / 32 = 128 倍。

(1) 只支持有限的算数运算

同态加密后的密文，即使是全同态加密算法，也只能支持加法、乘法，无法支持比较操作。如果需要比较两个密文，则需要先做差，再解密，最后进行正负性判定。这使得难以在密文上进行排序。

(2) 计算速度慢

无论是全同态加密算法，还是半同态加密算法，在计算速度上都比明文要慢上N个数量级。以全同态加密算法来说，在通用芯片上，密文计算相对明文计算要慢10万倍；因此硬件加速非常有必要在同态计算中引入。常用的算力加速设备为GPU与FPGA，FPGA由于其可重构性、高性能、低功耗得到了算力加速厂商的青睐，这也间接带动了芯片产业的发展。可见挑战中也容易出现机会和新的赛道。

(3) 学习曲线高

软件开发人员和资深的密码研究者，使用有着同样实现的全同态加密算法，大概率会在安全性和计算性能方面有着截然不同的表现。以全同态算法BFV中三个参数配置来进行说明。

plain_modulus、poly_modulus_degree和coeff_modulus需要在使用前由用户配置。

1) plain_modulus

plain_modulus指明文模数，它的设置与poly_modulus_degress有关(plain_modulus要求是一个质数，且与 1 关于模 2 * poly_modulus_degree同余)，同时它的大小决定了每次进行密文运算所消耗的noise budget的大小，plain_modulus越大，每次计算所消耗的noise budget就越大。这里需要说明的是，noise budget直接决定了一个密文能否被成功解密。每进行一次乘法运算，noise budget会被消耗，连续进行多次乘法，noise budget会被不断消耗，如果一个密文在多次乘法运算后noise budget被消耗完后，这个密文就无法被解密了。是的，即使我们持有正确的私钥，也无法对其进行解密。因此我们希望这个plain_modulus越小越好。

2) poly_modulus_degree

poly_modulus_degree指明文多项式阶数，是2的整数次幂。它决定了在encode的时候，有多少明文可以被encode到多项式的系数上。后续在密文状态时，可以进行batch操作，这样一次计算可以被应用到多个数据上。这个数值越大，越安全。

3) coeff_modulus

coeff_modulus 是一组素数，决定了密文的初始noise budget的大小。coeff_modulus越大，密文的初始noise budget越大，后续进行的乘法和加法运算的次数就越多。但coeff_modulus同时还跟密码安全性有关，越大越不安全。因此从计算能力上讲，我们期望coeff_modulus越大越好；但另一方面，从安全性的角度来讲，又希望coeff_modulus越小越好。这就有个折衷。通常如果coeff_modulus增大，需要增大poly_modulus_degree以满足安全性的要求，增大后的poly_modulus_degree又对计算性能有影响。此外plain_modulus因为与poly_modulus_degree相关，因此也需要跟着调整。另外coeff_modulus是一组素数，那么究竟设置多少个合适呢? 可以看到，仅仅三个参数的设置，就已经让我们需要思忖良久，要知道，启动BFV还有很多其他参数需要考虑。

六、同态算法在PSI中的应用

接下来，让我们再看看在PSI中是如何应用同态算法的。基于不同的同态加密算法会有不同的PSI实现，这里我们看看全同态加密算法在PSI中的实现。以下是一个最简单朴素的实现方法: 多项式做差再求积。

Alice中的集合A，其元素记为(a1， a2， a3， ... ， an)；Bob中的集合B，其元素记为(b1， b2， b3， ... ， bn)。Alice将集合A中的元素加密之后发送给Bob，比如将a1加密之后的结果enc(a1)发送给Bob，Bob用他所有的元素，计算(b1 – enc(a1)) * (b2 – enc(a1)) * (b3 – enc(a1)) * ... * (bn – enc(a1))，然后将得到的结果enc(result)发送给Alice； Alice用她的私钥对enc(result)进行解密，如果是0，就说明a1在B中，如果不为0，就说明a1不在B中。

注意上述过程，Bob进行计算的每一个乘积项(bi – enc(a1))，其中bi是明文。由于是在Bob侧计算的，所以Alice并不知道bi的值是多少； enc(a1)是加密状态的，且私钥在Alice侧， 所以Bob也不知道Alice发送的a1值是多少。最后Bob计算得到了一个结果enc(result)， 由于只有Alice能够解密这个结果，因此Bob此刻并不知道a1是否在B的集合中(除非Alice愿意与Bob分享得到的结果)；Bob将enc(result)的结果发送给Alice后，Alice解密得知a1是否在Bob的集合B中。

当然这只是PSI的一种理论的实现，在工程实际中，会在这个基础上进行很多改良，主要是从安全性、计算速度及传输量上考虑的。

在这个例子中，如果使用半同态加密算法，因为半同态无法计算密文乘法，而这个例子中的每个乘积项都是密文(明文和密文之间进行运算得到的结果会是一个密文)，因此无法进行运算。对于使用半同态的PSI，会有其他实现方式。

七、小结

本文通过隐私计算中的一个常用技术PSI的实现说起，介绍了密码学的相关知识及同态加密算法的现状及使用场景。

同态加密保护了计算过程的安全性，使数据可用不可见成为可能。但同态加密算法不支持大小比较，仅支持有限的算数运算，且运算效率低，使得在数据库中对其进行应用非常困难。

贝格迈思是国际领先的数据智能技术引领者，

数据科技驱动行业应用创新者，研发的高性能智能数据库AiSQL，支持数据可查询加密，在数据处理全过程中对数据进行全密态保护。与传统的加密方式相比，数据可查询加密提供了更高的安全性和隐私性，同时保留了数据的可用性。

贝格迈思将不断探索，持续提升数据库中加密算法的创新应用，欢迎大家的关注与交流！

参考文献：

1. T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)

2. P. Paillier, Public key cryptosystems based on composite degree residuosity classes, Proceedings of Advances in Cryptology, EUROCRYPT’99, 1999, pp. 223–238

3. Damgard I, Geisler M, Kroigard M. Homomorphic encryption and secure comparison[J]. International Journal of Applied Cryptography, 2008, 1(1): 22-31.

4. Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with compressed queries and amortized query processing. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 962--979.

Changyu Dong, Liqun Chen, and Zikai Wen. 2013. When private set intersection meets big data: an efficient and scalable protocol. In ACM CCS 2013, Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung (Eds.). ACM Press, 789--800.