浮点数据的类复合同态加密机制

浮点数据的类复合同态加密机制

随着信息技术的快速发展，大量计算机数据存储的安全性以及敏感数据的窃取和复制变得越来越重要。数据库系统作为计算机信息系统的核心部件,其安全问题是信息安全领域所要研究的一个重要方面。对于一些重要或敏感数据,用户迫切希望以密文的形式存储和传输,并且可以对数据库信息进行操作但又不泄露其中的内容。数据库加密方法可以应用于不同的环境,但存在一个共同的问题是对于所形成的密文数据库无法进行操作。也就是说,对于密文数据库,若要对某些字段进行统计、平均、求和等数学运算时,必须先对这些字段进行解密运算,然后对明文进行数学运算,之后再加密。这样一来,首先增大了时空开销;其次,在实际应用中,对于某些重要或敏感数据,无法满足用户对其进行操作但又不让用户了解其中的信息的需要。如果能对密文数据库进行数学运算和常规的数据库操作,显然能够解决上面存在的问题,并可以大大削减加/解密所需要的时空开销,提高数据库的运行效率。秘密同态(privatehomomorphism)技术就是一个能解决上述问题的有效方法。1算法的基本思想秘密同态是由Rivest等人于1978年提出的,是允许直接对密文进行操作的加密变换。但是由于其对己知明文攻击是不安全的,后来由Domingo作了进一步的改进。秘密同态技术最早是用于对统计数据进行加密的,由算法的同态性,保证了用户可以对敏感数据进行操作但又不泄露数据信息。秘密同态技术是建立在代数理论之上的,其基本思想如下:设Ek1、Dk2分别代表加、解密函数,明文数据空间中的元素是有限集合{M1,M2,…,Mn},α和β代表运算,若α(Ek1(M1),Ek1(M2),…,Ek1(Mn))=Ek1(β(M1,M2,…,Mn))成立,且Dk2(α(Ek1(M1),Ek1(M2),…,Ek1(Mn)))=β(M1,M2,…,Mn)成立,则称函数族(Ek1,Dk2,α,β)为一个秘密同态。算法实现过程如下:a)选取安全大素数p、q,及由此计算m=pq(m保密)。b)选取安全参数n(根据需要选择适当大小)。c)明文空间T=Zm(小于Z的所有非负整数集合),密文空间T′=(Zp×Zq)n。d)选取两素数rp、rq,分别满足rp∈Zp,rq∈Zq。e)确定加密密钥为K=(p,q,rp,rq)。f)加密算法:设有一明文x∈Zm,随机地将x分为n份:x1,x2,…,xn,并满足xi∈Ζm‚i=(1‚2‚⋯,n)‚x=n∑i=1ximodmxi∈Zm‚i=(1‚2‚⋯,n)‚x=∑i=1nximodm。Ek(x)=(,X2RP2MODP,X2RQ2MODQ,…,XNRPNMODP,XNRQNMODQ)g)解密算法Dk(x):(a)计算(X1RPRP-1MODP,X1RQRQ-1MODQ,X2RP2RP-2MODP,X2RQ2RQ-2MODQ,…,XNRPNRP-NMODP,XNRQNRQ-NMODQ)。其中:rp-n和rq-n分别为rpmodp和rqmodq相应次幂的乘法逆元。(b)计算n∑i=1[ximodp,ximodq]=[n∑i=1ximodp,n∑i=1ximodq]=∑i=1n[ximodp,ximodq]=[∑i=1nximodp,∑i=1nximodq]=XMODP,XMODQ(c)利用中国剩余定理计算Dk(x)=(xqq-1+xpp-1)modm。其中qq-1=1modp,pp-1=1modq。2浮点数的秘密同态加密本文基于秘密同态加密的基本原理,在同态加密机制中提出了类复合同态的概念并应用于浮点数的加密算法中,实现了浮点数的秘密同态加密,使得同态加密机制更具有通用性。2.1同态变换ek定义设σ、τ分别是空间G到H和H到M的同态变换,则σ和τ的复合σ·τ是空间G到M的同态变换。即对于∀x∈G,有同态变换y=σ(x)(y∈H),存在z∈M,z=τ(y)=τ(σ(x))=σ·τ(x)。满足σ·τ(x+y)=σ·τ(x)+σ·τ(y)σ·τ(x×y)=σ·τ(x)×σ·τ(y)基于实际的应用和讨论的方便,假设两次同态变换分别是加密运算Ek1(x)和Ek2(y)。由于引入复合变换的目的是将浮点数转换成整数的形式然后进行加密,定义Ek1(x)是对浮点数进行的加密运算,Ek2(y)仍然采用整数上秘密同态变换的加密机制。2.2浮点数的处理为了保持与原同态运算的一致性,对浮点数到整数的转换也采用类似形式。算法的实现过程如下:a)设明文数据x的小数点位数为k(k为非负整数)。b)将原数据分解为x0,x1,…,xk,使得x×10k=x0×100+x1×101+…+xk×10k。其中xi为正整数。c)定义同态加密变换Ek1(x)=x0×100+x1×101+…+xk×10kd)解密运算Dk1(x)=x/10k,Dk1(x)为浮点数。在浮点数的加、减、乘、除运算中,根据实际的需要设定所有明文数据的最大小数点位数为k(k为非负整数),不够k位的用零补足,定义计算Ek1(M)(M表示运算表达式)时小数位k′的取值由各明文数据k值经基本运算后的所得值决定,则有:a)加和减Ek1(x±y)=Ek1(x)±Ek1(y)为10的i(0≤i≤k)次方项的加减法。b)乘Ek1(x)×Ek1(y)=(x0×100+x1×101+⋯+xk×10k)×(y0×100+y1×101+⋯+yk×10k)=x0y0×100+0+x0y1×100+1+⋯+xiyj×10i+j+⋯+xkyk×10k+k=∑i,jxiyj×10i+j=Ek1(xy)Ek1(x)×Ek1(y)=(x0×100+x1×101+⋯+xk×10k)×(y0×100+y1×101+⋯+yk×10k)=x0y0×100+0+x0y1×100+1+⋯+xiyj×10i+j+⋯+xkyk×10k+k=∑i,jxiyj×10i+j=Ek1(xy)。其中0≤i≤k,0≤j≤k,0≤i+j≤2k。c)除x和y经除法运算后k值消去,则k′取值0,显然有Ek1(x/y)=Ek1(x)/Ek1(y)由上述加减乘除运算可得Ek1(a/b±c/d)=Ek1(a)/Ek1(b)±Ek1(c)/Ek1(d)=/这些运算保证了可以直接对转换后的整数进行操作。将浮点数进行同态加密,即将浮点数明文x经过Ek1(x)同态变换后,转换成一整数的形式,然后再用Ek2(y)(其中y=Ek1(x))进行加密变换。解密运算定义为Dk(x)=Dk1(Dk2(x)),Dk1、Dk2分别为Ek1和Ek2的解密运算。解密过程中首先对Ek1(x)形成的密文数据进行解密,然后再利用Dk1(x)计算得到明文数据。2.3类复合同态加密的步骤类复合同态运算完成的是浮点数的同态加密过程,也是本部分的核心。下面的基本运算包括上面讲述的浮点数到整数的同态转换Ek1(x)以及整数上的同态加密算法Ek2(x)。具体实现过程如下:a)类复合同态的加、减法运算Ek2(Ek1(x))±Ek2(Ek1(y))=Ek2(Ek1(x)±Ek1(y))=Ek2(Ek1(x±y))=Ek2·Ek1(x±y)b)类复合同态的乘法运算Ek2(Ek1(x))×Ek2(Ek1(y))=Ek2(Ek1(x)×Ek1(y))=Ek2(Ek1(xy))=Ek2·Ek1(xy)c)类复合同态的除法运算Ek2(Ek1(x))/Ek2(Ek1(y))=Ek2即对经过类复合同态加密后得到的密文之间的加、减、乘、除运算就相当于对明文进行基本运算后再加密。下面给出两个浮点数加密运算的示例,所用数据有点小,但却能反映出基本的加密过程(为了清楚简便,加密过程中把中间生成的整数分割成两份进行运算)。例1加法运算:设加密密钥p=17,q=13,rp=2,rq=3,明文x1=0.3,x2=-0.1,x3=2。由类复合同态的加密原理,设k=1,则有y1=Ek1(x1)=Ek1(0.3)=3×100=3y2=Ek1(x2)=Ek1(-0.1)=-(1×100)=-1y3=Ek1(x3)=Ek1(2.0)=2×101=20则有z1=Ek2(y1)=Ek2(3)=Ek2(2,1)=(,)z2=Ek2(y2)=Ek2(-1)=Ek2(2,-3)=(,)z3=Ek2(y3)=Ek2(20)=Ek2(12,8)=([7,10],[15,7])z1+z2+z3=(,)+(,)+([7,10],[15,7])=([15,22],[24,28])对计算结果进行解密运算得Dk(z1+z2+z3)=Dk1(Dk2([15,22],[24,28]))=Dk1(22)=2.2例2乘法运算:令加密密钥p=17,q=13,rp=2,rq=3,明文x1=-0.03,x2=0.1。由类复合同态的加密原理,设k=2,则有y1=Ek1(x1)=Ek1(-0.03)=-(3×100)=-3y2=Ek1(x2)=Ek1(0.10)=0×100+1×101=10则有z1=Ek2(y1)=Ek2(-3)=Ek2(1,-4)=(,)z2=Ek2(y2)=Ek2(10)=Ek2(4,6)=([8,12],[7,2])z1×z2=(,)×([8,12],[7,2])=([0,0],[16,36],[22,42],[7,6])对计算结果进行解密运算得Dk(z1×z2)=Dk1(Dk2([0,0],[16,36],[22,42],[7,6]))=Dk1(-30)=-0.0032.4浮点数同态加密将同态加密机制的应用从整数扩展到浮点数范围内,使秘密同态加密算法更具有实用性。加密过程中即使经过Ek1(x)加密转换后得到相同的数据,由于第二次同态加密素数的随机选取和加密数据的随机分割,这样得到的加密数据也是不一样的。浮点数同态加密即在外层加密中保留了原始秘密同态加密的安全性,同时也对原数据进行了双重同态变换,在安全性上只有过之而无不及。由Dominggo-Ferrer等人在文献中的讨论可知,在浮点数上的同态加密机制在安全性方面同样能抵抗仅知密文攻击和已知明文攻击。3字符的编码和存储与整数不同的是,整数加密后能够实现的在密态下的加、减、乘、除运算对于字符串是没有意义的,所以本文通过中国剩余定理将字符串进行转换,然后利用秘密同态算法进行加密处理。具体算法如下:a)设一字符串B,将字符串中的每一个字符取其ASCII码,分别表示为b1,b2,…,bk。其中k是字符串中字符的个数。b)对应取k个两两互素的正整数,设为m1,m2,…,mk(mi≥121)。c)由中国剩余定理得同余式组{x≡b1(modm1)x≡b2(modm2)⋯x≡bk(modmk)⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪x≡b1(modm1)x≡b2(modm2)⋯x≡bk(modmk)d)同余式组的解x≡k∑i=1Μ′iΜibi(modm)(令m=m1m2…mk;Mi=m/mi;M′i=Mi-1modmi;i=1,2,…,k)就是将要加密的整数值。e)根据秘密同态算法解密后可得加密数据x,则由bi=xmodmi可得字符串中每个字符的对应ASCII码值。利用中国剩余定理的证明方法可对字符串与所得加密整数值的对应