同态密码的理论及应用

同态加密研究背景

作为同态加密重要应用领域的“云计算”是当前信息技术领域的热门话题之一，所谓云计算是由分布式云计算、网格云计算、并行云计算、云存储、存储与计算虚拟化、负载均衡等技术的发展融合，将多个成本较低的计算节点整合成一个有强大计算能力的云计算系统，借助以下几种服务来部署环境：
1）基础设施即服务（IaaS)，如Amazon的弹性云（Elastic Compute Cloud,简称EC2）、IBM的蓝云（Blue Cloud）、阿里巴巴地阿里云（Aliyum）、以及Sun的云基础设施平台（IaaS）等。
2）平台即服务（PaaS)，如Google的Google APP Engine 与微软的Azure平台等。
3）软件即服务（SaaS),如Salesforce公司的客户关系管理服务等。正是由于云计算把计算能力分布到了终端用户，具有的便利、经济、可扩展性等特点，使得广大企业投入了越来越多的目光，他们能过从沉重的基础设施建设、维护和升级中腾出手来，更加关注自身核心产能的提高和发展。

云计算按照部署模式可以分为：私有云、公有云和混合云。
1)公有云(PublicClouds)，第三方提供一般公众或大型产业集体使用的云端基础设施，是云计算的主要形态，拥有很强的数据处理能力，而且价格低廉，能提供有吸引力的服务，创造新的业务价值，且作为一个支撑平台，能够整合上游的各种服务(如增值业务，广告)提供者和下游的最终用户，去打造新的价值链和 生态系统。
2)私有云(PrivateClouds)是为了满足客户的单独使用构建的，提供对数据、 安全性、服务质量的有效控制。但需要公司拥有基础设施，并能将应用程序部署在基础设施上。私有云一般部署在企业数据中心的防火墙内，或将它们部署在一 个安全环境下的主机上。
3)混合云(Hybrid cloud)，是目标架构中公有云、私有云或者公众云三者的 结合。由于安全和控制原因，企业信息并不是都能放置在公有云上，所以大部分应用云计算的企业都采用了混合云模式。还有很多选择了同时使用公有云和私有云，有一些也会同时建立公众云。
私有云和公有云各自为政，而是私有云和公有云同时协调工作。下面是一个 经典事例：在私有云里实现利用存储、数据库和服务处理，同时，在无须购买额外硬件的倩况下，在需求高峰期充分利用共有云来完成数据处理需求。目前，已经有很多企业都朝着这种集中云(Cloud-Bursting)的架构发展，同时这也是实现利益最大化的关键。

随着云计算的迅速普及，云安全问题也日益隐现。Symantec近期一项研究显示，云安全仍是人们首要关心的问题。2013年6月，前美国中情局(CIA)职员爱德华·斯诺登震惊全球的“棱镜门”事件对云计算市场也有所影响。棱镜计划反映了网络安全隐患，一场有关云安全的讨论和反思正在全球范围内展开。“美国国家安全局通过互联网获得个人信息，首先得归功于云计算时代。如今大量用户数据明文信息不再存放于个人电脑中，而是在云服务提供商手中。”此次，“棱镜门”事件的发生，让我们有机会重新审视云安全问题，并思考相关对策圆。解决云计算安全问题的当务之急是针对威胁，建立综合性的云计算安全框架，为实现用户的安全目标提供技术支撑，并积极开展各个云安全关键技术的研究工作，云计算安 全大致可以分为三个方面：
一、云计算服务提供商的网络安全问题。这个问题包括云端存储的帐号和身 份信息的安全性，存在不存在被盗取的可能性。大量数据在云端存储的时候，提供商会不会对数据进行统计和分析。
二、客户在使用云计算服务时的安全问题。包括如何将存放云端或本地的数据进行划分，不同安全性之间是怎么平衡的，或者选择什么加密算法进行密文存 储。检索过程中，密文数据解密后的泄漏问题。
三、客户对自己隐私信息保护的间题。客户在把数据提交给云端后，数据在 客户端是如何进行销毁或保存的也会造成数据的泄漏问题。
密文的检索和云端密文数据的处理是云计算中的关键研究技术，云端如果能 够针对用户实际需求对密文数据进行操作，那么将大大提高云端的应用效率，同时也会降低用户数据交互过程中的隐私泄漏风险。
从目前的研究成果来看，同态密码技术能够一定程度上解决上述问题，在实现数据密文存储的同时，也能对密文进行的特定计算、统计与检索。但是同态加 密(Homomorphic Encryption，HE)自1978年由Rivest等人提出以来，一直停留在前瞻性的层次上。1984年，Goldwasser和Micali提出过语义安全的同态加密方案，定义了加密的安全性，但是这个加密方法仅仅支持加密字节模2的加法，在全同态加 密方向，并无实质的进展m 2009年，IBM研究员Craig Gentry提出的全同态方案™， 才能够实现对加密数据的充分操作。随后的几年里，各种基于Gentry技术的全同态方案在改进和设计，大大推进了同态密码技术中的全同态加密技术向实际应用领域方面的发展。从目前的各种研究成果来看，如果全同态加密的效率和安全性能够得到保障，那么同态密码技术将会应用到云计算的各个领域，也能够解决部分 云计算中的密文计算和云存储的安全问题。
随着云计算的快速发展，越来越多的企业和个人选择将数据的存储和处理外 包给云端的服务器，由此带来的数据保密和隐私间题也将引起广泛的关注。全同态加密能够实现密文域上的各种运算，在云计算领域有着重要的应用价值。

基础知识

同态与同构

同态加密涉及明文空间与密文空间两个空间的对应操作问题，对应着数学中 的映射，映射就是描述两个元素的对应关系，所以首先从基本的映射开始介绍：
定义2.11 一般地，设A、B是两个集合，如果按某一个确定的对应关系f，使对于集合A中的每一个元素x，在集合B中都有唯一确定的元素y与之对应， 那么就称对应f：A-B为从集合A到集合B的一个映射。
映射可以作为转移代数构造的工具，它可以把一个代数系统所具有的代数性质转移到另外一个非空集合上去。设f(q+x，)=f(q)+f(x)，f(ηz)=f(q)f®,在等式两边都有意义的情况下，这种关系叫做保持运算。保持运算这个关系对 于研究代数系统是非常重要的，它可以把一个代数系统转移到另一个集合上去，同时可以改变一个集合的代数结构。随着研究的不断深入，保持运算这个关系揭示了许多理想的结论。

定义2.12 设G是一个非空集合。如果在G上定义一个代数运算，称为乘法，记作ab(或称为加法，记作a+b)，而且它适合以下条件，那么G称为一个群：

1. 对于G中任意元素a，b，c有：
   a(bc)=(ab)c (结合律)
   2)在G中有一个元素e，它对G中任意元素a有
   ea=a
   3) 对于G中任一元素a都存在a中一元素b使
   ba=e

定义2.13设G与G是两个群。如果有一个G到G的一一对应映射σ，它对于所有x，y∈G有：σ(xy)=σ(x)σ(y)。那么就称G同构于G，记作G≌G’。一一 对应称为G到G’的一个同构映射，简称群同构。

定义2.14设G与G°是两个群，σ是群G到G的一个映射，如果σ适合条件：
σ(xy)=σ(x)σ(y),x,y∈G
那么σ就称为G到G的一个同态映射，或群同态。
显然，同构都是同态，与同构的情形一样，可以证明σ(e)=e’，σ(a^-1
)=σ(a)^-1， 其中e与e分别为群G与G*的单位元素

定义2.15 在同态定义中，对于映射σ：G->G’是映上的，即σG=G`，我们称σ为满同态。如果σ：G-G³是单射，即G与σG同构，也就是G与G°的一个子 群同构，我们就称σ为单同态，或者嵌入映射。
对于同态σ：G-G*，对于任一a’∈G*，我们考虑集合：
{x∈G|σ(x)=a’}
这个集合可能是空集合(当a∈σG)，也可能包含一个以上的元素，我们称这个集合为元素a的完全反象，记为σ^-1(a)。特别地，单位元素的完全反象σ-(e)称为同态σ的核同态σ的核即为kcr(σ)则群同态基本定理可以表达为：设σ：G——>G’ 是一满同态， N为σ的核。于是G/N与G’同构。

定义2.16设非空集合L，定义两个代数运算，一个叫加法，记为a+b，一个 叫乘法，记为ab。具有如下性质：
1)L是加法成一个交换群；
2)乘法结合律： 对于所有的a，b，c∈ L， a(bc)=(ab)c
3)乘法对加法的分配律：对所有的a，b，c∈ L
a(b+c)=ab+ac
(b+c)a=ba+ca
那么L就称为环。

定义2.17 设L与L’是两个环，如果有一个乙到L’的一一对应σ，它具有性质：
1)σ(a+b)=σ(a)+σ(b)
2)σ(ab)=σ(a)σ(b)
其中a,b∈L 那么乙就称为与乙’同构。具有以上性质的映射σ称为一个环同构映射(或简称同构)。

定义2.18 设L，L’是两个环，σ是厶到乙’的一个映射。如果对于所有的 a，b∈L，σ具有性质：
1)σ(a+b)=σ(a)+σ(b);
2)σ(ab)=σ(a)σ(b);
那么σ就称为环L到L’的一个环同态映射(简称环同态)，有时简记为σ：L->L’。
环的同态当然是L的加法群到L’的加法群的同态，因之
σ(0)=0,σ(-a)=-σ(a)
由同态的定义立即看出， σ(L)是L’的一个子环。如果σ(L)={0}，则σ称为零同态；如果σ(L)=L’，则我们说σ是一个满同态，而L’就称为L的一个同态象。
显然，同构是同态的特殊情形。
定理2.11 设σ：R-R’是一个环的满同态，N=kcr(σ), H为R的任一包含 N的理想。则σ诱导出环同构δ：R/H-σ®/σ(H)使得：
σ(x+H)->σ(x)+σ(H)
若将R’与R/N等同使得σ(x)=x+N，则得：
R/H≌(R/N)(H/N) 而且δ：a+H)≯σ(a)+σ(H)是它们的一个同构映射。

同态加密体制的定义

Rivest, Adlcman 和Dertouzos人于1978年在《On Data Banks and Privacy Homomorphisms一文中提出同态加密(Homomorphic cncryption，HE)，这是一种允许直接对密文进行操作的加密变换技术，如果用代数知识来解释的话，把加密过程看作是映射，那么同态加密体制是域上的同态。他们还提出：用求幂函数和RSA函数进行加法隐私同态和乘法隐私同态。虽然，他们的方案已经被证明是不能抗 已知明文攻击的。但是他们却提出了同态加密的描述：
定义2.21Rivest等人对同态加密做了如下定义：s’是和S具有相同基数的另一个集合。D：S*->S是双射。D将作为解密函数。用如下的代数系统来描述对明文的操作：U=<S:f1…fk:p1…pt:s1…sm> 。
这里f1：s^*-s是以g1为参数的函数，p1是以h1为参数的谓词，s1是区分常数。 对U的逆运算可以描述如下：
C=<S:f1…fk:p1…pt:s1…sm>
映射D如果满足如下条件则被称为秘密同态：
(1)(任意i)(1≤i≤k=>(∨(a1……,ak)∈s^*)(存在c∈S)
(f^*(a1…ak)=c=>fi(D(a1)…D(ak))=D©)
2)(任意i)1≤i≤l=>任意(a1…ak)∈s^*)
(p^*1)(a1……ak)=>p1(D(a1)…D(ak)))
3)(任意i)(1≤i≤l=>(任意(a1…ak)∈s^*)
为了将C和D应用到更多的加密机制中，下列附加的限制条件也需要满足：
(1)D和D’是较易计算出的。
(2)C中f^*1和p^*1是能求出的有效值。
(3) D^-1是非扩张密文，且是一个比相应的明文大的能够扩张密文。
(4)在C中的运算和谓词，不能产生有效D运算。
此外，D和D’能够抵抗已知密文攻击和选择明文攻击。这样的一个密码系统
如果存在，它将能够解决云计算环境下的许多问题，被称为全同态加密体制。同态加密早期的构想是用来处理加密数据，现在已经发展为一种云计算环境下的一 种密文计算的准则。

同态加密体制的分类

胡玉璞老师在报告中总结了同态的分类，提出了他的分类方法，即同态可 以分为：单同态，双同态，无限同态和有限同态，这是一个较为概括性的分类方法，加上本人的理解，现把本人的分类方法列出如下：
定义2.31 单同态指仅仅关于明文乘法或加法运算的同态“大数分解”陷门的公钥加密原型和“离散对数”陷门的公钥加密原型都只能实现单同态，且这个单同态是无限的，即任意多个明文的加法运算都对应着密文的乘法运算的解密值。
定理2.31对于密码体制S(E，D，P，C)，x∈P，y∈P，E(x)∈C、E(y)∈C如 果满足： D(E(x)*E(y))=xy
其中，*为密文空间P的任意操作，则该体制s满足乘法同态，若还是单同 态的话，则称该体制是乘同态加密体制。

定理2.32 对于密码体制S(E，D，P，C)，xEP，y∈P， E(x)∈C,E(y)∈C如 果满足： D(E(x)ΦE(y))=x+y
其中，④为密文空间P的任意操作，则该体制s满足加法同态，若还是单同 态的话，则称该体制是加同态加密体制。
定义2.32
双同态指关于明文空间的加法运算和乘法运算都是同态的，且明文 空间必须是一个环。基于一些“译码难题”陷门的公钥加密方案可以实现双同态，
且这个双同态是有限的，即少量明文的环运算是对应密文环运算的解密值。常见
的译码难题包括格上的难题，且陷门的公钥加密方案是带有误差的方案，误差尺 寸在一定限度之内才能被正确解密。

定义2.33 全同态指关于明文空间可以实现任何运算的同态，即对明文空间的任何运算都可以转化为密文空间恰当的运算解密值。无限的双同态密码体制，可 以转化为全同态。
通过对现有的具有同态性质的加密体制进行分析，得出：ElGamal满足乘法同 态、RSA满足乘法同态、Paillicr满足加法同态。
Brcsson 满足加法同态等。

常见密码体制的同态性分析

许多著名的公钥加密算法，如RSA算法，ElGamal算法，Paillier算法等，天然的具有某种同态加密特性，有的具备乘法同态特性，有的具备加法同态特性。本章对这些密码体制的同态性进行了分析，虽然已经有学者对其中的一些进行了分析，但是他们的分析具有一定的局限性，本文对这些分析进行了系统的梳理，提出了自己的分析思路。

RSA密码体制同态性分析

RSA是最熟悉的公钥密码体制,1978年，MIT的3位年轻数学家R。L。Rivcst、A。Shamir和L。Adlcman发明的“RSA是基于Diffie和Hellman所想象的单向陷门函数的定义，而给出的第一个公钥密码的实际实现。非对称加密技术允许在不 安全的媒体上交换信息，也称之为“公开密钥系统”。
RSA加密体制可以描述如下：

选取独立的两个大素数p1和p2(各100~200位十进制数字)，求出： n=p1×p2
	 计算: 
	 φ(n)=(μ1-1)(μ2-1) 
	 随机选一整数e,1≤e≤φ(n)， (φ(n)，e)=1。因而在模φ(n)下，e有逆元 
	 d=e³modφ(n) 
	 取公钥为n，e。密钥为d(p1，p2不再需要，可以销毁) 
	 加密过程：将明文分组，各组在mod n下，可唯一地表示出来(以二元数字表示，选2的最大幂小于n)。各组长达200位十进制数字。可用明文集为： 
	 A,={x:1≤x<n,(x,n)=1}
	 注意，(x，n)≠1是很危险。x∈A的概率： 
	(φ(n)/n)=((p1-1)(p2-1))/(p1·p2)=1-(1/p1)-(1/p2)+(1/p1·p2)——>1
	 密文:y=x^e^mσdn 
	 解密过程：x=y^d^modn 

RSA算法同态性分析：若RSA公私钥为：(N。e)是公钥，(N，d)是私钥，则 明文信息为m，密文信息为e，加密过程为：e≡m(modN)：解密过程为：m≡c^d^(modN)。
	 对于明文m1和m2，，加密后得到： E(m1)≡m1^e^(modN) 
E(m2)≡m2^e^(modN) 有:E(m1)*E(m2)≡m1^e^*m2^e^modN=(m1·m,)modN 
D(E(m1)*E(m,))≡m1*m2, 
	因此，RSA公钥密码体制满足乘法同态特性，又因为RSA不满足加法同态和 其他同态特性，所以RSA是乘法同态密码体制。 
	例子：如果p=5，q=7，n=pq=35，那么可知：φ(n)=(5-1)(7-1)=24,m=6,m,=8d=13,e=13
	c1=6^13^(mod35)=6(mod35)=6,c2=8^13^(mσd35)=8. 
	c1·c2=(m1·m2^13^(mod35)=(6×8)^13^(mod35)=48(mod35)=13, 
	c1·c2=(m1·m2)^13^(mod35),=(6*8)^13^(mod35)=48(mod35)=13
	 c1·c2=(m1·m2)^13^(mod35)
	 所以，该体制乘法同态。 

ElGamal密码体制同态性分析

EIGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K 。

ElGamal密码体制描述如下： 
密钥生成：安全的选取一个大素数p，且要求p-1有大素数因子，找出模p的一个本原元α∈Zp^*^，(Zp^*^是一个有个元素的有限域，是中的非零元构成的乘法群) 。随机生成一个整数a(1<a<p-2)，计算 β=α^a^modp。
公钥：(p,α,β)。私钥：α.
加密过程：选取一个秘密的随机整数x(1<x<p-1)对于明文消息m，计算密文c=(c1·c2)=(α^x^modp，mβ^x^modp)。
解密过程：对于密文c，计算m=c2(c1^a^)^-1^。
ElGamal公钥加解密算法的正确性。
因为：β=α^x^modp,c1=α^x^modp，c2=mβ^x^modp.
所以：c2/c1^a^=mβ^x^α^ax^modp=α^m^/α^ax^modp=mmodp。

ElGamal加密过程需要两次模指数运算和一次模乘运算，解密过程需要模指数运算和模乘积运算各一次(求逆运算忽略不计)。每次加密运算需要选择一个随机数，所以密文既依赖于明文，又依赖于选择的随机数，对于同一个明文，不同的时刻生成的密文不同。另外，ElGamal加密使消息扩散两倍，即密文的长度是对应 明文的两倍。

EIGamal算法同态性分析：对于明文m1，m2，加密后，可以得到： 
E(m1)=(α^x1^modp,m1β^x1^modp),
E(m2)=(α^x²^modp,m2β^x2^modp), 
此时: 
D(E(m1)*E(m2))=D(α^x1+x2^modp,m1m2β^x1+x2^modp) 
=D(α^x1+x2^modp,m1m2β^x1+x2^mod p) =m1m2 
所以,D(E(m,≯E(m))=mm 故El Gamal满足乘法同态特性。又因为El Gamal不满足加法同态和其他同态特性，所以El Gamal是乘法同态密码体制。 例子：确定公共参数：对于p=19，有∠={1,2…,18} α=2是c，的一个本 原根。确定接收方公私钥对：接收方秘密地选择整数a=10，计算： β=α^a^modp=2^10^mod19=17。其中p=19。α=2，β=17是公钥,10是私钥。 
然后进行加密变换，设发送方发送明文m1=11，m2=7，发送方选择两个随机 数x，=7，x，=5，我们计算： 
E(m1)=(α^x1^modp,m1β^x1^modp) 
=(2^7^mod19,11×17^7^mod 19) 
=(14,17)
E(m2)=(α^x2^modp,m1β^x2^modp) 
=(2^5^mod19,11×17^5^mod 19) 
=(13,4)
D(E(m1)·E(m2))=D(α^x1+x2^modp,m1β^x1+x2^modp) 
=D(2^12^mod19,7×11×17^12^mod 19) 
=D(11,11)=7×11
故该ElGamal公钥密码体制示例满足加法同态特性