【原创】同态加密及其应用
本文作者：北京海泰方圆科技股份有限公司首席密码专家 Shookin
当前，云服务应用广泛，云上数据安全备受关注。为了解决云上数据安全，催生出引人入胜的应用场景，即同态服务。简言之，云端对数据进行同态加密，可直接对密文进行计算，再将计算结果从云端发回用户解密，得到相应明文的计算结果。同态服务是云服务中最具有诱惑力的服务，同态加密技术是云计算安全技术体系的制高点，国内外非常重视同态加密技术的发展。海泰方圆作为一家以密码技术为核心的信息安全企业，结合当前国内外的研究成果，对同态加密技术进行了综合研究，对整数环上的同态加密、Paillier算法、FV算法等同态加密算法有过分析研究。
何为同态加密？为了便于理解，这里给出一种数学上不太严格的简单的定义。设x与y为明文数据，E为加密算法，如果在明密文空间上分别存在一种运算“+”和“⊕”，使得E(x+y) =E(x)⊕E(y) 成立，那么这时就称E是加法同态加密。如果在明密文空间上分别存在一种运算“*”和“?”，使得E(x*y) =E(x)?E(y)成立，那么这时就可以称E为乘法同态加密。如果E既是加法同态加密，也是乘法同态加密，那么就称E为全同态加密（FHE）。还有一种叫做SHE（somewhat homorphicencryption) 的同态加密，仅能支持密文空间上有限次加法和乘法同态运算。加法同态、乘法同态、SHE均属于非全同态或部分同态。对于只需要在密文上进行特定计算的应用场景，使用部分同态加密方案有时能够在数据的密文上高效地完成计算功能，同时这些同态加密方案达到语义安全，保证数据机密性。
加法同态加密图
乘法同态加密图
为简便起见，在明密空间上的运算不易混淆的情况下，明密文空间上的加法可统一用“+”表示，明密文空间上的乘法运算可统一用“*”表示。如果E是全同态加密，根据加法同态性，对明文x，进行n次叠加再加密，则
E(nx)=E(x+x+…+x)=E(x)+E(x)+…+E(x)=nE(x). 即E(nx)=n E(x).
同样地，全同态也具有乘法同态性，对明文x，进行n次乘法再加密，则
E(xn)=E(x*x*…*x)=(E(x))n.即E(xn)=(E(x))n.
综合利用上述全同态加密的加法同态性和乘法同态性，假设对明文x进行多项式f(x)计算再加密，不妨假设f(x)=a1x+a2x2+…+anxn，则
E(f(x))=E(a1x+a2x2+…+anxn)=E(a1x)+E(a2x2)+…+E(anxn)
= a1E(x)+a2E(x2)+…+anE(xn)=a1E(x)+a2(E(x))2+…+an(E(x))n
=f(E(x)).
即E(f(x))=f(E(x))，也就是对明文进行多项式计算再加密等价于对明文加密再进行多项式计算，具有这种全同态性质的函数E在一般实数域空间上是难以找到的，除非E退化为恒等变化函数，即E(x)=x，明密相同，这其实就是没加密，显然这样的函数是毫无意义的。
能否构造非退化的全同态加密FHE？该公开问题自提出以来困扰了人多年，直到Gentry在其博士论文中提出了第一个全同态加密方案，即基于多项式环上理想格的全同态加密方案。Gentry全同态加密的关键技术称为Bootstrapping，方案可以简单地概括为：“FHE=SHE+Bootstraping”，这就是说，每当同态运算的次数太多使得误差尺寸过大时，就使用自举降低误差尺寸，于是SHE就改造成了全同态加密FHE。
目前，基于Gentry的FHE方案历经了多次演变，引入了很多新的处理技术，每个新技术的出现都带来了FHE方案效率的提高。尽管全同态加密是解决加密数据计算这一问题的最佳方案，但是，目前其性能往往大多不能满足实际应用需求，而一些部分同态加密方案可用于解决特定的加密数据计算的应用问题。当前出现的全同态加密有基于格的BGV全同态加密、bra12全同态加密、GSW13全同态加密，以及整数环上的全同态加密，LWE全同态加密、FV同态加密等。
国内首个密文查询算法团体标准——《T/SCCIA001-2019 基于整数同态加密的密文查询算法标准》于2019年6月通过专家评审，2019年11月22日正式发布。标准规定了基于整数的同态加密的密文查询算法，并给出了密文查询的流程和示例。
同态加密技术在分布式计算环境下的密文数据计算方面具有比较广泛的应用领域，比如安全云计算、安全多方计算、安全智能电网等。
3.1 安全云计算
云计算为用户提供了高灵活性、动态可扩展性、高性价比等特点的应用，而将数据上云，给云计算中的数据带来安全问题，云计算环境同态密码的应用可以使得我们在云环境下，充分利用云服务器的性能，通过对密文的运算间接地实现对明文的运算，保护数据的私密性。用户数据通过同态加密存储于云端，被同态加密的数据在云端可进行基于密文的运算，运算结果仍为密文形式，用户对运算结果执行相应的同态解密便可得到相应于明文运算的结果。例如，用户可以向云端查询、检索、统计自己所需要的信息，查询、检索、统计对象为密文数据，云端将查询、检索、统计到的密文数据发回，用户再通过同态解密得到自己需要的信息，整个数据处理结果、数据内容对云端完全透明的。同态密码应用于基于云计算的医疗大数据，可有效保护患者隐私。
3.2 安全多方计算
所谓安全多方计算（MPC)就是分别持有私有数据的多方，在分布式环境中协同执行一个算法而不泄露各方的私有数据。安全多方计算允许多个数据所有者在互不信任的情况下进行，输出计算结果的同时保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说，MPC技术可以获取数据使用价值，却不泄露原始数据内容。在网络环境和分布式环境背景下的大数据共享在很多时候可以归纳为安全多方计算。安全多方计算应用于电子选举、门限签名以及电子拍卖等诸多方面。同态加密技术可以满足安全多方计算协议设计中保护各方隐私的需要，例如，基于同态加密技术设计的电子选举方案，统计方可以在不知道投票者投票内容的前提下，对投票结果进行统计，既保证了投票者的隐私安全，又能够保证投票结果的公证。
3.3安全智能电网
智能电网通过使用数字化的通信和控制技术，对系统中的电网节点进行有效的控制和监视。智能电网提供具有多个节点的网络，其中每个节点产生大量数据。大型智能电网监控每个节点产生的数据。监控系统可以利用同态加密对来自网格上每个节点的状态数据进行计算。相关研究方面，有基于同态加密技术的智能电网WSNs数据融合方案，它利用对称同态加密方案对数据的机密性和完整性保护，融合节点实现网内虚假数据过滤，提高了数据的有效性，同时避免因传输虚假数据包而消耗不必要的能量。此外，得益于无双线性配对的签名方案的高效性和对称同态加密方案的简单高效性，成员节点的计算代价低。
参考资料
[1]. Gentry C. A fully homomorphic encryption scheme [ D ]. Stanford：Stanford University, 2009.
[2]. Gentry C. Fully homomorphic encryption using ideal lattices [ C] //Proc of Annual ACM Symposium on Theory of Computing. New York ：ACM Press,2009：169-178.
[3]. 几类同态加密方案的研究，陈虎，西安电子科技大学博士学位论文，2016年.
[4]. 基于格的同态加密研究与设计，陈智罡，南京航空大学博士学位论文，2015年.
[5]. 同态加密的发展及应用，巩林明、李顺东、郭奕旻，中兴通讯技术第22卷第1期2016年2月.
[6]. 基于同态加密的智能电网WSNs 安全数据聚合，史丰图，赤峰学院学报（ 自然科学版）第35卷第4期 2019年4月.
[7]. 全同态加密的发展与应用，王付群，信息安全与通信保密 NOV 2018.