同态加密技术及其在机器学习中的应用
source link: https://www.infoq.cn/article/iHaL9CagG9fY7algmpuy
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
分布式人工智能系统是一个多学科交叉领域，从应用场景看，其既可以应用在数据中心做加速，又可以用在联邦学习领域成为多方共同训练模型的工具。而在这两个应用场景中， 隐私保护都是必不可少的。近些年同态加密在隐私保护领域备受关注，本文将科普性地介绍什么是同态加密，以及其在联邦学习、云计算领域的应用。
1 什么是同态加密
同态加密（HE，homomorphic encryption）是密码学里一种特殊的加密模式，同态加密使我们可以将加密后的密文发给任意的第三方进行计算，并且在计算前不需要解密，即：在密文上进行计算。 虽然同态加密的概念最早出现于 30 年前，但是第一个支持在密文上进行任意运算的 全同态加密 框架出现较晚，在 2009 年由 Craig Gentry 提出。
同态加密的数学定义为 [1]：
其中 E 为加密算法，M 是所有可能信息的集合。如果加密算法 E 满足公式 (1)，那么我们称 E 在★运算上符合同态加密的性质。目前的同态加密算法，主要支持两种运算上的同态：加法和乘法。
需要注意的是，以上公式 (1) 只是为了让我们更加清晰地理解同态加密的性质，实际中的同态加密算法可能会有一些不同。比如 Paillier 算法对加法同态，那么根据公式 (1)，其密文的求和应该等于求和后的密文，但实际情况是密文的乘积等于求和后的密文，所以我们一般只要求得到的密文结果和我们预期的计算相同，但是对密文上的计算不作具体要求（一般由加密算法决定）。
2 同态加密的组成与分类
同态加密算法一般包含以下四个部分：
- KeyGen：密钥生成算法，产生公钥和私钥
- Encryption：加密算法
- Decryption：解密算法
- Homomorphic Property：同态加密计算部分
其中前三个部分在很多加密算法中都可以看到，第四部分则是同态加密算法的核心，指导密文下的运算。
为了更好地理解与运用同态加密算法，我们按照将同态加密算法支持的运算类型和数量，将其分成 3 类：部分同态加密、层次同态加密、和全同态加密 [1]。
- 部分同态加密（Partial HE，简称 PHE）指同态加密算法只对加法或乘法（其中一种）有同态的性质。 例如：RSA 加密是最早应用的公钥加密算法框架，同时 RSA 算法也是一种 PHE 算法，其对乘法有同态的性质。PHE 的研究成果出现比较早，并且加法同态加密算法（Additive HE）比 乘法同态加密算法要多一些。 PHE 的优点是原理简单、易实现，缺点是仅支持一种运算（加法或乘法）。
- 层次同态加密算法（LHE，Leveled HE 或 SWHE ，SomeWhat HE）一般支持有限次数的加法和乘法运算。 层次同态加密的研究主要分为两个阶段，第一个阶段是在 2009 年 Gentry 提出第一个 FHE 框架以前，比较著名的例子有：BGN 算法、姚氏混淆电路等；第二个阶段在 Gentry FHE 框架之后，主要针对 FHE 效率低的问题。 LHE 的优点是同时支持加法和乘法，并且因为出现时间比 PHE 晚，所以技术更加成熟、一般效率比 FHE 要高很多、和 PHE 效率接近或高于 PHE，缺点是支持的计算次数有限。
- 全同态加密算法（Fully HE，简称 FHE）支持在密文上进行无限次数的、任意类型的计算 。从使用的技术上分，FHE 有以下类别：基于理想格的 FHE 方案、基于 LWE/RLWE 的 FHE 方案等等。 FHE 的优点是支持的算子多并且运算次数没有限制，缺点是效率很低，目前还无法支撑大规模的计算。
图 1 展示了三类同态加密算法的研究时间线，同态加密的概念在 1976 年提出，随后 PHE 的研究成果逐渐丰富；在 Gentry 的 FHE 框架前，LHE 研究占主导；2009 年后，研究热点集中在 FHE。
3 同态加密在机器学习中的应用
3.1 联邦学习（PHE）
联邦学习是一种隐私保护机器学习方法，其主要思想为：构建一个隐私保护机器学习系统，使得拥有数据的多方能够联合训练一个或多个模型，并且任意一方的数据不会泄露给其他参与者。这能在保证隐私数据不泄露的情况下，提升参与者们本地模型的任务表现，打破数据孤岛 [2]。
在联邦学习中，多方联合训练模型一般需要交换中间结果，如果直接发送明文的结果可能会有隐私泄露风险。在这种场景下，同态加密就可以发挥很重要的作用。多方直接将中间结果用同态加密算法进行加密，然后发送给第三方进行聚合，再将聚合的结果返回给所有参与者，不仅保证了中间结果没有泄露，还完成了训练任务（第三方可以通过优化系统设计去除）。
在联邦学习中，因为只需要对中间结果或模型进行聚合，一般使用的同态加密算法为 PHE（多见为加法同态加密算法），例如在 FATE 中使用的 Paillier 即为加法同态加密算法。为了更好地展示同态加密在联邦学习中的应用，我们在此展示一个同态加密在联邦学习推荐系统中的应用 [3]。
在传统的推荐系统中，用户需要上传浏览记录、评价信息来实现个性化推荐，但是这些信息均属于个人的隐私数据，直接上传会带来很大的安全隐患。在联邦推荐系统中，每个用户将数据保存在本地，只上传特定的模型梯度。这样虽然避免了隐私数据的直接泄露，但是还是透露了梯度信息给云服务器。同时我们发现，从数学上可以证明，使用连续两次更新的梯度即可反推出用户的评分信息。这种情况下，就必须使用同态加密对用户上传的梯度进行保护，即用户在上传梯度前使用加法同态加密算法对梯度信息进行加密，然后云服务器将所有用户的密文梯度进行聚合（相加），再将更新后的模型返还给各个用户解密，完成训练更新。
3.2 密态机器学习（LHE and FHE）
除了联邦学习外，同态加密另一个比较重要的应用领域是密态计算。和联邦学习不同的是，密态计算不需要多方参与，但需要的计算比联邦学习更加复杂（算子多、计算量大）。密态计算中使用的同态加密算法多为 LHE 和 FHE。其实全同态加密研究的初衷，就是为了实现安全的云计算，即对云算力有需求的用户可以将本地的数据全部加密，然后上传到云端，然后云端的服务器即可按照用户指令完成计算，整个过程用户的数据不会泄露给云端，从而完成“绝对安全”的云计算服务。
但是由于目前 FHE 效率比较低，所以使用全同态加密进行云计算远远没有达到应用的级别。机器学习在云计算中有着广阔的市场，而机器学习有训练和推理两种需求，训练过程一般数据较多、计算量很大，而推理则数据量相对较小、计算量也小，所以目前研究主要集中在密态下的机器学习推理，并且目前已经有速度比较快的方案 [4]；而密态下的机器学习训练研究稀少，是一个比较难解决的问题。
4 部分开源同态加密库的效率比较
目前 GitHub 中有很多的开源 HE 框架，在这里我们选择两个进行测试比较，一个是 python-paillier ，支持加法同态；一个是 SEAL -CKKS，属于 LHE 算法，支持有限次数的加法和乘法。
表 1 展示了 Paillier 和 CKKS 的效率对比，时间单位为毫秒，测试机器为 Intel® Xeon® E5-2630 24-core 2.6GHz CPU，63GB RAM，表格 C+P 中的 C 代表密文、P 代表明文。表格中 CKKS 的 key 含义为 polynomial modulus degree。
从结果中可以看出，paillier 在 key size 逐渐增大时，耗时迅速增长（速度超过线性），paillier 一般使用最少 2048 位密钥来保证安全， 2048 位下的 paillier 运算效率高于 CKKS。值得一提的是，SEAL-CKKS 支持 SIMD 操作，所以在机器学习的训练、推理中，可以按照 batch size 维度对一批数据进行打包、加密，使得运算效率线性提升。
总结：在不能够使用 SIMD 操作时（部分机器学习场景可能没有 batch 的情况，比如矩阵分解），使用 key size 比较小的 paillier 效率更高；在能够使用 SIMD 操作时（例如大部分场景下的机器学习模型训练、推理），SEAL-CKKS 效率显著高于 paillier。
除了 Paillier 和 CKKS，未来我们将测试更多的同态加密算法效率，以便为同态加密的应用提供参考，欢迎查看 GitHub 项目主页：
https://github.com/Di-Chai/he-benchmark参考文献：
[1] A. Acar et al , “A Survey on Homomorphic Encryption Schemes,” ACM Computing Surveys (CSUR), vol. 51, (4), pp. 1-35, 2018. Available: http://dl.acm.org/citation.cfm?id=3214303 . DOI: 10.1145/3214303.
[2] Q. Yang et al , “Federated Machine Learning,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 10, (2), pp. 1-19, 2019. Available: http://dl.acm.org/citation.cfm?id=3298981 . DOI: 10.1145/3298981.
[3] D. Chai et al , “Secure federated matrix factorization,” arXiv Preprint arXiv:1906.05108, 2019.
[4] C. Juvekar, V. Vaikuntanathan and A. Chandrakasan, “{GAZELLE}: A low latency framework for secure neural network inference,” in 27th {USENIX} Security Symposium ({USENIX} Security 18), 2018, .
Recommend
-
42
布隆过滤器、同态加密、PKI体系……一文告诉你密码学在区块链中能做什么区块链大本营2019-10-19理解为什么区块链可以防止消息被篡改、怎么进行数字身份认证
-
23
-
24
-
33
CCS 2017 - 基于同态加密的高效隐私集合求交协议密码学话题下的优秀回答者演讲视频简介格密码视频被花式催更，无奈最近实在是太忙了，没有时间静下心来整理字幕，但我保...
-
16
点击 蓝字 关注我们 只有获得了对加密数据直接执行复杂计算的能力，公共及私营部...
-
11
同态加密(HE)是一种隐私保护技术，可以直接在加密数据上执行计算任务。HE支持安全的远程计算，云服务提供商可以在不查看高度敏感数据的情况下进行数据计算(即“可用不可看”)。但是，尽管颇具吸引力，但性能和可编程性方面面临的挑战仍然是HE广泛采用的主...
-
6
【乘求值修正完毕】同态加密标准（译稿）密码学话题下的优秀答主今天无意中看到开放隐私计算（微信公众...
-
6
阅读paper"一种高效的同态加密方案及其应用"的笔记。 基础# 生成可逆矩阵对的算法
-
2
隐私计算中的完同态加密为加密数据提供量子安全级的计算，保证明文数据及其衍生计算结果永远不会公开，并且在基础设施受到破坏的情况下保持安全，不会被修改和/或破坏。大多数完同态加密方案都是基于lattice 数学方式描述的（序理论和抽象代数子学科研究的一种抽象）...
-
5
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK