全同态加密知识体系整理(下)

本文紧接全同态加密知识体系整理（上），将介绍以FHEW和TFHE为代表的高效自举（Bootstrapping）技术。这类方法相比于上期介绍的层次同态加密（LHE）方法有自己的优势。对于LHE类型的方案来说，只支持加法和乘法操作，对于非多项式的函数，比如激活函数等需要使用高次多项式拟合，而FHEW类型的方案可以在自举的同时运算一个任意的函数，但是这类方案对于多项式打包并不友好。除此之外，本文还将介绍同态加密的应用案例以及前沿研究等。

1

FHEW类型同态加密

FHEW类型的同态加密，优点在于Bootstrapping较快，缺点是每次只能刷新几个比特的密文，且不支持SIMD。有一个特性在于可以在Bootstrapping的同时对刷新的这几个比特执行一个任意的函数，即BlindRotate 刷新几比特密文Functional Bootstrapping 刷新的同时运算某个函数
2

同态加密应用

2.1 隐私集合求交PSIPSI场景：Alice有数据库，Bob有数据库。现在Alice想要知道自己的数据库和Bob重合的部分有哪些，即，但彼此不暴露其他信息。使用同态实现的基础思路：

1. 对于中的数据，Alice使用同态加密。
2. Bob收到后，运算对于每条，运算并返回。
3. Alice解密，若结果为0，则表示在的数据库中。

以上为基础思路，优化方法可见：[1] Chen, H., Huang, Z., Laine, K., & Rindal, P. (2018). Labeled PSI from Fully Homomorphic Encryption with Malicious Security. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security.[2] Cong, K., Moreno, R.C., Gama, M.B., Dai, W., Iliashenko, I., Laine, K., & Rosenberg, M. (2021). Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security.效率：

的量级是两亿。是400万。在unbalanced情况下，通信开销是非常小的。
2.2 隐匿查询PIR

PIR场景：

Alice有一个索引，Bob有一个数据库。Alice想在不暴露的情况下得到。使用同态加密实现的基础思路：

1. Alice构造一个查询序列：，其中。
2. Alice加密这个查询序列：，并发送给Bob。
3. Bob进行运算并返回给Alice。
4. Alice解密得到。

以上为基础思路，优化方法可见：[1]Ali, A., Lepoint, T., Patel, S., Raykova, M., Schoppmann, P., Seth, K., & Yeo, K. (2019). Communication-Computation Trade-offs in PIR. IACR Cryptol. ePrint Arch., 2019, 1483.[2]https://github.com/microsoft/SealPIR[3]https://github.com/OpenMined/PIR效率：2.3 作为MPC组件生成Beaver Triple2.4 作为FL的组件作为加法同态做聚合3

通用的优化方法

3.1 计算效率（RNS,NTT,Montgomery）NTT加速：多项式之间的计算可通过NTT来加速Montgomery：快速的取模运算，针对很多数据对同一个素数取模的运算。主要介绍一下RNS：计算机原生支持64bit的模加和模乘算法但在同态加密的构造中往往模数，比如比特。为了避免使用高精度大整数库，我们将比特的分成个小,原本一个的数字，我们分别用四个数字来表示，分别为。
在同态加密库中，比如CKKS和BFV，会看到这样的表达，其实就是取了个素数来表达比特的模数 。
3.2 通信开销（随机种子,模数替换）随机种子，可以用于传输中，只发送生成的随机数种子和，能节省一半的通信开销。模数替换，降低模数就是降低表达一个密文所需要用到的比特的数量。
4

前沿研究

4.1 CKKS的安全性问题CKKS因为解密带噪声，所以会有安全性问题。比如。而，所以完全可以计算来得到，那么就很容易推出密钥了。现在各大同态加密库都解决了这个问题了。可参考:[1]https://link.springer.com/chapter/10.1007/978-3-030-77870-5_234.2 将FHEW类型的密文和RLWE类型的同态加密结合比如PEGASUS，CHIMERA。都是用RLWE来算加法乘法运算，用FHEW类型的操作来算激活函数之类的。可参考：https://www.degruyter.com/document/doi/10.1515/jmc-2019-0026/html[2]https://eprint.iacr.org/2020/16064.3 研究如何进行快速的Bootstrapping通过扩模方式来实现Bootstrapping。可参考：https://eprint.iacr.org/2021/6914.4 将RLWE类型的同态加密与MPC结合，通过MPC实现Bootstrapping过程可参考：https://eprint.iacr.org/2020/1396
5

同态加密参数（实现相关）

5.1 推荐参数关于安全的参数选取的标准在Standard – Homomorphic Encryption Standardization中有给出几个推荐的参数集合。参考链接：https://homomorphicencryption.org/standard/解释一下几个表头：如果如果不使用推荐的参数，而是用自行选取的参数，可以使用lwe-estimator来计算出当前选取参数的安全等级。参考链接：https://lwe-estimator.readthedocs.io/en/latest/
5.2 参数与效率一般来说，取得越大，安全性越高，取得越大，安全性越低。这两项一般是同时增加或同时减小以满足相同等级的安全性。而这两项增加会导致运算效率变低。但会增加计算的能力，也就是乘法的层数。在CKKS中有，BFV中有明文空间的模数，这两项与效率无关。和与明文的表达能力有关，越大则能表达越精确或越多的数。但会减少计算的能力，一般来说或越小，能运算乘法的次数越多。

5.3 代码中参数的解释

以SEAL库为例：

CKKS：

• 第一行创建了一个params类型，指定了方案为CKKS。
• 第二三行设置了多项式的阶为，根据之前的参数表，模数的比特数为时能达到128bit安全。越小，安全性是越高的。
• 第四行创建了4个素数，他们的比特数分别为，这里具体说明一下，首先四个模数加起来是200bit，小于需要218bit，所以这里能达到128位的安全性。
• 最后一个模数是一个特殊模数，用于在Keyswitch中减小噪声，可以暂时不去看他。
• 主要的模数是，一般来说，除了第一个模数，后面的模数的大小都是和扩张因子长度相同的。
• 因为在CKKS中，没做完一次乘法，就要采用模数替换的方法，将变为，也就是除掉一个和大小类似的数。
• 而第一个模数是决定了CKKS明文能表示的精度和整数位。因为采用了的方式来表示一个数字，因此的大小代表了能表示多少小数位，的大小代表了整数部分能有多少位。

CKKS:

BFV与CKKS在设置参数上面的区别在于，CKKS需要设置scale，即。而BFV设置的是plain_modulus，即。
5.4 开源库效率测试SEAL

Lattigo

BFV n=8192,q=218。

作者简介：沈华杰，毕业于华东师范大学，目前任职电信翼支付的密码算法工程师，主要关注FHE，MPC，ZK等技术的发展与应用。

我们社区的小伙伴也会在学习群内讨论同态加密技术，下面罗列出几个问题，小伙伴们可以在推文下方留言，也可以扫描推文末尾小编微信加入学习群一起讨论~

1. 从格推演到全同态加密算法的原理是什么？

2. 在同态加密的CKKS方案中，精度和参数的选取有怎样的关系？

本周六下午，本文作者沈老师将在开放隐私计算社区城市见面会杭州站，分享同态加密知识体系，和大家一起讨论如何入门、学习难点，以及同态加密商业化程度、硬件加速最新进展等问题，欢迎大家参与~

活动地点以及时间如下：

时间：2023年4月1日（本周六）下午14：00-17：00

地点：浙江省杭州市滨江区西兴街道联慧街188号安恒大厦

惊喜：来现场，超多惊喜的社区周边精美大礼包等你噢！

报名方式：扫码报名

END

往期推荐

1.全同态加密知识体系整理(上)
2.联邦学习安全聚合：基于安全多方计算的经典方案3.椭圆曲线密码在多方安全计算中的应用4.SGX-FPGA | CPU-FPGA异构体系结构的可信执行环境