不可信云计算环境下存储数据的隐私保护问题已逐渐引起人们的关注，目前保护数据隐私安全的方法之一是采用加密技术将数据加密后再存储到数据库，但必须要解决对密文的运算、检索等问题。提出一种可变保序编码方案gmOPE，基于广义平衡二叉搜索树（AVL-N）进行保序编码，允许用户自定义加密算法与调整策略，保证加密的信息保留明文的顺序关系，使用户能直接对数据库中密文进行高效的顺序相关查询。gmOPE支持任意数据类型的保序加密，运用新型重平衡调整策略，提高数据库增减操作的效率。实验结果表明，gmOPE方法有效地降低了用户与数据库交互和编码变更带来的额外开销，提高了密文数据库的运行效率。孙彦珺,杨庚,史经启,等:用户可自定义的低调整率保序加密算法():用户解密密文c从而获得加密前的明文。衡因子,若超过则进行(),执行“旋转”操作;否则()…:判断待插入明文v与明文v的大小更新节点p高度,继续往上回溯:节点p指向当前节点关系。若<,则向左进行查找”;若父节点,转()。υ-',则找到节点;若υ>υ′,则向右进行查找对以节点p为根节点的子树进行“旋转”,更新相关节点的编码和高度,退出算法。():服务器基于用户的反馈信息,返回下一个优缺点分析密文c,并执行步骤()。达安全等级,是种安全、高找到v,或者服务器到达树的一个空效的交互性保序加密方案。平衡一又树是实现节点时,算法终止,返回路径如图所示,数据库中存储了、加密方案的关键数据结构,但是严格维护其平衡性会引发高频次的重平衡操作,严重降低算法效率,增加服务器计后的密文对应的编码信总。当插入新数据时,按○算开销,当数据库中存储大量数据时尤为明显。如果适算法的步骤操作,依次与比较后得到插入位置当地放览平衡二义树约束条件,降低重平衡执行次数,的路径为根据路径进行二进制编码先可以在不对密文操作造成较大影响的情况下,显著降低在补¨”,然后补“”直到达到规定长度服务器端的开销即为该节点的二进制编码例如.的编码为编码方法通用编码公式定义如下数据的插入操作主要分为两部分:定位数据插入位置并计算保序编码和保证逻辑二义搜索树的平衡性。阶段每次必须执行,阶段则根据需要执行,且阶段耗时较多,因此若能降低阶段的执行频次,就能显著地提高数据插入的效率。本文通过放宽约束条件到N,将扩展为广义平衡二叉树N,降低重平衡频次,提升算法效率。基于广义平衡二叉树进行编妈,使用“(N+2)+(N+3)”重构算法替换旋转”操作,因而比更具通用性。同时通过借助数据库临时表实现重排算法、设计正确且髙效的编码更新规范等方法对算法进行优化,进一步提升算法整图数据结构概览体效率。平衡调整策略平衡叉树的重平衡方法重平衡算法由端定义实现。用户在需保证二叉树的平衡性,可以减少交互次数,提要的时侯向服务器发送请求结合前文的交互实高用户洵数据的效率。重平衡操作一般采用旋转法,现重平衡。该算法具体描述如下但旋转调整的理论比较抽象,旋转方向又各不相同,代算法重平衡算法码量大且流程复杂,实际使川较为复杂。如耒利川平衡输入:节点的路径义树“中为根、小为左、大为右”的特性来重组失衡子输出:无树,可以省去针对不同的失衡结构采用不同的旋转方法()根据路径,在中从插入节点的父的复杂中间过程,使算法更为简单节点开始向根节点回溯。设当前回溯节点为p。文献提出了一种新的重平衡方法来替换()查询数据库得到节点p的高度hro和左、右旋转"操作,当平衡二叉树出现失衡,只需要从失衡节点子树的高度h!en、hgt。由于插入新节点后,节点p开始向深度较深的子树方向进行搜索,就可以得到失的高度可能会发生改变,记父节点新的高度 h root nere=衡节点、一个较深子节点和较深子节点的较深子节点max(h_left, h right)+1把这三个主干节点和四个从属节点按照完全二叉树的()比较插入新节点前后节点p的高度 h root和结构进行重新排列,就可以恢复平衡。h root new,判断树平衡性。如果高度不变,说明本文在此基础上,扩展为“(N+2)+(N+3)”重构算树依然平衡,不需要重平衡,退出算法;否则,继法,并把该算法应用于广义的平衡二义树中,该树允许续()。用户自定义平衡因子N,又称为N树,并用此优()判断节点p的左、右子树高度差值是否超过平化扩展后的重平衡算法主要由两部分组成,算()计算机工程与应用法主要用亍标识、保2N+5个失衡节点,并利用算)将失衡一叉树按照重排序完全二叉树重构,更法自动计算的失衡节点分类情况,把失衡树重构为完新节点编码,详见节。全二叉树,其中N+2个节点称为主干节点,主干节点更新高度:山叶子节点开妗向上,根据左右子节点对应二叉树中单个节点;N+3个节点称为高度计算并更新父节点高度h,m0ee= max(h_ lefa,从属节点,从属节点对应的单个节点或某A)+1,并向上回滴至重排序完全二义树根节点个子树抽象而成的抽象子节点。之后更新各个节点的注:有序完全二乂树是指按照广度优先遍历方式ⅷ编码和高度信息,以及N+3个抽象子节点下属所有节历二叉树,得到的是有序数列。下文概念相同点的编码信息。算法主要用于计算失衡节点对应的建立一个大小为的节点指针数组mde8收集并分类情况,求出重排后完全二又树各节点相应的编号,保存节点信息:号节点为失衡节点的父节点,号节点并存储在数组md中由于平衡二又搜索树是通过为失衡节点,号节点为号节点较深的子节点,号节编码维扩的逻辑二又树因此对于节点点为号节点较浅的子节点。以此类推直到所有失衡左、右孩子及父节点的查找可以直接通过路径。定《二又树节点都收集完成,采集剑的节点数组为图中第位到该方法采用自动计算分类的形式流程简单,易一类对应的编号。失衡节点的父节点可以通过路径于操作去掉最后一位后往上回溯求得,与n0e0效果相当N=1时,N树的约束条件与普通的平衡同因此文章不单独列出mO],默认为节点my义搜索树相同。如图所示图中数字为节点编号,四m2N+5]。之后根据算法,求出重排后完全二叉树幅图中每幅图的左侧为失衡二又树,右侧为重排后的结各节点相应的编号,生成重平衡后的广度优先遍历数组果。下面以第一类(对应左旋)为例详细讲解重排过程。ide(详细步骤见节)。最终根据 ideal]数组即可重建半衠二叉搜索树,并根据算法更新树对应数据项的编码和高度,至此完成了一次重平衡操作构建重排序二叉树及改进()第一类,对应左旋()第二类,对应先右旋再左旋当N=1时重排后的完全二叉树有种类型,每种类型对应的数组中包含个编号元素;当N=2时有种类型,包含个编号元素。以此类推,N越大对应的分类情况越多,计算量也越大,人工难以胜任。因此结合算法,采川自动计算分类的形式,可以直接计算出失()第三类,对应先左旋再右旋)第四类,对应右旋衡树对应的重排数组,简化计算过程。算法的主要功图四类重平衡情况示例能是根据采集到的失衡树节点,求出重排后的节点编算法重平衝算法号,构建完全平衡二叉树。具体算法内容如输入:失衡节点的路径算法输出:无输入:平衡约東N,收集的节点数组noel()查找并保存失衡叉树的2N+5个节点信息。输出:重排序完全二又树节点数组ider①将失衡节点作为根节点,存入nii-1);)中序遍历()失衡树,得到对应的编号数组②比较“”节点和节点的高度高度 UBTArrayl较大的节点作为主干节点,较小的作为从属节点。主干UBTArruyl=LDR(nodel]节点存入noe[i+1,从属节点存入〃et+N+3]。()构建包含2N+5个节点的有序的完全平衡i+1,若N+1,转④,香则转③;叉树,屮序遍历完全二叉树,得到完全二叉树数组③将主干节点作为新根节点,并根据主干节点相CB7Aray对父节点的左右方向在后补“”或“”,转②CBTArrayl =LDRiCreat Btree By Order())④meN+3]-新根节点的左孩子,n0le[2N+5])根据上面的两个数组,构建重排序完全二叉树新根节点的右孩子得到对应的广度优先遍历数组mde。()构建重排序完全二叉树:根据失衡二叉树和对i-12N+5应的有序完全二叉树构建重排序完全二叉树,得到广度der[CBTarrayli]=UBTArrayli优先遍历重排序完全二叉树节点数组ide]。算法由三部分组成,以第·类情况为例,说明重ileo](算法)排过程。如图所示,中序遍历失衡树得到数组孙彦珺,杨庚,史经启,等:用户可自定义的低调整率保序加密算法UBTArruyL然后构建包含2N+5二叉树结构,百底向上依次对各个节点进行更新即可个节点的有序完全二乂树并进行中序遍历,记为数组而对于节点编碼,则要设计一种高效、正确的编码更新CBTArrayL]-,,,,,。步骤()结合 UBTArrayl]规范。和 CBTArray],得到重排后的索引数组dex由于节点路径发生变化,节点编码即为重排完全一又树的广度优先遍厉结也随之改变,并且改变前后的节点编码均只与果。结合路径和编码在算法中即路径有关。将所有节点编码拆分为前级和后可完成重平衡操作缀前缀《由路径决定,后缀由各节点在了树内部的具体路径决定。定义编码调整公式为:e nete encoder=new prefix +(OPE encoding oldprefix)x Pow(2, old_ len new len0其中 new le和 old len分别为新旧路径的长度对整张表进行编码更新会明显降低执行效率,凡其是在数据库中已经存在大量数据记录时。因此可以结合叶子节点对应的编码范围限定受影响的节图算法讲解图例点,从而在正确更新编码的同时,保证编码更新效率。算法主要涉及数组操作和中序遍历操作,在高级编程语言中实现较为简单由于算法不涉及任何客理论分析户端操作,同时为省去不必要的通信开销,将算法定时间复杂度分析义成数据库,借助数据库临时表实现重排算法。通本文介绍的方案和新提出的方案过临时表实现重排算法,使逻辑更加直观简洁省去了插入过程都主要分为两个阶段:阶段包括定位插入位构建完全二义树和中序遍历等操作,既简化了算法步置、计算编吗、改写语句和向数据库中插入密骤,又节省了计算时问,提升了算法效率。以图第文记录;阶段为检杏逻辑二叉树是否失衡并触发重平类情况说明其体实现过程。首先将节点编号按采集顺序依次存入临时表衡算法在第一阶段,逻辑平衡二义树相关操作的时间复杂(图()取值为,将的值与节点编号对应存入表中。再将表格内容按张度最大。客户端与服务器交互找到待插入数据的位置。假设数据表屮巳经存在n个数据项,由于两种方案编码大小排序,达到与中序遍历相同的的实现方式均为平衡二叉树因此具有相似的时间复杂效果,编号排序随之改变。然后将中序遍历有序完度。客户端与服务器在最好情况下需要进行b+1)全二义树的结果数组CE1Aray存入列编号,如次通信交互,以及相应次数的加解密操作;而在最坏情图()所示。最后将图()对列编号执行语勹,即可得到图()中的结果,此时编号列的况下仍然为(bn+1),由于平衡因了由内容即为重排后的完全二叉树广度优先遍历的结果。扩展到了N,因此需要多进行N次交互操作,复杂度之后按算法的后续步骤即可完成一次重排序过程。为bn」+1)-N。改进后的算法借助数据库临时表,通过语句在第二阶段,所有操作均在服务器端进行,因此没达到中序遍历相同的效果,简化了重新生成mle数有通信开销,仅有平衡性检测和重平衡开销。两种方案组的过程。在每次插入数据后都调用函数检查平衡性,当存在失衡节点时,可能会不断回溯至根节点,即为最坏情編引编号別编引引编引况O(lbn);当二叉树仍然平衡时,结束回溯操作,即为最好情况O(1)。判断失衡的方法与方案致,囚此两者时间复杂度相似。重平衡操作时,在最好情况下,需要平衡包含空节点在内的2N+5个()初始()中间结果()最终结果节点,要平衡个节点;最坏情况即为调整整个图数据库临时表实现重排算法树,两者时间复杂度均为0)(n更新从属节点及子节点编码方法基丁普通平衡二叉树来编码,大约每插当在执行算法的步骒()生成了重排序完全二又入两次数据就会触发一次重平衡操作。而基于树之后,需要更新2N+5个失衡节点对应的编码和高广义平衡一:叉树N来编码,降低了插入数据时触度信息、对丁重平衡后树中节点的高度,根据调整后的发重平衡操作的概率,N越人,触发重平衡操作的概率()计算机工程与应用就越低。假设插入相同的数据量为n,重平衠定义用来实现逻辑二叉树调整及编码调整策操作的次数n小于的n1,因此的重平衡略。客户端程序主要功能为定位插入位置数据加解密频率f也小于的fm,即f≤f(N=1时等号等计算操作,端主罗负责编码的调整和逻辑二叉成立)又因为单次时间复杂度基本相同,所以树的维护。其中加解密算法为电子密码本模式的分组重平衡操作的平均时间复杂度更具优势。重平衡操作加密算法分组长度为位在整个插入过程中耗时最多,因而虽然单次抽入操作时实验平台由于N的存在时间复杂度略微高于硬件平台主要为服务器节点。节点运行数多次插入时,由于此整体时间复杂度更其优势。sea.ore调整频次比低得多因据库及函数,配置为:为缓存;内存为在实际生产坏境中数据库的记录数n>N,因此;硬盘为N可以忽略不计,ON)即为O(1),见表。钦件平台:操作系统与时间夏杂度比较数据库为版本为位时间复杂度单次时间复杂度平均时间复杂度实验中将客户端放置在服务器节点一同运行程序查找和最好Obn)OO(bn)Oabn)忽略客户端和端的通信时延,主要对数据插入操计算编码最坏O(bn)OIOlb)Obz+N)作的性能进行分析对比平衡性检查最好(1)(1)数据集和采川同一数据集,为使川最坏ObO(bn+N)O(bn)O(bn+N)随机生成的包含条不重复的整数型数据的重半衡二叉却最好O1)ON)1m×O1)kxON)数据集最坏O(n)On)Jm×O1m)fs×O(n)满足对任意i,n≠r与r的大小关系随机实用性对比实验结果分析年等首次提出了一种基于多重线性分別对和屮N树N为、、映射的保序加密概念。该方案虽然为最新研究成、五种情况卜的方案进行测试,比较它们的性能差别,果,为保序加密提供了新的研究思路,但在安全性方面分析在不同情况下插入不同数据量的明文数据所需的仍有不足,且在应用实现上有一定难度,而已经时间以及触发重平衡操作的次数。在系统中得到实际应用。本文在基础调整时间上改进提出的方家,可以自定义函数配合图为两个阶段总的时间消耗随插入数据量的变现有数据库使用不需要对数据库做定制,并能根据需化,包括阶段中的计算时间和数据库插入耗时阶段要结合现有加密方案增强安全性,安全性达到中调用函数检査二义树平衡性并重新调整二义树等级,更好地应用亍实际生产环境。因此与和编码。其中阶段的计算量主要由查找明文插入位和相比,兼顾了安全性与效率,可以在实置、加解密操作、重写语句和数据库插入操作组成,际应用中发挥其优势,见表。和的每一次插入操作均必须经过阶段的所有步骤,因此两种方案在阶段的耗时基本相同实验数据与分析且方案中N的增大并未对阶段的耗时造成明本文分别实现了和并且在相同的显影响。图为阶段的耗时随插入数据量的变化。在实验环境中对两种方案分别进行了测试和插入条数据的时候,和在N取不同程序均为结构,分为客户端和服务器端两部值时阶段耗时均约为,其中计算时间约为分。客户端使用实现,通过与服务器通信;插入耗时约为端主要为数据库。端数据库为未阶段的操作为和的共同部分,时间经修改的普通数据库,包含用户事先实现的自消耗基本致,两者时间开销的差别主要集屮在阶段表方案对比分析方案安全性信息泄露除了顺序(平均)复杂度应用场景明文前半部分比特信息O(n×P(m)第一个不同的比特块下标 O niM)无g×O(n)注:P(m)关于m的多项式,其中m是m多重线性映射,λ是安全参数孙彦珺,杨庚,史经启,等:用户可自定义的低调整率保序加密算法插入记录数条插入记录数条插入数据量与总的时间消耗图插入数据量与阶段的耗时插入记录数条插入记录数条图插入数据量与阶段的耗时图插入数据量和触发重平衡操作的次数的二义树重平衡操作部分,因此下面重点分析两者在阶时所触发的重平衡操作的次数,在N=1时段的时间差别,对比分析两者的性能。N即为普通的树,调整次数与完全图为阶段的耗时随插入数据量的变化,观察可致。随着N的增大,的重平衡次数具有越来越知两个方案均具有稳定性,调整时间随数据量的增加稳明显的优势:当N=2时,的调整次数仅为定增长,没有出现因为数据量的增加而导致操作时间急N=3时的调整次数已经下降剧增长的情况。在N=1的时候即为普通的为的树,与效果一样:两者触发重平衡操作的频图是当用户向数据库中插入条数据时,触次如图所示,完全一致;由于具有通用性,在发重平衡操作的次数随广义平衡叉树中N的大小的收集失衡节点及二叉树调整等操作步骤的时候比变化关系。从图中可以看出,在方案中,随平衡复杂,因此调整操作比耗时多,实验显示插入因子N的增大,触发重平衡的操作次数有显著的降条数据()阶段耗时比多出低。当N=1时,插入同样的数据量的重平衡但随着N的增大,在插入数据过程中次数只有的千分之触发重平衡操作的次数显著下降,重平衡操作的总耗时也随之下降。虽然单次二叉树调整操作耗时比多,但因为调整频次显著下降,因而在N≥2时的整体效率优于。结果显示,在N=2~5时在阶段中调整操作的耗时比节省约当N取值为时阶段效率比提升约,整体效率提升约。并且随着N的继续增大效率提升会更加显著日丹调整颎次平衡因子图描述的是两种方案在插入不同数据量的数据图平衡因子与插入数据时触发重衡操作的次数()计算机工程与应用小结本文利用广义的平衡二叉搜索树,实现了可变保序编码方案,并取得了较为理想的实验结果。把该保序加密方案运川在数据加密系统中,可以让客户端能直接对文数据库中的数据进行检索等作且支持任意类型数据的保序加密。加密方案允许用户自定义平衡约朿糸件,采用新型的重平衡调整方法,既保证了保序加密方案的可变性,又减少了重平衡的次数,提高了效率。实验结果表明整体效率得到●大幅提升,在N苧5时,整体效率提升约参考文献江顺亮,胡世鸿,唐祎玲,等低调鳘率的广义树及其统一重平衡方法计算机应用