云环境下基于随机间隔的保序加密算法

周 雄,李陶深,2,黄汝维,2

(1.广西大学 计算机与电子信息学院,南宁 530004;2.广西高校并行与分布式计算技术重点实验室,南宁 530004)

云环境下基于随机间隔的保序加密算法

周 雄1,李陶深1,2,黄汝维1,2

(1.广西大学 计算机与电子信息学院,南宁 530004;2.广西高校并行与分布式计算技术重点实验室,南宁 530004)

针对隐藏原始数据分布的问题,提出一种改进型的基于随机间隔的保序加密算法(OPERI)。算法首先将原始数据域映射至新的数据域中以达到隐藏原始数据分布和改变数据分布概率的目的,其次通过引入随机间隔对数据进行加密,支持对密文数据的关系运算。安全性分析和实验结果表明:OPERI算法在已有安全性基础上能够抵御统计型攻击,并能高效实现密文关系运算。

保序加密;隐私保护;云计算;统计型攻击

随着云计算的快速发展,人们越来越关注隐私安全问题。目前解决用户隐私安全问题的常用方法是采用加密技术将数据加密后再存储到云端,但是现有的大多数加密方案都不支持对密文的运算,如果对加密数据进行检索、排序,势必会严重妨碍云服务提供商对数据的管理,从而削弱了云计算所带来的优势。文献[1]对各类算法进行分析研究,就现有保序加密算法(Order Preserving Encryption,OPE)不能同时满足高效性和安全性需求的问题,提出一种基于随机树的保序加密算法OPEART,通过引入随机性实现了对数据的加密。虽然OPEART算法较好地解决了密文上的关系运算问题,但是它不能隐藏原始数据分布,加密后的密文与原始数据呈现相同的数据分布,因此不能很好地抵挡统计型攻击。

为了解决隐藏原始数据分布的问题,笔者对OPEART算法进行改进,提出一种基于随机间隔的保序加密算法(OPERI)。该算法首先会通过映射函数将原始数据分布转化为不同类型的分布,然后通过随机分配大小不同的间隔域实现对数据的加密。

1 相关工作

目前有关保序加密方案的研究成果大致分为2类:即密文不变的保序加密方案和密文可变的保序加密方案。

1.1 密文不变的保序加密方案

该类方案的主要思想是:同一加密算法加密同一数据得到的密文是相同的。文献[2]基于多项式函数提出一种OPE方案,该方案利用一系列严格递增的多项式函数来对整数进行加密,密钥是多项式函数的系数,进行多次计算可以得到最终的密文。文献[3]和[4]利用加密函数enc(v)=av+b+vnoise对明文v进行加密,利用噪声vnoise提高其安全性。基于折半查找以及超几何分布和负超几何分布相结合文献[5]、[6]和[7]提出一种保序对称加密算法(OPSE),支持对加密数据的各种关系运算。文献[8]提出一种基于非退化矩阵概念的OPE方案,该方案采用矩阵理论,具有很高的安全性,但是由于构造矩阵的过程复杂,不适于云环境下的大型的数据库系统。文献[9]提出一种基于网格对角线划分原理的OPE方案,该方案首先使用二分搜索确定点的位置,位于对角线上的点的坐标为加密密钥,然后通过线性函数计算得到密文值。文献[10]提出一种将桶划分和树的遍历相结合的OPE方案,经过多次迭代确定每个桶中包含的数据以达到安全性标准。

1.2 密文可变的保序加密方案

云计算环境下的大型数据库系统需要满足数据处理效率性上的需求,如检索时间不能过长、处理过程不能过于复杂;也要满足安全性上的需求,如能够抵挡选择明文攻击(IND-CPA)或者统计型攻击(IND-SA)等。由于保序加密支持密文上的关系运算,能够提高数据检索效率,同时能够达到特定级别的安全性。为此,设计了一个基于随机间隔的保序加密算法,能够满足密文隐藏原始明文的分布,具有保序性,且加解密负载不会随着数据域的变化而变化。

2 系统模型

2.1 系统体系结构

支持隐私保护的云计算体系结构如图1所示,该结构反映了数据拥有者(Data Owner,DO)、用户(Certificate User,CU)和云服务器(Cloud Database Server,CDS)之间的交互,具体过程如下:

1) DO首先通过转换模块对原始数据pi(i∈[1,n],n≥1)进行处理,隐藏其数据分布,得到新的数据分布集di(i∈[1,n],n≥1);

2) 通过加密模块,采用加密算法E对数据di(i∈[1,n],n≥1)加密得到E(di),然后通过安全信道进行传输存储到CDS上;

3) 获得DO授权的CU对请求参数(para)首先经过转换模块得到(para1),然后采用相同的加密算法E加密后得到E(para1),并将E(para1)和计算要求(type)提交给CDS;

4) CDS验证CU的权限后根据CU的计算要求,对其权限范围内的E(di)和请求参数E(para1)进行计算,得到计算结果E(result),并将E(result)返回给CU;

5) CU获得E(result)后通过解密模块进行解密得到中间值tempValue,然后通过还原模块处理,得到最终明文结果result.

图1 支持隐私保护的云计算体系结构

2.2 威胁模型

由于云计算数据外包和服务租赁的特点,DO和CU将数据提交给CDS进行存储和运算,CDS会对DO的数据和CU的计算请求很好奇,通过持续的统计分析获取额外的信息,这种内部攻击是云计算所独有的攻击模型。因此考虑了内部攻击中最常见的统计型攻击(Statistical Attack,SA),即攻击者在获取相关背景信息后,可以从数据拥有者那里获取一些统计信息,然后发动以下攻击:从明文和密文的数据分布中,攻击者可以很容易确定密文的范围。例如给定的属性域“薪水”,假如攻击者知道员工的薪水分布情况，如图2所示,可以在密文上进行统计,试着确认包含5 000到6 000的区间的密文的范围。

图2 薪水-员工数据分布

3 保序加密算法OPERI

本节将设计一个基于随机间隔的保序加密算法(Order-Preserving Encryption based on Random Interval,OPERI),支持对加密数据的任何关系运算。OPERI算法主要分为3个阶段:数据初始化阶段;数据加密、解密阶段;数据还原阶段。首先,OPERI算法将原始数据D进行划分,然后通过映射函数映射到一个范围更大的空间C上,来达到隐藏数据分布和改变数据分布概率的目的。其次,算法根据空间C的大小和密钥key计算获得值域V={vmin,vmax}和初始间隔interval,然后将值域V平分为vnum份,对初始间隔随机分为大小不同的m份,重新计算vmin,vmax的值,每次迭代都会改变值域V的大小,进行vlevel次迭代后,可将密文值确定在一个区间{xminx,xmaxx}内。最后,算法利用随机数确定密文值的大小。

OPERI算法由以下4个算法过程组成。

3.1 初始化Init

初始化算法Init描述为:

Init:{tmin,tmax,v}←Init(mmin,mmax,m)

其中,mmin,mmax定义了原始数据的定义域D,通过处理后得到中间值C定义域为{tmin,tmax},原始明文m处理后得到v.

对于明文空间D,划分成一系列的区间Di=[li,ri] (i=1,2,…,m) .由于D通常是离散的空间,所以设定li,ri∈z,满足:

(1)

划分明文空间可以有效地破坏数据的分布规律:即对于一个数据集,数值越多,划分的区间数就越多。

对于扩展空间C,划分相等个数的区间Ci=[li’,ri’](i=1,2,…,m),设定li’,ri’满足:

(2)

给定一个原始明文区间Di,相对应的扩展空间区间为Ci,还能得知Mi(li)=li’,Mi(ri)=ri’.同样划分扩展空间可以有效破坏数据的分布规律:即在Di中包含的数据越多,对应的Ci的范围也就越大。

映射函数M满足以下条件:M是可解的,对于∀x∈Di,扩展空间值Mi(x)是很容易通过编程计算的。而且如果yi=Mi(xi),那么相对应的xi=Mi-1(yi)也很容易求出。为了实现可编程化,第i个区间边界值和x∈Di作为输入,输出结果yi∈Ci.最简单的过程如下所示:

计算比例因子vscale=(ri’-li’)/(ri-li);

映射x到扩展空间,y=li’+vscale(x-li’);

通过以上计算,原始明文空间D映射到扩展空间C中,从而能够隐藏原始数据的分布以及改变数据分布概率

3.2 加密算法Enc

加密算法Enc描述如下:对于数据v∈C,c←Enc(vmin,vmax,vinterval,vlevel,vnum,vkey,v)且c∈V.其中,vkey表示密钥;vmin,vmax定义了OPERI算法的最小值和最大值;vinterval为初始间隔域大小,vlevel是处理间隔域的层数;vnum定义了值域分割的数量。Enc算法的过程描述如下:

算法1.加密算法Enc

输入:值域最小值vmin,值域最大值vmax,初始间隔域vinterval,计算次数vlevel,处理间隔域层数vlevel,密钥vkey,值域平分个数vnum,扩展区间明文值v

输出:密文值c

1:procedure Enc(vmin,vmax,vinterval,vlevel,vnum,vkey,v)

2:t← (vmax-vmin)/vnum;

3:tt←vinterval;

4: fori=1 tovlevel

5: splitList←v

6: ranList←random.next();

7: borderList←border;

8: end for

9: fori=0 tovlevel

10:vmin=vmin+t-splitList[i]+tt-borderList[i];

11: if split[i]==borderList[i][0]

12:vmax=vmin+t-ranList[i]+tt-(borderList[i][1]-

borderList[i-1][1]);

13: elsevmax=vmin+t-ranList[i];

14:tt=t-(1-ranList[i]);

15: end for

16:c=vmin+(vmax-vmin)-random(vkey+v);

17: end procedure

3.3 解密算法Dec

解密算法Dec描述如下:对于密文c∈V,v∪φ←Dec(vmin,vmax,vinterval,vlevel,vnum,vkey,c),φ表示无解。Dec算法的具体过程描述如下:

算法2.解密算法Dec

输入:值域最小值vmin,值域最大值vmax,初始间隔域vinterval,处理间隔域层数vlevel,值域平分个数vnum,密钥vkey,密文c

输出:扩展空间明文值v

1:procedure Dec(vmin,vmax,vinterval,vlevel,vnum,vkey,c)

2:t← (vmax-vmin)/vnum;

3:tt←vinterval;

4: fori=1tovlevel

5:

6:r=random(vkey+x);

8: ifx==xivmax=vmin+t—r+tt—random(vkey+xj);

9: elsevmax=vmin+t—r;

10:tt=t·(1-r);

11:v=v+x;

12: end for

13:end procedure

3.4 还原算法Restore

还原算法Restore描述如下:对于v∈C,m←Restore(tmin,tmax,v),经计算后可得到最终结果m且m∈D。算法的具体过程描述如下:

算法3.还原算法Restore

输入:扩展区间值域最小值tmin,扩展区间值域最大值tmax,扩张空间明文值v

输出:原始明文值m

1:procedure Restore(tmin,tmax,v)

2:vscale← (tmin,tmax);

3:m=(v-tmin)/vscale+tmin;

4: end procedure

4 安全性分析

定义1 一个加密算法E在统计型攻击(SA)下是安全的,如果攻击者ξ发起以下攻击:原始数据各个区间的分布概率都不相等的情况下,假设p(x∈D1)>p(x∈D2)>…>p(x∈Dm),ξ在进行多次查询后,得到的密文分布概率p(x∈C1),p(x∈C2),…,p(x∈Cm),通过统计分析,ξ根据明文数据分布做出猜测有p(x∈C1)>p(x∈C2)>…>p(x∈Cm) .

ξ的优势概率定义为:Adv(ξ)=|p(x∈Ci-p(x∈Cj)|=ε,(i,j∈[1,m]且i≠j),如果 足够小,则E在统计型攻击下是安全的。

定义2 如果一个数x∈Di,Di表示一个区间,p(x∈Di)=|Di|/L(Di),其中L(Di)为Di的宽度,|Di|为Di中包含的元素个数。

定理1 OPERI算法在统计型攻击(SA)下是安全的。

证明 在数据初始化过程中,OPERI算法通过划分映射等操作,可以隐藏原始数据的分布并且改变数据分布概率。根据定义2得知,如果在未进行空间扩展的情况下,密文分布明文分布相同。由于有p(x∈D1)>p(x∈D2)>…>p(x∈Dm),则有p(x∈C1)>p(x∈C2)>…>p(x∈Cm) .在进行了空间扩展后,原始数据空间D划分为多个大小不等的区间Di,同样扩展空间C也会被分为相同数量的区间Ci,通过映射函数M使得Ci=M(Di),Ci区间的大小根据Di中的元素个数来定。假设明文区间中的任意两个子区间Di,Dj,元素个数分别为s,t,那么映射区间Ci,Cj大小为s-g,t-g(g为设定的单位距离)。最后通过计算获得的密文值区间x∈C1,x∈C2,…,x∈Cm会呈现出近线性分布y=k·x+b那么对于任意两个区间Di,Dj中的元素有p(x∈Di)=|Di|/L(Di)=s/(s-g)=1/g以及p(x∈Di)=|Di|/L(Di)=t/(t-g)=1/g.

同理可以推出p(x∈C1)≈p(x∈C2)≈… ≈p(x∈Cm),即有|p(x∈Ci-p(x∈Cj)|=ε,(i,j∈[1,m]且i≠j),其中任意小,因此OPERI算法在统计型攻击下是安全的。证毕。

5 实验

通过实验对OPERI算法与文献[1]提出的OPEART算法进行比较。实验部署在云翼实验平台上,该平台是一个基于Web的面向学生的云计算环境,以KVM和Swift为基础,并部署在由12台服务器构成的集群上。

5.1 数据分布

实验1比较通过OPERI与OPEART加密后的数据分布。为了让实验的结果更具有对比性,实验选取两组原始分布具有特征性的数据,第一组是成对数分布的y=log1.2(x),为使数据分布更广泛,将x的范围定义在[1,10 000]内,得到y后再乘以10 000取整;第二组是成指数分布的y=1.01x,实验选取的x值范围是[1,1 000],得到y后再乘以10 000取整。

第一组数据的原始分布以及加密后的分布图如图3所示。

图3 第一组数据的实验结果

第二组数据的原始分布以及加密后的分布图如图4所示。

图4 第二组数据的实验结果

通过图3和图4的实验比较结果可以看出,经过OPEART算法加密后的数据与原始数据呈现相同的分布,而通过OPERI算法加密后的数据呈近线性分布,并不与原始数据分布相同。实验1的结果表明,OPERI算法比OPEART算法更能隐藏原始数据的分布特征,具有更高的安全性。

5.2 数据分布概率

实验2是比较通过OPERI和OPEART加密后的数据分布概率,实验选取图2对应的薪水-员工数据,实验对比结果如图5所示。

图5 数据分布概率的实验对比结果

由图5的对比结果可以看出,通过OPEART算法加密后,数据与原始数据具有相同的数据分布概率,在5 000～6 000范围的数据分布概率明显大于其他区间数据的概率,而通过OPERI算法加密后,数据的整体分布概率基本相同,很好地达到了隐藏数据分布概率的目的。

5.3 OPERI算法的效率

实验3比较了OPERI算法与OPEART算法在加解密、范围检索两方面的性能。其中,OPERI算法与OPEART算法选择相同的参数vlevel=7,vnum=99,实验结果如图6、图7所示。

图6 加解密时间对比

图7 检索时间对比

由图6可以看出,OPERI算法的加密和解密负载几乎是一样的,相比OPEART算法加解密时间也是呈线性增长。由图7可以看出,在进行范围检索时,OPERI算法与OPEART算法在时间上都是呈线性增长。性能上相差不大。

综合实验结果来看,OPERI算法能够隐藏原始数据分布,具有更高的安全性,而且在加解密以及检索性能上与OPEART算法相差不大。

6 应用场景

在实际的云环境中,应用本文的OPERI算法可以进行以下这些操作:

1) 比较运算。假如需要求出某个区间[xm,xn]内的数据,首先将原始数据排好序得到x1

2) 字符串精确匹配。字符串是由一个个的字符构成,由于不同的字母对应的ASCII码值不同,而且大小按照字母表顺序排列,比如a对应的ASCII码值为97,b对应的码值为98,有a

3) 字符串模糊匹配。假如需要查找字符串abcde,经过2)中的字符串精确匹配后发现没有完全匹配的字符串,但是有相近的字符串abcee、abcfe和abcge,由于OPERI算法能计算得出e与d的距离相比于f与d和g与d的距离更近,所以最终会选择将abcee的密文返回给用户,然后用户进行解密得到距离abcde最近的明文值abcee.这种模糊匹配不同于用编辑距离查找模糊字符串的做法,它是返回距离指定字符串最近的明文值。

7 结论

对OPEART算法进行改进,提出了一种OPERI算法。改进的算法首先利用线性表达式将原始明文空间映射至扩展空间,从而能够隐藏原始数据的分布以及改变数据分布概率;其次将扩展空间的数据作为加密算法的输入,通过引入随机间隔,每经过一轮计算,密文所在的数据域的范围会被缩小;最后通过随机数确定密文的值。安全性分析和实验结果证明了OPERI算法在原有安全性的基础上能够抵挡统计型攻击,并且具有很高的运行效率,能够抵挡统计型攻击。

[1] Huang Ruwei,Gui Xiaolin,Chen Ningjiang.An encryption algorithm supporting relational calculations in cloud computing[J].Journal of Software,2015,26(5):1181-1195.

[2] Ozsoyoglu G,Singer D A,Chung S S.Anti tamper databases:querying encrypted databases[C]∥Proceeding of the 17th Annual IFIP WG 11.3 Working Conference on Database and Applications Security.GA,USA,2003:1-19

[3] Liu D,Wang S.Nonlinear order preserving index for encrypted database query in service cloud environments[J].Concurrency and Computation:Practice and Experience,2013:1967-1984.

[4] Liu D,Wang S.Programmable order-preserving secure index for encrypted database query[C]∥2012 IEEE Fifth International Conference on Cloud Computing.Hawaii,USA,2012:502-509.

[5] Boldyreva A,Chenette N,Lee Y,et al.Order-preserving symmetric encryption[J].Advances in Cryptology-EUROCRYPT,2009:224-241.

[6] Boldyreva A,Chenette N,O’Neil A.Order-Preserving encryption revisited:improved security analysis and alternative solutions[C]∥Proceedings of the 31st annual conference on Advances in Cryptology.Berlin,Heidelberg,2011:578-595.

[7] Mohammad A,Ashkan P,Marinescu D C.Security of applications involving multiple organizations-order preserving encryption in hybrid cloud environments[C]∥2014 IEEE 28th International Parallel & Distributed Processing Symposium Workshops.Phoenix (Arizona),USA,2014:894-903.

[8] Krendelev S F,Yakovlev M,Usoltseva M.Order-preserving encryption schemes based on arithmetic coding and matrices[C]∥Proceedings of the 2014 Federated Conference on Computer Science and Information Systems.Warsaw,Poland,2014:891-899.

[9] Martinez S,Miret J M,Tomas R,et al.Securing databases by using diagonal-based order preserving symmetric encryption[J].Applied Mathematics & Information Sciences,2014,8(5):2085-2094.

[10] Fang Q,Wilfred Ng,Feng J,et al.Mining bucket order-preserving submatrices in gene expression data[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(12):2218-2231.

[11] Bebek G.Anti-tamper database research:inference control techniques[R].Technical Report EECS 433 Final Report,Case Western Reserve University,2002.

[12] Popa R A,Li F H,Zeldovich N.An ideal-security protocol for order-preserving encoding[C]∥2013 IEEE symposium on Security and Privacy.San Francisco,CA,USA,2013:463-477.

[13] Reddy K S,Ramachandram S.A Novel dynamic order-preserving encryption scheme[C]∥2014 First International Conference on Networks & Soft Computing (ICNSC).Andhra Pradesh,India,2014:92-96.

[14] Liu Zheli,Chen Xiaofeng,Yang Jun,et al.New order preserving encryption model for outsourced database in cloud environments[J].Journal of Network and Computer Applications,2014,(7):1-10.

(编辑：刘笑达)

Order-Preserving Encryption Algorithm based on RandomInterval in Cloud Environments

ZHOU Xiong1,LI Taoshen1,2,HUANG Ruwei1,2

(1.SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,Nanning530004,China；2.GuangxiCollegesandUniversitiesKeyLaboratoryofParallelandDistributedComputing,Nanning530004,China)

With the further development of Cloud Computing,people are more concerned for data privacy.Encryption is an effective way to protect data privacy.But it makes data inoperable and most of them can not hide data distribution.To solve the problem of hiding original data distribution,modified order-preserving encryption algorithm based on random interval in cloud environment (OPERI) is proposed in this paper.Firstly,original data are be mapped to new data domain in order to hide the data distribution of original data and change the data probability.Then,random interval is introduced to encrypt the data,which can suppert relational calculations on ciphertexts.Security analysis and experiment results show that OPERI algorithm can resist the statistical attack on the original security and it is efficient to realize relational calculations on ciphertexts.

order preserving encryption;privacy protect;cloud computing;statistical attack

1007-9432(2015)06-0741-08

2015-05-10

国家自然科学基金资助项目:无线Mesh网络中基于定向天线的关键技术研究(61363067),广西自然科学基金项目(2012GXNSFAA053222)，广西教育厅科研基金项目(2013YB007)资助

周雄(1990-),男，湖北武穴人，硕士生，主要从事网络计算与信息安全研究，(Tel)13768301390

李陶深，湖北武穴人，博士，教授，主要从事分布式数据库系统、无线mesh网络、云计算研究。

TP309

A

10.16355/j.cnki.issn1007-9432tyut.2015.06.019