GMTC全球大前端技术大会(北京站)门票9折特惠截至本周五,点击立减¥480 了解详情
写点什么

同态加密技术及其在机器学习中的应用

2020 年 6 月 26 日

同态加密技术及其在机器学习中的应用

分布式人工智能系统是一个多学科交叉领域,从应用场景看,其既可以应用在数据中心做加速,又可以用在联邦学习领域成为多方共同训练模型的工具。而在这两个应用场景中, 隐私保护都是必不可少的。近些年同态加密在隐私保护领域备受关注,本文将科普性地介绍什么是同态加密,以及其在联邦学习、云计算领域的应用。


1 什么是同态加密

同态加密(HE,homomorphic encryption)是密码学里一种特殊的加密模式,同态加密使我们可以将加密后的密文发给任意的第三方进行计算,并且在计算前不需要解密,即:在密文上进行计算。 虽然同态加密的概念最早出现于 30 年前,但是第一个支持在密文上进行任意运算的全同态加密框架出现较晚,在 2009 年由 Craig Gentry 提出。


同态加密的数学定义为 [1]:



其中 E 为加密算法,M 是所有可能信息的集合。如果加密算法 E 满足公式(1),那么我们称 E 在★运算上符合同态加密的性质。目前的同态加密算法,主要支持两种运算上的同态:加法和乘法。


需要注意的是,以上公式(1)只是为了让我们更加清晰地理解同态加密的性质,实际中的同态加密算法可能会有一些不同。比如 Paillier 算法对加法同态,那么根据公式 (1),其密文的求和应该等于求和后的密文,但实际情况是密文的乘积等于求和后的密文,所以我们一般只要求得到的密文结果和我们预期的计算相同,但是对密文上的计算不作具体要求(一般由加密算法决定)。


2 同态加密的组成与分类

同态加密算法一般包含以下四个部分:


  1. KeyGen:密钥生成算法,产生公钥和私钥

  2. Encryption:加密算法

  3. Decryption:解密算法

  4. Homomorphic Property:同态加密计算部分


其中前三个部分在很多加密算法中都可以看到,第四部分则是同态加密算法的核心,指导密文下的运算。


为了更好地理解与运用同态加密算法,我们按照将同态加密算法支持的运算类型和数量,将其分成 3 类:部分同态加密、层次同态加密、和全同态加密 [1]。


  1. 部分同态加密(Partial HE,简称 PHE)指同态加密算法只对加法或乘法(其中一种)有同态的性质。例如:RSA 加密是最早应用的公钥加密算法框架,同时 RSA 算法也是一种 PHE 算法,其对乘法有同态的性质。PHE 的研究成果出现比较早,并且加法同态加密算法(Additive HE)比 乘法同态加密算法要多一些。PHE 的优点是原理简单、易实现,缺点是仅支持一种运算(加法或乘法)。

  2. 层次同态加密算法(LHE,Leveled HE 或 SWHE ,SomeWhat HE)一般支持有限次数的加法和乘法运算。层次同态加密的研究主要分为两个阶段,第一个阶段是在 2009 年 Gentry 提出第一个 FHE 框架以前,比较著名的例子有:BGN 算法、姚氏混淆电路等;第二个阶段在 Gentry FHE 框架之后,主要针对 FHE 效率低的问题。LHE 的优点是同时支持加法和乘法,并且因为出现时间比 PHE 晚,所以技术更加成熟、一般效率比 FHE 要高很多、和 PHE 效率接近或高于 PHE,缺点是支持的计算次数有限。

  3. 全同态加密算法(Fully HE,简称 FHE)支持在密文上进行无限次数的、任意类型的计算。从使用的技术上分,FHE 有以下类别:基于理想格的 FHE 方案、基于 LWE/RLWE 的 FHE 方案等等。FHE 的优点是支持的算子多并且运算次数没有限制,缺点是效率很低,目前还无法支撑大规模的计算。



图 1 三种类型同态加密的研究时间线 [1]


图 1 展示了三类同态加密算法的研究时间线,同态加密的概念在 1976 年提出,随后 PHE 的研究成果逐渐丰富;在 Gentry 的 FHE 框架前,LHE 研究占主导;2009 年后,研究热点集中在 FHE。


3 同态加密在机器学习中的应用

3.1 联邦学习(PHE)

联邦学习是一种隐私保护机器学习方法,其主要思想为:构建一个隐私保护机器学习系统,使得拥有数据的多方能够联合训练一个或多个模型,并且任意一方的数据不会泄露给其他参与者。这能在保证隐私数据不泄露的情况下,提升参与者们本地模型的任务表现,打破数据孤岛 [2]。




图 2 联邦学习流程示例


在联邦学习中,多方联合训练模型一般需要交换中间结果,如果直接发送明文的结果可能会有隐私泄露风险。在这种场景下,同态加密就可以发挥很重要的作用。多方直接将中间结果用同态加密算法进行加密,然后发送给第三方进行聚合,再将聚合的结果返回给所有参与者,不仅保证了中间结果没有泄露,还完成了训练任务(第三方可以通过优化系统设计去除)。


在联邦学习中,因为只需要对中间结果或模型进行聚合,一般使用的同态加密算法为 PHE(多见为加法同态加密算法),例如在FATE中使用的 Paillier 即为加法同态加密算法。为了更好地展示同态加密在联邦学习中的应用,我们在此展示一个同态加密在联邦学习推荐系统中的应用 [3]。



图 3 联邦矩阵分解推荐系统流程


在传统的推荐系统中,用户需要上传浏览记录、评价信息来实现个性化推荐,但是这些信息均属于个人的隐私数据,直接上传会带来很大的安全隐患。在联邦推荐系统中,每个用户将数据保存在本地,只上传特定的模型梯度。这样虽然避免了隐私数据的直接泄露,但是还是透露了梯度信息给云服务器。同时我们发现,从数学上可以证明,使用连续两次更新的梯度即可反推出用户的评分信息。这种情况下,就必须使用同态加密对用户上传的梯度进行保护,即用户在上传梯度前使用加法同态加密算法对梯度信息进行加密,然后云服务器将所有用户的密文梯度进行聚合(相加),再将更新后的模型返还给各个用户解密,完成训练更新。


3.2 密态机器学习(LHE and FHE)


除了联邦学习外,同态加密另一个比较重要的应用领域是密态计算。和联邦学习不同的是,密态计算不需要多方参与,但需要的计算比联邦学习更加复杂(算子多、计算量大)。密态计算中使用的同态加密算法多为 LHE 和 FHE。其实全同态加密研究的初衷,就是为了实现安全的云计算,即对云算力有需求的用户可以将本地的数据全部加密,然后上传到云端,然后云端的服务器即可按照用户指令完成计算,整个过程用户的数据不会泄露给云端,从而完成“绝对安全”的云计算服务。


但是由于目前 FHE 效率比较低,所以使用全同态加密进行云计算远远没有达到应用的级别。机器学习在云计算中有着广阔的市场,而机器学习有训练和推理两种需求,训练过程一般数据较多、计算量很大,而推理则数据量相对较小、计算量也小,所以目前研究主要集中在密态下的机器学习推理,并且目前已经有速度比较快的方案 [4];而密态下的机器学习训练研究稀少,是一个比较难解决的问题。


4 部分开源同态加密库的效率比较

目前 GitHub 中有很多的开源 HE 框架,在这里我们选择两个进行测试比较,一个是python-paillier,支持加法同态;一个是SEAL-CKKS,属于 LHE 算法,支持有限次数的加法和乘法。



表 1: Paillier 和 CKKS 的效率对比(ms)


表 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


作者介绍:柴迪,星云 Clustar 算法工程师,香港科技大学在读博士,于 2018 年在香港科技大学取得理学硕士学位,研究方向为联邦学习、隐私保护机器学习。可通过以下邮箱联系:dchai@cse.ust.hk


参考文献:


[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, .


2020 年 6 月 26 日 09:004646

评论

发布
暂无评论
发现更多内容

What's new in Dubbo-go v1.5.1

apache/dubbo-go

golang dubbo 服务端

抗疫代码入国家博物馆, 程序员的巅峰时刻!

程序员生活志

程序员 程序员代码

架构师训练营第十三周作业

Hanson

架构师训练营第13周作业

服务化反面案例

心平气和

服务化 权限

解Bug之路-Nginx 502 Bad Gateway

无毁的湖光

nginx Linux TCP

超详细:完整的推荐系统架构设计

博文视点Broadview

架构 算法 推荐系统

大专生拿到阿里offer,却担心背调不过,网友:985在你面前黯淡无光

程序员生活志

面试 职场 阿里

如何在企业微信上搭建一款活动报名 App

Ceelog

go 企业微信

架构师训练营第十三周作业

张明森

超级TV盒子,超清秒播,解锁全网VIP资源!

程序员生活志

资源

架构师训练营第十三周总结

Hanson

模板方法模式——看看 JDK 和 Spring 是如何优雅复用代码的

简爱W

Java 程序员 java架构

Spring 5 中文解析核心篇-集成测试之TestContext(上)

青年IT男

单元测试 Spring5 JUnit

「查缺补漏」巩固你的RocketMQ知识体系

Kerwin

Java RocketMQ

为什么一个还没毕业的大学生能够把 IO 讲的这么好?

cxuan

Java 后端 io

PageRank 算法

周冬辉

克隆虚拟机

yuanhang

Hessian Bug修复

心平气和

php 序列化 hessian

大数据

yuanhang

Centos 7 虚拟机

关于二进制的补码,反码,正负数表示以及Java代码测试

Zexho

Java 补码 位运算 反码 计算机知识

第13周 作业

Jaye

对PageRank的理解

2流程序员

开源流数据公司 StreamNative 正式加入 CNCF,积极推动云原生策略发展

Apache Pulsar

云原生 pulsar Apache Pulsar 消息系统 消息中间件

全票通过!易观开源项目DolphinScheduler进入Apache孵化器

易观大数据

防止APP窃取用户隐私问题,OPPO安全在行动

OPPO安全

App 安全 隐私保护 数据隐私 sdk

字节小组长无意中得知整个部门的薪资,自己28K,手下却有35K,怎么办?

程序员生活志

字节跳动 职场 薪资

架构师训练营第 0 期第 13 周作业

无名氏

oeasy 教您玩转linux 之010208 满屏乱码 bb

o

你应该了解的MySQL锁分类

X先生

MySQL 数据库 sql 数据库优化

​程序员离职后收到原公司 2400 元,被告违反竞业协议赔 18 万

程序员生活志

程序员 职场

同态加密技术及其在机器学习中的应用-InfoQ