因为一条微软开源同态加密算法库SEAL的消息,这两天不少朋友询问我关于同态加密技术的应用问题。2018年12月1日,微软在github上开源了简单加密运算库(Simple Encrypted Arithmetic Library:SEAL)。实际上,SEAL不是最早的同态加密算法开源库,也不是支持算法最多的。还有一些较好的开源库,比如HElib、PALISADE、TFHE。PALISADE的速度非常快、TFHE支持的算法最多。

关于同态加密算法的实用性问题,回答分为两个部分。

一是在理论上,支持在密文上执行任意深度电路(通俗地讲就是任意一个数据应用)的全同态加密算法远不到实用的程度。

二是在实践中,我们对一个数据集进行的操作绝大多数情况下都是有限的(就是电路深度是有限的,或者通俗地讲就是程序执行长度是有限的)。在这种情形下,我们只需要特殊的全同态:Somewhat HE或者Leveled HE。对于一些应用,SHE已经有具有一定的实用性。举两个例子:

2018年4月Cheon-Han-Kim-Kim-Song报道采用CKKS算法和同态加密算法在575个加密过的样本上执行机器学习构建LRM(logistic regression model)模型。构建这个模型主要是统计分析计算(包括浮点运算),他们在i5的CPU上使用一个核在1.8分钟内完成了模型的训练。

2018年12月Halevi-Polyakov-Shoup报道采用中国剩余定理(CRT)实现BFV同态加密算法。他们使用E5 CPU的系统在62毫秒内可以在密文上完成20次乘法(1次乘法约3毫秒,5次乘法约10毫秒)。

鉴于同态加密算法已经具有一定的实用性,相关组织也在进行一些标准化工作。

homomorphicencryption.org在2018年11月发表了"Homomorphic Encryption Standard"1.1版(文档链接http://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf)。这个文档仍然处于更新过程中,目前包括BGV/BFV/GSW算法的基本描述,提及YASHE和CKKS。

即使有标准的指导,同态加密算法的选择和使用仍然不是一件轻松的事。因为没有一个算法能够在密文扩展、性能、支持密文运算能力上都到达最优,所以在选择同态加密算法上我们需要根据待保护数据集特征、数据上的实际计算操作等因素来选择合适的算法、设置合理的参数,以便取得最好时间和空间效率。

另外,如果数据集只有整数且操作也是整数运算,选择BGV、BFV等算法可能比较合适,如果有浮点运算,则目前选择CKKS是合适的。SEAL、PALISADE、TFHE等都同时支持BFV和CKKS。Costache-Smart认为长明文选择BGV更合适,而短明文则适合YASHE。注意这是2016年的分析比较,最新研究显示BFV/YASHE等算法可以利用新的高效实现技术。