摘 要:  随着云计算的深入发展,隐私安全成为云安全的一个关键问题.加密是一种常用的保护敏感数据的方法,但是它不支持有效的数据操作.为了提供云计算环境中的隐私保护,设计了一种随机数据结构——随机树,并构建了基于随机树的保序加密算法OPEART(order-preserving encryption based on random tree).OPEART通过引入随机性实现了对数据的加密,并支持加密数据的任何关系运算(>,<,>=等).安全分析和性能评估表明:OPEART 是 IND-DNCPA(indistinguishability under distinct and neighbouring chosen plaintext attack)安全的,并能高效地实现对加密数据的关系运算.

关键词:  云计算;隐私安全;保序加密;关系运算

云计算作为一种新型的网络计算模式,以一种比传统 IT 更经济的方式向用户提供按需的 IT 服务(计算、 存储和应用等).由于云计算的发展理念符合当前低碳经济与绿色计算的总体趋势,它得到了世界各国政府和企业的大力倡导与推动,正带来计算领域和商业领域的巨大变革.但在已经实现的云计算服务中,隐私安全问题一直令人担忧,并已经成为阻碍云计算发展和推广的主要因素之一.用户的隐私数据包括可用来识别或定位个人的信息(例如电话号码、地址和信用卡号等)、敏感的信息(例如个人的健康状况、财务信息、公司的重要文件等).

云计算的隐私安全问题源于云计算的数据外包和服务租赁的特点.用户数据存储到云环境中,人们失去了对数据的直接控制力,可能会导致个人隐私数据的泄露和滥用.而近年来发生的 Google,MediaMax 和 Salesforce.com 等云服务商泄露或丢失用户数据的事实证实了人们的担心 [1] .加密是一种常用的保护用户隐私数据的方法,但目前的大多数加密方案都不支持对密文的运算,如对加密的数据进行检索、 对加密的公司财务信息进行排序等统计分析,因而严重妨碍了云服务商为用户提供更进一步的数据管理和运算服务,从而削弱了云计算的优势.

针对上述问题,本文提出一种基于随机树的保序加密算法OPEART(order-preserving encryption algorithm based on random tree).OPEART 通过树状结构组织数据,同时,通过随机地为树中节点分配大小不同的区域实现对数据的加密.该算法支持对加密数据的任何关系运算(==,>,<,<=,>=等),特别适用于云计算环境中的大型数据库,方便建立索引和快速检索.本文第 1 节回顾相关研究的进展情况.第 2 节建立支持隐私保护的网络计算模型和攻击模型.第 3 节定义OPEART 并介绍其具体实现.第 4 节和第 5 节分别就 OPEART 的安全性和性能进行评估.第 6 节做出总结.

1 相关工作

对于加密数据的关系运算问题,目前已有一些研究成果,可以大致分为以下几类:(1) 支持精确匹配的加密算法;(2) 保序的最小完美哈希函数;(3) 保序的加密算法;(4) 不保序的加密算法;(5) 借助索引的方法.(1) 支持精确匹配的加密算法Song 等人 [2] 提出了基于对称加密和数据异或运算的加密关键字检索算法;Boneh 等人 [3] 提出了基于双线性映射的加密关键字检索算法PEKS;Ohtaki等人 [4] 使用BloomFilter来存储关键字的各种布尔组合信息,从而实现了支持逻辑运算的密文检索;Liu 等人 [5] 提出了基于双线性映射的加密关键字检索算法 EPPKS,它是在 PEKS 的基础上增加了对外包数据(而不仅仅是外包数据的关键字)的加密部分,并让服务提供者参与了一部分解密工作,减轻了用户的计算负载.以上算法都只支持关系运算中的“==”比较,功能较为单一,不能完全解决云计算环境中对密文数据的关系运算问题.(2) 保序的最小完美哈希函数假设一个集合 S 有 m 个关键字,一个有 n 个桶的哈希函数 h 是保序的最小完美哈希函数需满足:i)  h:Sn 是单射函数;ii)  m=n;iii)  如果 x<y,那么 h(x)<h(y).Belazzougui 等人 [6] 通过建立相关分级树和前缀匹配的方法实现了一个单调变化的最小完美哈希函数,该函数没有隐藏原数据的值,而是把该数据映射到与该值相近的桶中.

Czech 等人 [7,8] 通过以两个任意函数的函数值作为顶点构造带权无环图实现了一个保序的最小完美哈希函数,该函数能够很好地隐藏原数据的值,但是要构造一个无环图可能需要多次尝试.以上的哈希函数都是针对静态数据域的,计算复杂度随着数据域中元素个数的增加而增长,当数据域很大或者动态变化时,保序的最小完美哈希函数的方法是不适用的.另外,要用哈希函数来实现对数据的加解密运算,需要保存一份映射表,这无疑增加了数据拥有者的存储负载.(3) 保序的加密算法Agrawal 等人 [9] 基于桶划分和分布概率映射的思想提出了一种保序对称加密算法 OPES,支持对加密数值数据的各种关系运算,其不足是:当定义域较大时,桶划分的计算负载较大;而且面对已知明文的攻击时,当输入分布的桶与对应的输出分布的桶中点的个数足够多时,可以通过解方程的方式破解.Boldyreva 等人 [10,11] 提出了一种基于折半查找和超几何概率分布的保序对称加密算法 OPSE,支持对加密数据的各种关系运算,但由于在计算超几何概率时需要进行多次组合运算,其计算负载较大.以上两种保序的加密方法的优点是保序性,即,密文反映了明文的大小关系,从而方便服务提供者对密文数据建立索引,加快查找速度,并易于实现各种关系运算;不足是,它们都不能同时满足高效性和安全性的要求. (4) 不保序的加密算法Wong 等人 [12] 设计了一个基于向量标量积的对称加密方案,该方案支持对加密数据库进行 KNN(k-nearestneighbor)计算,具有 IND-CCA 安全性,其不足是:i)  只能对对象之间的距离进行比较,并不支持两对象本身的比较;ii)  由于该算法是 IND-CCA 安全的,数据加密后具有不确定性和不保序性,因此要找到满足条件的数据,必须搜索整个数据库,这对于大型数据库来说是不现实的.

Boneh 等人 [13,14] 基于双线性映射理论实现了支持关系运算检索的加密方案,它们的优点是具有 IND-CCA安全性,缺点是:i)  计算复杂度高;ii)  数据加密后具有不确定性和不保序性,服务提供者必须对表中的所有数据进行遍历才能找到符合条件的数据,效率很低.Shi 等人 [15] 提出了一个 Interval tree 的概念,并基于双线性映射原理实现了支持关系运算检索的加密方案.该方案的优点是 IND-CCA 安全的,缺点是:i)  Interval tree 只能定义在静态数据域上;ii)  计算复杂度高;iii)  SP 必须对表中的所有数据进行遍历才能找到符合条件的数据.通过以上分析可知,不保序的加密算法的优点是安全性高(IND-CCA),缺点是:i)  计算负载大;ii)  要对整个表进行遍历才能找到满足要求的所有数据,这对于大型数据库来说是不现实的.(5) 借助索引的方法Wang 等人 [16] 针对 XML 数据库提出了一个安全的加密方案:i)  采用任意一种确定的对称加密算法加密外包数据;ii)  为了快速定位,构建可用于结构检索的结构索引和可用于数值比较的值索引.该方案的不足是:i)  需要服务提供者开辟额外的存储空间存放索引,且当数据发生变化时,数据拥有者要重新建立索引;ii)  在建立值索引时采用了保序的加密算法,因此具有这类算法的不足.Hacıgümüş 等人 [17] 将关系数据库中表的属性分为 5 类,并采用不同的加密方式:i)  对于需要进行聚合型运算(SUM,AVG)的属性,采用隐私同态方案 [18] 加密;ii)  对于需要进行精确匹配的属性,采用确定的对称加密算法来加密;iii)  对于需要进行关系运算的属性,建立一个粗粒度的索引,将整个数据域分为若干段,每一段给一个编号,用编号来代替实际的属性值;iv)  对于不会被单独访问的属性,对整个对象进行加密.该方案中采用的粗粒度索引不能真正实现关系运算.Wang 等人 [19] 通过建立索引实现了查找与关键字最相关(例如出现频率)的 k 个文件的功能,其索引主要包括用哈希函数加密的关键字和用任意一种对称加密算法加密的,包含该关键的文件编号和相关度,其中,为了隐藏真实的相关度,先用改进的 OPSE 对相关度进行了加密.

该方法有以下不足:i)  建立索引时需要对包含某个关键字的文件进行扫描,从而得到与该关键字相关的信息,例如出现频率,这增加了用户的计算负担;ii)  索引占用了服务提供者额外的存储空间;iii)  当增加或删除与某个关键字相关的文件时,用户必须重新设置并加密索引,这是非常麻烦的事.以上方法都是借助索引来实现支持关系运算的检索,需要数据拥有者自己建立并维护索引,这增加了数据拥有者的负担,同时也占有了服务提供者额外的存储空间. 针对云计算环境中的大型数据库系统,我们权衡了以上加密算法的利弊,就已有的保序加密算法不能同时满足高效性和安全性的要求,设计了一种随机数据结构——随机树,并构建了基于随机树的保序加密算法OPEART(order-preserving encryption based on random tree),能够满足:(1)  具有保序性,从而支持大规模数据库的快速检索,并支持各种关系运算;(2)  安全性介于已有的保序加密算法和不保序的加密算法之间,即 IND-DNCPA 安全性;(3)  不需要事先建立额外的索引,减轻 Owner 的计算和存储负担;(4)  负载不会随着数据域的变化而变化.

2 问题描述

2.1 支持隐私保护的云计算模型如图 1 所示,支持隐私保护的云计算模型反映了数据拥有者(owner)、用户(user)和服务提供者(serviceprovider,简称 SP)之间的交互,具体过程如下:(1)  Owner 用加密算法 E 对敏感数据 d i (i[1,n],n≥1)加密,得到 E(d i ),然后存储到 SP 的服务器上;(2)  User 获得 Owner 的授权后,对敏感计算参数(para)加密,得到 E(para),并将 E(para)和计算要求(type)提交给 SP;(3)  SP 验证 User 的权限,然后根据 User 的计算要求,对其权限范围的 E(d i )和计算参数 E(para)进行计算,得到计算结果 E(result),并将 E(result)返回给 User;(4)  User 对 E(result)进行解密,得到结果的明文 result.Fig.1 Privacy-Preserving calculation model of cloud图 1 支持隐私保护的云计算模型在这个过程中,由于 Owner 和 User 分别对敏感的外包数据和计算参数进行了加密处理,使得 Owner 和 User的隐私得到了很好的保护.但同时也带来了一个新的问题:SP 如何对加密的数据进行计算呢?如果这个问题不能得到有效的解决,Owner 和 User 就不能利用云计算中的计算资源对敏感数据进行处理,从而削弱了云计算的优势.因此,本文提出的支持关系运算的加密算法是解决这一矛盾的关键技术之一.

2.2 威胁模型根据图 1 可知,在用户交换的过程中可能存在以下几种隐私攻击:(1)  数据从 Owner 传递到 SP 的过程中,外部攻击者可以通过窃听等方式盗取数据;(2)  外部攻击者可以通过无授权的访问、木马和钓鱼软件来攻击 SP 从而获取数据; (3)  Owner 和 User 将数据提交给 SP 进行存储和运算,SP(内部攻击者)能够获得数据,因此,SP 要发起攻击(例如盗取、泄露数据、私自分析和统计数据等)更为容易.在以上的 3 种攻击中,第(1)种和第(2)种是传统网络安全中涉及的问题;第(3)种是在云计算模式下出现的新的攻击形式,也是破坏性最大的一种隐私威胁.因此,我们设计的加密算法主要针对第 3 类攻击,同时能够有效地防御前两种攻击.

3 基于随机树的保序的加密算法 OPEART(order-preserving encryption algorithm based onrandom tree)

3.1 OPEART定义本节将构造一种基于随机树的保序加密算法 OPEART.OPEART 在确保 Owner 和 User 数据安全的前提下,支持对加密数据进行任何关系运算.

定义 1(保序的加密算法). 假设加密算法 E 的定义域为 D,E 是保序的加密算法,满足:如果 x 1 >x 2 (x 1 ,x 2 D),那么 E(x 1 )>E(x 2 ).

定义 2(随机树). 随机树(random tree,简称 RT)是一棵多叉树,树中每个节点都对应定义域中的一点,并占据值域中的一段区间;树中的子节点区间是对父节点区间的一种随机划分,如图 2 所示.RT 的定义域为 D=[0,410 12 ],值域为V且V的大小|V|[10 16 ,2 64 ](2 64 为long类型的取值范围大小),RT=(Gen,Div)由以下两种算法组成:(1)  RT 生成算法 Gen:{min,max,level,num}Gen(|V|,key),其中,key 表示用户的密钥;|V|表示值域的大小;min 和 max 定义了 RT 的针对 key 的值域 V=[min,max],且 min=|V|(1) (key mod 2) random(key),max=min+|V|,其中,random(key)(0,1);level 表示树的高度;num 定义了每个节点的子节点的数量,满足:num level ≥|D|;(2)  区间划分算法 :ixno D de iv (iZ 且 i[1,num])}Div(node x ,key,i),其中,  node x 是当前待划分区间的节点,它的 4 个属性分别是:node x .value 表示该节点对应的明文值,node x .level 表示该节点处于 RT 中的层数,node x .min 和 node x .max分别表示其区间的最小值和最大值;  i 是待求子节点ixnode 的编号,即,ixnode 是 node x 的第 i 个子节点.如图 2 所示,随机树首先将整个值域 V=[min,max]根据密钥 key 分为值域 vf 0 和间隔域 gf 0 两部分,然后对 vf 0按照子节点的个数平均分为 num 份,再根据 key 将 gf 0 分为大小不等的 m(mZ 且 m≤num)份,并分给随机选择的 m 个子节点,每一层按照以上原理依次往下分裂.除 L=0 层外,以下各层分配的值域、间隔域大小以及间隔域的分裂份数和选择哪些子节点由 key 和该节点本身代表的值共同决定.

定义 3(OPEART). 设 OPEART 的定义域为 D,值域为 V,OPEART=(Gen_RT,Enc,Dec)由以下 3 种算法组成:(1)  RT 生成算法 Gen_RT:RTGen(|V|,key),其中,key 表示用户的密钥;(2)  确定的加密算法 Enc:mD,cEnc(RT,key,m)且 cV;(3)  确定的解密算法 Dec:对于密文 c,m/Dec(RT,key,c),表示无解.

定义 4(IND-DNCPA). 一种加密算法 E 是 IND-DNCPA(indistinguishability under distinct and neighbouringchosen plaintext attack)安全的,如果攻击者 A 发起以下攻击:(1)  A 选择一组明文 M={x 1 ,x 2 ,…,x k }(x i D,x i x j 且 i,j[1,k])向 E 进行加密询问,E 将加密的结果 C={c 1 ,c 2 ,…,c k }返回给 A,A 不能通过(x i ,c i )(i[1,k])解出其他密文 c(cC)对应的明文;(2)  A 选择两个数据 m 0 ,m 1 发给 E,其中 m 1 =m 0 +1,且 m 0 M,m 1 M;(3)  E 随机加密其中一个数据 m b (b{0,1}),并将产生的密文 c b 返回给 A;(4)  A 输出 b作为对 b 的猜测.A 的优势概率定义为定义5(随机性强度). OPEART基于随机树和用户的密钥为定义域中的每个点分配了大小不等的密文区间,从而实现了对数据的加密,其随机性强度通过以下两个参数来衡量:(1) 值参数(parameter of value,简称 pv):假设任取连续的k个点{x 1 ,x 2 ,…,x k }(x i D,i[1,k],k≥2),定义平均距离d=(Enc(x k )Enc(x 1 ))/(k1),点x的参照值可以通过函数 f(x)=Enc(x 1 )+(xx 1 )d 计算得到,则有:2 21| ( ) ( ) |ki iikpvEnc x f x(1)pv反映了OPEART产生的密文与参考值的差距大小,变化越大,pv的值越小,攻击者通过密文猜测明文就越困难.(2) 值变化参数(parameter of value change,简称 pvc):假设任取连续的 k 个点{x 1 ,x 2 ,…,x k }(x i D,i[1,k],k≥2),平均距离为 d=(Enc(x k )Enc(x 1 ))/(k1),用 d=(Enc(x i )Enc(x i1 ))(i[2,k])来表示相邻两点间密文值的差距.假设 OPEAT 的值域为 V,其中共有 n 个点,则 d[1,Vn].下面将 d的取值范围[1,Vn]分为 5 个区间,每个区间赋予一个权值:(0,d/2)的权值为 1,(d/2,d)的权值为2,(d,d3/2)的权值为 3,(d3/2,2d)的权值为 4,(2d,Vn)的权值为 5.假设在以上的 k 个点对应的密文值的差距中,在以上 5 个区间中的比例分别为(p 1 ,p 2 ,p 3 ,p 4 ,p 5 ),下面定义值变化参数 pvc 如下:当 p i 0(i[1,5])时,pvc=p 1 +p 2 2+p 3 3+p 4 4+p 5 5  (2)由于平均距离为 d,所以平均值变化参数 pvc avg 为pvc avg =2  (3)最大值变化参数 pvc max 可通过下面的方程组求出:1 2 3 4 51 2 3 4 513 3 50 2 22 2 2 2 22 2 2 2 2p p p p pd d d d dd d d dp p p p p d                                                                          解方程(4)可得:pvc max =2.5  (5)因此,当 pvc=pvc max 时,密文值之间的差距变化最大.注意,为了方便计算,方程(4)假设第 5 区间的范围为(2d,5d/2],因此 pvc max =2.5;当实际的连续密文距离超过 5d/2 时,pvc max >2.5.这对安全性分析没有影响.

3.2 算法描述

本节先对RT的区域划分算法Div()进行描述,再对OPEART的加密算法Enc()和解密算法Dec()进行描述.1) Div()算法用于求出 node x 的第 i 个子节点ixnode 的区间范围.其原理是:将节点 node x 的区间[node x .min,node x .max]随机地分为值域 vf 和间隔域 gf 两部分,其中,vf 部分被均匀的划分为 num 份;而 gf 部分则使用密钥key 和本节点对应的值作为随机运算的种子,随机地划分为 m(mZ 且 m≤num)份并分给随机选择的 m 个子节点,第 j 份表示为 gf j ,其中的第 j 个子节点的区间大小(node x .maxnode x .min)/num+gf j .

算法 1. RT 的区域划分算法 Div().输入:待划分区域的节点 node x 、密钥 key、待求子节点的编号 i.1:  min=node x .min; max=node x .max;2:  If node x .level==0 then3:  ran_root=key;  //产生随机数的种子4:  Else5:  ran_root=key+node x .value;6:  End If7:  根据 ran_root 分割数据域(min,max)产生值域 vf 和间隔域 gf;8:  d=|vf|/num;9:  根据 ran_root 产生间隔域 gf 的分裂份数 m 和选择 m 个子节点:1{ ,..., },mx xNode node node    满足:11 1( . ) 1, ( . ) 1;j jm mx xj jrandom key node value base random key node value base                  ≤ 且//base 为间隔域的分割基数(见第 3.3.4 节),可调整值参数 pv 和值间隔参数 pvc;10:  For j=0 to i do11:  Ifjxnode Node  then12:  .min min;jxnode 13:  .max min | | ( . );j jx xnode d gf random key node value     14:  Else15:  .min min;jxnode 16:  .max min ;jxnode d  17:  End If18:  min .max 1;jxnode  19:  End For20:  .ixnode value = node x . valuenum + i ;21:  .ixnode level = node x . level +1;2)  加密算法 Enc (  ) 对数据进行加密 , 即 , 要寻找一条从随机树的根节点到加密数据对应的叶子节点的路径 .

算法 2 . OPEART 的加密算法 Enc (  ).输入 : 值域 V =[min,max] 、随机树 RT 、密钥 key 、待加密数据 x 1:  在 x 的前面补 0, 使得补位后的 x 满足 | x |=|max  1|; 将 x 分解为 RT . level 段 , 第 i 段的值用 x [ i ] 表示 ;2:  node = node root , 其中 , node root .min=min, node root .max=max, node root . level =0, node root . value =0,3:  For  L =0 to  RT . level do4:  For  j =0 to  RT . num do // 判断 x [ L ] 对应 node 的哪个子节点5:  node j . value = node . valuenum + j ; // node j 表示 node 的第 j 个子节点5:  If  x [ L ]== node j . value then6:  i = j ; break;7:  End If8:  End For9:  node = RT . Div ( node , key , i );10:  If  L == RT . level then11:  ciphertext = node .min+( node .max node .min) random ( key + x [ L ]);12:  End If13:  End For14:  return ciphertext;3)  解密算法 Dec (  ) 也是要寻找一条从随机树的根节点到加密数据对应的叶子节点的路径 .

算法 3 . OPEART 的解密算法 Dec (  ).输入 : 值域 V =[min,max] 、随机树 RT 、密钥 key 、待解密数据 val .1:  node = node root , 其中 , node root .min=min, node root .max=max, node root . level =0, node root . value =0,2:  For  L =0 to  RT . level do3:  For  j =0 to  RT . num do // 判断 val 属于 node 的哪个子节点的区间4:  node j = RT . Div ( node ,  key , j );5:  If  val [ node j .min, node j .max] then6:  i = j ; break;7:  End If8:  End For9:  node =  node j ;10:  plaintext = plaintext + node . value ; // 字符串连接11:  End For

3.3 关键问题

3.3.1 密钥的值域和字符串的基本长度OPEART 的密钥 key 的值域用 V key 来表示 . 字符串的基本长度 len 定义了 OPEART 一次能处理的最长字符串长度 . 当一个字符串 S 的长度 | S |> len 时 , 在 S 后补充最少的随机字符得到 S , 满足 :| S | mod  len ==0. 然后 , 将 S 分割成 ( S / len ) 段 , 每一段字符串作为一个基本字符串进行处理 .密钥的值域和字符串的基本长度直接影响到 OPEART 算法的安全性强度 , 分析如下 :攻击者 A 可能会发起以下两种袭击 :(1)  当 A 得到一对明密文对 ( x , c ) 时 , 可通过遍历法求出 key . 假设 OPEART 加密一次基本字符串所需要的时间为 t , 则 A 攻破密钥的平均时间 T 为| || |keyVxT tlen    (6)其中 , x 是在 x 后补充随机字符后得到的字符串 . 根据公式 (6) 可知 , 指数越大 , T 值越大 , A 攻破密钥的难度就越大 .(2)  当 A 知道基本字符串长度 len 后 , 可以通过密文 c 的长度 len c 判断出明文 x 的长度 len x ; 然后 , 通过分析密文的出现频率和长度为 len x 的明文字符的各种组合的使用频率来推断明文 x . 假设明文字符的集合为 D x , 长度为 len 的字符串加密后的密文长度为 len b , 则 A 要完成以上分析的计算复杂度 O c 为| |cblenlenlencxO OD        (7)根据公式 (7) 可见 , O c 的最小值为 O ( D x | len ). 因此 , len 越长 , A 推断明文的难度就越大 .OPEART 采用 long 类型作为密钥 key 的类型 , 即 : key [  9223372036854775808,9223372036854775807],| V key |=2 64 , 字符串的基本长度 len =12( 由 RT 的定义域可知 ). 通过实验得出 : 当 RT . level =7, RT . num =100 时 , OPEART加密一次基本字符串所需要的时间 t =0.088ms. 假设已知一个长度为 len 的明密文对 , 则根据公式 (6),  A 要破解密钥需要 2.9 亿年 ; 根据公式 (7), 假设明文字符都是数字 , A 要进行统计分析 , 其计算复杂度为 O (10 12 ). 因此 ,OPEART采用 long 类型作为密钥 key 的类型 , 字符串的基本长度 len =12 能够有效抵御以上两种攻击 .

3.3.2 RT 的高度和宽度的平衡RT 的高度指树的层数 RT . level , 宽度表示每一个节点的子节点数 RT . num , 假设 RT 的定义域为 D , 则 :| D |= RT . num (RT.level1) (8)满足公式 (8) 的 RT . num 和 RT . level 的值并不是唯一的 , 例如 , 当 | D |=10 12 时 ,( RT . num , RT . level ) 可以取以下几种值 : v 1 =(10,13), v 2 =(100,7), v 3 =(1000,5), v 4 =(10000,4). 图 3 反映了以上几种值对对 OPEART 加解密性能的影响 , 其中 , length 为明文的长度 ,“ Enc _ v 1 ” 表示在 v 1 的情况下的加密时间 , 其他符号以此类推 . 如图 3 所示 ,( RT . num ,RT . level ) 的取值对加密和解密时间都有影响 , 对解密时间影响最大 . 其原因是 , 根据算法 Div (  ) 的第 10 步 , 要判断一个子节点jxnode 是否属于 Node , 这是一个遍历的过程 , 对于加密操作 , 从根节点找到对应的叶子节点的计算复杂度为 O ( RT . numRT . level ); 对于解密操作 , 从根节点找到对应的叶子节点的计算复杂度为 O ( RT . numRT . numRT . level ). 因此在实现 RT 的时候 , 要根据 RT 的定义域 , 选择合适的高度和宽度 , 从而获得较好的效率

3.3.3 随机数的选取在 RT 中 , 划分节点 node x 的区间 D x =[ node x .min, node x .max] 时 , 以密钥 key 和 node x . value 作为选取随机数的根 , 从而生成随机数 ran x ( ran x R 且 ran x  (0,1)), 然后根据 ran x 将 D x 分为值域 vf 和间隔域 gf 两部分 . 假设 node x的直接子节点和间接子节点的个数为 Sum x , 为使 vf 能够容纳下所有子节点且能够保持随机性 , ran x 应满足如下要求 :(1) 当 Sum x / D x ≤ 0.3 时 , ran x  (0.3,0.7);(2) 当 Sum x / D x  (0.3,0.7) 时 , ran x  ( Sum x / D x ,0.7);(3) 当 Sum x / D x ≥ 0.7 时 , ran x  ( Sum x / D x ,1).

3.3.4 间隔域的分割基数间隔域的分割基数 base ( base [1, RT . num ]) 限定了分割间隔域的最小份数 . 根据算法 1, 将间隔域 gf 根据ran _ root 随机分裂为大小不等的 m 份 , 再根据 ran _ root 随机选择 m 个子节点1{ ,..., },mx xNode node node    满足                 ≤ 且Node中的子节点ixnode 可分配得到大小为| | ( . )ixgf random key node value    的子间隔,因此,间隔域分裂时产生的子间隔大小是随机的,分裂份数 m 是不确定的,但 m≥base.间隔域主要用于实现对数据分布的干扰,一方面,m 越大,受干扰的子节点就越多;另一方面,如果 m 太大,那么,虽然受干扰的子节点个数多,但对每个节点的干扰不大.因此,选择合适的分裂基数将直接影响到 RT 的随机性.图 4 反映了间隔域分裂基数 base 对 RT 随机性的影响,其中,RT 1 .level=7,RT 1 .num=100;RT 2 .level=5,RT 2 .num=1000.如图 4(a)和图 4(b)所示,对于 RT 1 来说: 当 base=40 时,pv 的值最小,pvc 的值最大.由 RT 的随机性强度定义可知,这时,RT 1 的随机性最好; 当 base<40 时,受干扰的子节点个数不够多,因此随机性不够强; 当 base>40 时,每个节点的干扰区域太小,因此随机性也不够强.根据图 4(c)和图 4(d)所示,对于 RT 2 来说:当 base=400 时,pv 的值最小,pvc 的值最大.这时,RT 2 的随机性最好.(a通过以上分析可知,间隔域分割基数对 RT 的随机性是有直接影响的,当 base=RT.num40%时,RT 的随机性最好.

3.3.5 拐 点在 RT 的 Div()算法中,对于 node x 节点,根据密钥 key 和 node x .value 随机地将 node x 的区域 D x 分为值域 vf和间隔域 gf 两部分,然后再以 key 和 node x .value 为根,随机地将间隔域 gf 分裂成 m 份,并随机地选择 m 个子节点构成子节点集合1{ ,..., },mx xNode node node    满足:11 1( . ) 1, ( . ) 1.j jm mx xj jrandom key node value base random key node value base                  ≤ 且因此,在进行加解密时,当判断某一子节点ixnode 是否属于 Node 时,平均需要进行(m/2)次取随机数运算和加法运算.当间隔域的分割基数为 RT.num40%,OPEART 的随机性最好,则 m≥RT.num40%.因此,加解密一个基本字符串 S 时,除最底层以外的各层都要进行上述判断,其平均计算复杂度 O r 为.( . 1)5rRT numO O RT level     (9)例如,当 RT.num=1000,RT.level=5 时,一共需要进行 800 次随机运算和加法运算,这是一个较大的计算负载.因此,OPEART 引入了拐点的概念.引入拐点的目的是对间隔域 gf=[g min ,g max ]进行粗粒度的划分,得到多个大小不等的桶,每个桶的边界即为拐点.生成拐点的步骤如下:采用二叉树结构,在二叉树的第 1 层,根据 key 和 node x .value 取随机值 i(i R ,且i(0.3,0.7)),拐点为 x=g min +(g max g min )i,其中,限定 i(0.3,0.7)是为了尽可能平均分割 gf.于是,拐点 x 将 gf 分割成[g min ,x]和(x,g max )两个桶.接下来,递归的对两部分进行划分,直至产生足够的拐点.假设有 n 个拐点,则 gf 被分成了(n+1)个桶.判断某一子节点ixnode 是否属于 Node 时,首先按照拐点生成的方法寻找一条从树根到叶子节点的路径,确定ixnode 对应的桶,然后再对桶内的子节点逐一比较,判断它是否在桶内即可.实际上,拐点实现了对 Node 中的m 个子节点的近似折半查找.合适的拐点个数 n 要依据 RT.level 和 RT.num 来确定.图 5 反映了拐点个数对OPEART加解密性能的影响,其中,length为明文的长度,“Enc_0”表示在拐点个数n=0时的加密时间,其他符号以此类推. 如图 5(a)所示,在 RT.num=100,RT.level=7 的情况下,当拐点个数 n=3 时,OPEART 的加解密效率最高;其次是n=7 的情况;当 n=32 时,与 n=0 的情况相似,OPEART 的加解密效率最低.如图 5(b)所示,在 RT.num=1000,RT.level=5 的情况下,当拐点个数 n=7 时,OPEART 的加解密效率最高;其次是 n=15 的情况;当 n=0 的时,即,没有拐点的情况下,OPEART 的加解密效率最低.根据以上分析可知,拐点可以提高 OPEART 的加解密效率,但合适的拐点个数要依据 RT.level 和 RT.num 来确定.

4 OPEART 的正确性和安全性

定理 1 . OPEART=(Gen_RT,Enc,Dec)是正确的,如果满足以下条件:(1) mD,Dec(RT,key,Enc(RT,key,m))=m;(2) 如果 x 1 >x 2 (x 1 ,x 2 D),那么 Enc(x 1 )>Enc(x 2 ).证明 :(1) 根据 RT 的结构,每个节点对应定义域中的一个点,每个子节点的值域是对父节点值域的任意划分且没有交集,因此保证了任何密文值只能属于一个叶子节点的值域空间.另外,如算法 2 和算法 3 所示,加密和解密的过程都是寻找一条从 RT 的根节点到明文值对应的叶子节点的路径.不同的是,在加密时,由于知道明文 x,因此只需调用 RT.Div()算法一次,根据由密钥 key 和 x 构成的 ran_root 直接求出分裂份数 m 和选择 m 个子节点集合 Node;在解密时,由于不知道 x,因此要逐一检查节点 node x 的每个子节点jxnode ,根据由 key 和 .jxnode value构成的 ran_root 产生jxnode 的值域,然后判断密文 val 是否属于该子节点的值域,从而找到对应的明文,也就是说,要多次调用 RT.Div()算法.因此,只要加密和解密的过程中使用相同的密钥 key,就能找到相同的一条路径.因此,mD,Dec(RT,key,Enc(RT,key,m))=m.(2) 根据 RT 的结构,每个子节点的值域是对父节点值域的任意划分且没有交集,假设 node x 的两个相邻的子节点为jxnode 和1 , jxnode其中1 .. 1j jx xnode value node value  ,则有1 .min.max 1j jx xnode node  .因为 ( . ) .min ( . ) ( .max .min),j j j j jx x x x xEnc node value node Random key node value node node     1 1 1 1 1( . ) .min ( . ) ( .max .min),j j j j jx x x x xEnc node value node Random key node value node node        所以,1( . ) ( . )j jx xEnc node value Enc node value .所以,OPEART 是保序的.综上所述,OPEART 是正确的.  □定理 2 . OPEART 是 IND-DNCPA 安全的.证明 :假设攻击者 A 发起以下攻击:(i)  选择一组明文 M={x 1 ,x 2 ,…,x k }(x i D,x i x j 且 i,j[1,k])向OPEART进行加密询问,OPEART将加密的结果 C={c 1 ,c 2 ,…,c k }返回给 A,A 试图通过解方程的方式解出其他密文 c(cC)对应的明文;(ii)  A 选择两个数据 m 0 ,m 1 发给 OPEART,其中,m 1 =m 0 +1,且 m 0 M,m 1 M;(iii) OPEART 随机加密其中一个数据 m b (b{0,1}),并将产生的密文 c b 返回给 A;(vi)  A 输出 b作为对 b 的猜测.(1) OPEART 通过以下操作产生了随机性,从而使得从明文到密文的映射关系是无法通过解方程的方式来破解的:(i)  对于非叶子节点 x i ,以密钥 key 和 x i 来决定该点的值域和间隔域的大小,使得不同的点具有不同的值域和间隔域大小;(ii)  对于非树根节点 x j ,以 key 和 x j 作为随机数的根,将父节点的间隔域随机地分成大小不等的 m j 份,并分配任选的 m j 个子节点;(iii) 对于叶子节点 x k ,以 key 和 x k 产生随机数在(min k ,max k )之间选择一点作为 x k 的密文.(2) 由于 OPEART 具有保序性,A 可能通过分析 M 中密文的差距以及与 m 0 或 m 1 最近的点的密文来推断b.M 中密文的差距受 OPEART 的随机性的影响:(i)  当 A 通过求出平均距离 d=(Enc(x k )Enc(x 1 ))/(k1)来猜测 x 的值时,由于 pv0,说明由于 OPEART 的随机性,使得密文与参照函数 f(x)=Enc(x 1 )+(xx 1 )d 相差很大,因此,A 无法从密文直接猜测出对应的明文;(ii)  当 A 通过分析密文之间的距离 d来推测密文的值域时,由于 pvc>pvc avg ,说明相邻点密文之间的变化超过了 d,尤其是 p i 0(i[1,5])且 pvcpvc max 时,处于 5 个变化区间的百分比达到了最大值,d的波动最大,即,d[1,Vn],使得 A 要判断值域的大小变得很困难.因此,A 的优势概率为Adv(A)=|Pr[b=b]0.5|=|(0.5+  )0.5|=  ,其中,  是一个足够小可忽略不计的数.综上所述,OPEART 是 IND-DACPA 安全的.  □

5 OPEART 的性能

本节将通过测试OPEART的随机性能判断其是否能够达到IND-DACPA安全性的要求;通过对比OPEART和 OPES 的性能来分析 OPEART 的效率,性能指标包括加、 解密性能,关系运算性能以及存储/通信负载等.实验部署在由本研究小组自行研发的青云实验平台 3.0 上,该平台是一个基于 Web 的面向校园的云计算环境,以KVM 和 Hadoop 的 HDFS 为底层支撑技术,并部署在由 12 台服务器构成的集群上.

5.1 随机性能实验 1 测量 OPEART 在相同密钥下不同数据组的 pv 值和 pvc 值,每次随机抽取 10 000 个连续的数进行加密,重复 100 次,如图 6 所示.实验 2 测量 OPEART 在不同密钥下同一组数据的 pv 值和 pvc 值,每次随机生成密钥,对同一组由 10 000 个连续的数组成的数据组进行加密,重复 100 次,如图 7 所示.在测试 pvc 值时,当出现 p i =0(i[1,5])时,pvc=0. 如图 6(a)和图 7(a)所示,pv 值均小于 10 15 ,是一个足够小的数,因此满足 pv0 的随机性要求;如图 6(b)和图7(b)所示,pvc 值均大于 2.4,满足 p i 0(i[1,5]),pvc>pvc avg 且 pvcpvc max 的要求.在某些点的 pvc 值大于 2.5,那是因为处于第五区间[(2d,Vn)]的连续密文之间的差距的平均距离大于 9d/4.实验 1 和实验 2 表明:OPEART 具有很好的随机性能,能够满足 IND-DACPA 的安全性要求.

5.2 OPEART的效率实验 3 比较了 OPEART 与 OPES 在加解密、 关系运算以及存储/通信负载这 3 个方面的性能,其中,OPEART的level=7,num=100;OPES具有和OPEART相同的数据域和值域,输入分布函数和输出函数的分桶数分别为100和 150.结果如图 8 所示. 如图 8(a)所示,OPEART 的加密和解密负载几乎是一样的,而且均比 OPES 的加解密负载低;在进行关系运算时,OPEART 与 OPES 的运算负载相差不大,基本上是在 0.01ms~0.013ms 之间;对于相同长度的明文,OPEART的密文长度小于 OPES.总的说来,OPEART 比 OPES 具有更好的运行效率.6 结束语针对云计算中的隐私保护问题,本文提出了支持隐私保护的云计算模型,并设计了一种支持隐私保护的加密方案OPEART.OPEART是一种保序的、 确定的对称加密方案,支持对加密数据的任何一种关系运算(=,>,<等).安全分析和性能评估证实:OPEART 具有 IND-DNCPA 安全性,并且具有很好的运行效率.下一步,我们将从提高安全性的角度对 OPEART 进行改进,同时也计划研究新的加密技术来实现安全的密文计算.

References :[1] Jessica EV. Google discloses privacy glitch (2009). 2011. http://blogs.wsj.com/ digits/2009/03/08/1214/[2] Song DX, Wagner P, Perrig P. Practical techniques for searches on encrypted data. In: Proc. of the 2000 IEEE Symp. on Securityand Privacy. 2000. 44-55. [doi: 10.1109/SECPRI.2000.848445][3] Bonech D, Crescenzo GD, Ostrovsky R, Persiano G. Public-Key encryption with keyword search. In: Proc. of the Eurocrypt 2004.2004. 506-522.[4] Ohtaki Y. Partial disclosure of searchable encrypted data with support for boolean queries. In: Proc. of the 3th Int’l Conf. onAvailability, Reliability and Security (ARES 2008). 2008. 1083-1090. [doi: 10.1109/ARES.2008.80][5] Liu Q, Wang GJ, Wu J. An efficient privacy preserving keyword search scheme in cloud computing. In: Proc. of the 2009 Int’lConf. on Computational Science and Engineering. IEEE, 2009. 715-720. [doi: 10.1109/CSE.2009.66][6] Boldyreva A, Chenette N, Lee Y, O’Neill A. Order-Preserving symmetric encryption. In: Proc. of the 28th Annual Int’l Conf. onAdvances in Cryptology (Eurocrypt 2009). 2009. 224-241. [doi: 10.1007/978-3-642-01001-9_13] [7] Belazzougui D, Boldi P, Pagh R, Vigna S. Monotone minimal perfect hashing. In: Proc. of the 20th Annual ACM-SIAM Symp. onDiscrete Algorithms. 2009. 785-794.[8] Fox EA, Chen QF, Daoud AM, Heath LS. Order-Preserving minimal perfect hash functions and information retrieval. ACM Trans.on Information Systems, 1991,9(3):281-308.[9] Czech ZJ, Havas G, Majewski B. An optimal algorithm for generating minimal perfect hash functions. Information ProcessingLetters, 1992,43(5):257-264. [doi: 10.1016/0020-0190(92)90220-P][10] Agrawal R, Kiernan J, Srikant R, Xu YR. Order-Preserving encryptiion for numeric data. In: Proc. of the 2004 ACM SIGMOD Int’lConf. on Management of Data (SIGMOD 2004). 2004. 563-574. [doi: 10.1145/1007568.1007632][11] Boldyreva A, Chenette N, O’Neil A. Order-Preserving encryption revisited: Improved security analysis and alternative solutions. In:Proc. of the 31st Annual Conf. on Advances in Cryptology. 2011. 578-595.[12] Wong WK, Cheung DW, Kao B, Mamoulis N. Secure kNN computation on encrypted databases. In: Proc. of the 35th SIGMODInt’l Conf. on Management of Data (SIGMOD 2009). 2009. 139-152. [doi: 10.1145/1559845.1559862][13] Boneh D, Sahai A, Waters B. Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Proc. of theEurocrypt 2006. LNCS 4004, 2006. 573-592. [doi: 10.1007/11761679_34][14] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In: Proc. of the TCC 2007. LNCS 4392, 2007.535-554. [doi: 10.1007/978-3-540-70936-7_29][15] Shi E, Bethencourt J, Chan THH, Song D, Perrig A. Multi-Dimensional range query over encrypted data. In: Proc. of the 2007IEEE Symp. on Security and Privacy. 2007. 350-364. [doi: 10.1109/SP.2007.29][16] Wang PH, Lakshmanan LVS. Efficient secure query evaluation over encrypted XML databases. In: Proc. of the 32nd Int’l Conf. onVery Large Databases. 2006. 127-138.[17] Hacıgümüş H, Iyer B, Mehrotra S. Efficient execution of aggregation queries over encrypted relational databases. In: Proc. of the9th Int’l Conf. on Database Systems for Advanced Applications (DASFAA 2004). 2004. 633-650. [doi: 10.1007/978-3-540-24571-1_10][18] Hacıgümüş H. Privacy in database-as-a-service model [Ph.D. Thesis]. Irivne: Department of Information and Computer Science,University of California, 2003.[19] Wang C, Cao N, Li J, Ren K, Lou WJ. Secure ranked keyword search over encrypted cloud data. In: Proc. of the 30th Int’l Conf. onDistributed Computing Systems (ICDCS 2010). 2010. 253-262. [doi: 10.1109/ICDCS.2010.34]