笔记分享 | 组队学习同态加密（1）——全同态加密基础知识
OpenMPC社区主办的组队学习同态加密第一期活动在近日圆满完成，荣幸邀请到电信翼支付密码算法工程师沈华杰老师为大家带来了主题为《FHE全同态加密基础知识》的精彩分享。本次分享长达一个半小时，干货满满，详细介绍了同态加密的基本概念原理和应用场景，并提供了一些常见的同态加密算法和性能指标。此外，沈华杰老师还比较了全同态加密不同加密方法的优缺点，并探讨了如何选择合适的参数以实现更高效、更安全的同态加密计算。
同态加密是什么？
同态加密是能让我们直接在一个加密的数据上进行各种的运算的技术。我们可以把它想象成一个手套箱，我有一把钥匙可以打开这个手套箱，我就可以把我想加工的一些零件，比如说一块黄金放进去，这个手套箱相当于是一个密文，里面装着我的黄金。
我将手套箱给到另外一个人，他可以用这个手套把手伸进去对我的黄金进行任意的操作，但是他没办法把黄金拿出来，因为钥匙在我手上。他只能对黄金进行加工，完成之后把整个箱子还给我，然后我拿钥匙去把这个箱子打开，取出黄金。相当于是做了一个外包计算，我将我的数据外包给了另一方，他在我的数据上进行任意计算之后，把处理完的数据返回给我。
形式化的定义，假设我们有一个明文m，我们可以用公钥或者私钥对它进行加密；然后在密文上进行任意操作，这里主要指的是加法和乘法操作，在密文上运算一个函数f，得到一个加密结果f(m)返回给加密的人。
典型的(全)同态加密算法
加密算法分为对称加密和非对称加密，在利用对称加密时，通信双方需要拥有
典型的同态加密算法，第一个是在 1978 年提出的RSA算法，以及 1999 年的Paillier算法，它们都是半同态加密算法，前者支持乘法操作，后者支持加法操作。BGV，BFV和CKKS都是既支持加法又支持乘法的同态加密算法，前两者是 12 年提出的CKKS是 17 年提出来的，我们把它们叫做层级同态加密算法。
至于全同态加密，也有人按照迭代分类。第一代是在2009年由Gentry博士提出的Bootstrapping概念代表，第二代则是支持快速的同态运算，第三代支持快速的Bootstrapping.
RSA算法相信熟悉密码学的朋友都有所了解，它是用一个指数形式来对明文进行加密，这个明文是在底数上。而Paillier算法与RSA不同的是它的明文在指数上表示。这两个算法是具有代表性的部分同态加密算法。
全同态加密就不再是一个幂次问题了，我们把它归类到容错学习（LWE，Learning With Error）问题。给定一个秘密的向量s，以及一个随机选取的向量a，还有一个符合某种分布的一个错误e，或者把它叫做噪声。将这一个随机选取的向量和秘密向量进行一个内积，再将我们的噪声加上，将这两项发送给另一方，另一方是无法通过a和b来计算得出s的。RLWE问题就是将LWE问题迁移到了环上，是一个整数的多项式，除掉一个分源多项式，在系数上模掉一个模数q。BGV，BFV和CKKS三种加密算法都是基于RLWE的加密方案，区别在于前两者的明文空间都在中，CKKS的明文空间是R，不受该限制。另外主要的区别就在于BGV，BFV是在一个有限域内的精确运算。然后CKKS是一个浮点数上或者说复数空间上的一个近似的运算，因为它会把最后的噪声也当作明文的一部分输出出来。
CKKS算法中，假设两边的明文是0.3和0.5，各放大10倍，通过指数运算的性质，得到8，不过引入了噪声，也就是最后的0.223/10，这是无法删除的。
乘法上，我们将两项的密文乘法运算后得到一个三项式。还是举明文为0.3和0.5的例子，我们已经可以得到相乘为15的结果，但是还是会引入无法消除的噪声。这里有三个问题：
这个三项的密文怎么继续运算？
密文的噪声增长已经影响了结果正确性了， 如何延缓噪声增长的速度？
有没有办法直接减少这个噪声？
先介绍几个重要术语。
为什么乘法之后密文是三项的？根据虚线框中的计算推导过程，密文可以把它拆分成，因为它是一个常数项;第二项密文要乘一个s，第三项要乘一个，所以密文是一个三项的密文。
如何将三项的密文变为两项？也就是重线性化问题。我们先生成一个重线性化密钥rlk，将三项式的后两项g、h和密钥结合，进行重线性化为(b,a)，并且考虑解密。重线性化是将(f, g, h)由(s, )解密的密文，变为了(b,a) 这个由s解密的密文。
但是这么做的后果就是噪声非常大，解密会出错。通常有三种方法：
使用分解基B分解，将噪声从|q|B降低为 扩模，将模数扩大，可以将噪声除以和B差不多大小的P，也会降低噪声 扩模和分解组合，在分解里面可以取大一点的B， 在扩模里面可以取小一点的P
参数选取时主要涉及到n和Q。一般来说，n越大，Q越小，安全性越高，Q和我们可以做的乘法层数相关，Q越大则层数越大，这是我们需要的，所以我们会放大Q，这会带来安全性的降低，因此我们需要同步增大n的值，将安全性同步提高到128bit。
在同态加密中，我们想要做的是向量之间的两两相乘。所以就面临一个问题——是怎么将向量之间的两两相乘映射到一个多项式上，然后多项式之间的相乘可以映射到向量之间两两相乘上。这里需要用到“打包技术（SIMD）”。
怎么构造打包？我们是通过一个点值的形式和多项式形式进行转换得到。比如
这是3个多项式，都可以用多项式曲线表示多个点，比如A(x)上的点(-2,1)，我们用A(x)上的点和B(x)上的点进行相乘，y轴上的值可以表示为相乘的结果映射到C(x)上。所以点乘可以和多项式相乘进行相互转换，也叫快速傅里叶转换。
在具体构造的时候，我们并不是用-2，-1这样的点，而是通过构造一个分元多项式：
它叫做2n分元多项式，满足的性质就是它的根都是一个单位圆上的虚数根，也叫单位根。等就是单位根。，实部是二分之根号2，虚部也是二分之根号2，这是一个实数轴和虚数轴的概念。同时1、3、5、7相互都可以表示对称关系，可以将编码过程抽象成二分问题，作一个快速傅里叶变换。这样我们可以将v=[a,b]打包如下：
将原始向量[v1,v2,v3]通过旋转一位或两位，可以得到密文向量。有啥用呢？我们将明文矩阵的一个对角线元素提取出来，A11、A22、 A33 和V1、V2、 V3 做两两之间的点乘。同样的，我们将A12、A23、A31跟V1V2V3就旋转后的一个密文做两两之间点乘。还有就是A13、A21、 A32和旋转两次的密文做两两之间的点乘，可以观察到这三个东西加起来乘积就是本来的一个矩阵和向量的乘积。
那是怎么构造的呢？我们将一个明文向量转换成一个明文多项式，用的就是我们之前说的打包技术。然后在明文多项式上运算一个同构映射得到密文。
同态加密算法应用场景
Paillier算法主要应用在联邦学习中，作为加密模型梯度的常见方法。整数上的LHE算法主要应用在隐私集合求交、隐私信息查询、安全多方计算中。而浮点数上的LHE算法一般用在一些机器学习的训练和推理上，处理一些浮点数的场景。
我们重点介绍一下隐私集合求交的过程。这里可能是一个客户（左边的接收方）她有一些数据集A=(1,2,3)，她想知道这些数据集哪些是在服务器（右边的发送方）的数据集里面。服务器有一个数据集B=(1,3,5,7,9)。客户想知道服务器有哪些是自己有的数据交集，哪些是在服务器独有，他们就做一个隐私集合求交最后得到的结果是(1,3)。隐私集合求交和普通的求交的区别就在于说接收方它是能得到最后的求交结果，但是不知道发送方集合究竟是什么。发送方他也是不知道接收方的集合是什么，然后我们可以让两方都得到结果，也可以只有一方得到结果。
隐私集合求交的应用场景相当丰富，有
反诈：黑灰名单
发现通讯录好友
联邦学习数据对齐
密码撞库检验
广告投放转化率统计
疫情风险地区行程检测
在上海的同学可能对之前疫情期间有一个叫天翼电子哨兵的东西有点耳熟，这款产品就是在追踪疫情数据的同时尽量的保证用户数据的隐私性。
华东某市多方安全计算实验室的多方安全数据分析平台基于隐私查询、安全求和、隐私集求交、联邦学习协同建模等可信数据分析能力，提供灰黑名单核查、一人多卡核查和公安精准阻诈、联邦学习反诈建模等功能。
那么怎么用同态加密做PSI呢？A这边有数据是（1,2,3），我们直接把（1,2,3）进行加密。B这边也有一些数据，它通过这些数据来构造一个多项式，然后对多项式做同态加密。接收方用自己的数据去验算这个多项式，可以得到（1,3）可以使多项式F(x)=0，所以交集就是(1,3）。
那这个方案要怎么优化呢？发送方可能有相当大的数据，如果构造一个超大多项式的话，因为所有的项都得包含在这个多项式内，计算量将相当大。这里我们用哈希函数，将数据之间用哈希映射对应，在非平衡场景下非常快。1000个数据和2亿个数据求交，只需要5秒，通信是12MB。
在机器学习的推理中，它有一个卷积层，一个bn层，一个激活层，一个池化层。卷积层和bn层都是一些矩阵向量层，类似于求平均，用同态加密的多项式方法非常好算。但是激活函数是没办法直接用一个多项式来算，所以说我们要通过一个拟合的方法处理。
现在同态加密的效率如何呢？乘法运算还是比较慢的，因为乘法相当于我们需要做多项式之间的相乘，然后相乘之后还要通过一个重线性化的步骤，但是同态的密文扩张相对来说没有很大。相比起MPC，同态加密的通信开销会小很多，但是目前的计算效率还是不如MPC。同态加密有一个优势在于它是一个非交互式协议，一份数据用同态加密上传给服务器，那对于用户来说，就不用再去跟服务器进行交互来取这份数据了。
同态加密在硬件加速上已经有比较大的一个提升了，在特定的硬件特定的算法下可能已经有了 4 个数量级的效率的提升。
以上就是沈华杰老师为大家带来了主题为《FHE全同态加密基础知识》的精彩分享。
视频回放：
上篇
下篇
对同态加密感兴趣的小伙伴，还可以点击阅读全同态加密知识体系整理(上)、全同态加密知识体系整理(下)进一步学习~
往期推荐
1.论文分享 | 联邦学习系统攻击与防御技术
2.即时通信的安全加密通信模型研究论文整理 | ICLR 2023 联邦学习论文合集4.如何实现全同态加密的电路隐私保护？