基于二叉树存储的多用户oram方案-孙晓妮.pdf

《基于二叉树存储的多用户oram方案-孙晓妮.pdf》由会员分享，可在线阅读，更多相关《基于二叉树存储的多用户oram方案-孙晓妮.pdf（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软件学报ISSN 10009825，CODEN RUXUEWJournal ofSoftware，2016，27(6)：14751486doi：10133280cnkijos005002】中国科学院软件研究所版权所有基于二叉树存储的多用户ORAM方案木孙晓妮，蒋瀚，徐秋亮(山东大学计算机科学与技术学院，山东济南250101)通信作者：蒋瀚，E-mail：jianghansdueducnE-mail：jOSiscasaccnhttp：wwwjosorgcnTel：+86一1062562563摘要： 随着大数据及数据挖掘技术的发展，云计算环境中用户访问模式成为泄露用户隐私的一条途径不经意随机存取技

2、术(ORaM)是保护用户访问模式的一条有效途径现有的ORAM方案中，大部分只支持单个用户，而唯一支持多用户的ORAM方案是基于分层ORAM方案设计的，但其混淆过程的计算复杂度高为了避免出现混淆过程，在基于二叉树ORAM方案的基础上，构造了一个多用户的ORAM方案首先，改进了一个代理加密方案，然后在多个用户和服务器之间引入一个代理，利用改进的代理加密机制，将不同用户加密的数据，通过代理再次加密成相同密钥加密的数据存储到服务器该方案的安全性基于伪随机函数的不可区分性，其最差情况下的计算复杂度和平均计算复杂度均为O(1092肝)，比现有的多用户ORAM方案的效率要高关键词： 云计算；二又树；不经意随

3、机存取；多用户；访问模式中图法分类号：TP309中文引用格式：孙晓妮，蒋瀚，徐秋亮基于二叉树存储的多用户ORAM方案软件学报，2016，27(6)：14751486http：1wwwjosorgc“lOoo-9825，5002htm英文引用格式：SunXN，JiangH，XuQLMulti-Userbinarytree basedORAM schemeRuanBanXueBaoJoumai ofSoftware，2016，27(6)：14751486(in Chinese)http：1wwwjosorgcn1000-98255002htmMulti-User Binary Tree Based

4、 ORAM SchemeSUN Xiao-Ni，JIANG Han，XU Qiu-Liang(School ofComputer Science and Technology，Shandong University，Jinan 250101，China)Abstract：With the development of big data and data mining technology,the access pattem becomes a risk of leaking users privacy inthe cloud computing environmentOblivious ran

5、dom access memory(ORAM)is an effective way to protect the userS access paRernTheexisting ORAMs mostly support a single userThe only ORAM supporting multi-user is based on the hierarchical ORAM including areshuffling phase that may cause high computational complexityIn order to avoid reshuffling，this

6、 paper designs a new multiuser ORAMbased on binary treeFirst，a proxy encryption scheme is improvedSecond，a proxy between users and the cloud server is introduced，Thedata encrypted by different users is encrypted again by the proxy to obtain the final ciphertext encrypted by the same key,and the fina

7、lciphertext is stored on the serverThe security of the scheme is based on the indistingnishability of the pseudorandom function，and theworst computational complexity and the amortized computational complexity are all O(1092n)，achieving higher efficiency than theexisting multiuser ORAM schemesKey wor

8、ds：cloud computing；binary tree；oblivious random access memory；multiuser；access pattern云计算作为一种新的计算方式，以其可靠性、共享性、方便性、隔离性、兼容性、低成本、高伸缩性等优势获得了迅速的发展(H】云计算在发展过程中面临着很多问题，其安全问题尤为突出J，已经成为用户衡量是基金项目：国家自然科学基金(61173139，61572294)；教育部博士点基金(201lOl311l0027)Foundation item：National Natural Science Foundation ofChina(61

9、173139，61572294)；PhDPrograms Foundation ofMinistry ofEducation ofChina(20110131110027)收稿时fnq：20150815；修改时间：2015-10-09；采用时间：20151205；jos在线出版时间：20160121CNKI网络优先出版：2016-0122 11：20：05，http：wwwcnkinetkcmsdetail112560TP201601221120014html万方数据1476 Journal of Software软件学报V0127，No6，June 20 1 6否使用云计算服务的一个重要因素

10、，获得了密码研究者极大的关注云计算的安全包括数据机密性、数据完整性以及隐私保护云存储数据的机密性可以通过现有的加密方案来获得云存储数据的完整性可以通过哈希函数、消息认证码、数字签名等来获得【61云计算的隐私保护包括身份隐私保护、查询隐私保护和访问模式隐私保护身份隐私保护可以通过匿名访问来实现；查询隐私保护可以通过安全索引、随机陷门等方法来实现；访问模式隐私保护可以通过动态数据结构、不经意随机存取等方法来实现随着数据挖掘技术的迅速发展，访问模式成为泄露用户隐私的一种潜在途径访问模式指的是在运行过程中所访问的地址序列【”2010年Pinkast8】指出服务器通过分析用户的访问模式，基于一定的背景知

11、识，可以推断出用户的部分隐私信息，如果服务器监测到用户连续进行特定的几次访问后，都会进行一次股票交易，那么，当用户发起相同或者相似的访问序列时，即使这些内容是加密的，恶意的服务器也可以以极高的概率推断用户将要进行一次股票交易，进而推断出这些序列的内容此外，服务器还可以统计用户每次访问返回的数据块的次数，推断出数据库中不同区域数据的重要程度由此可见，在云计算中，隐藏用户的访问模式对于保护用户隐私至关重要不经意随机存取(oblivious random access memory,简称ORAM)技术是隐藏用户访问模式的一种重要方法当执行一个普通的RAM程序时，ORAM可以将其转换为多个RAM步骤，

12、以达到不泄漏访问模式的目的最平凡的ORAM方案是当用户发起请求时，云服务器顺序读取每个数据项，发送给用户，然后用户再将每一个数据项重新加密后发布到云服务器，这样用户既获得了自己需要的数据，也使服务器不知道用户需要的是哪些位置的数据项，从而保护了用户的访问模式由于平凡的ORAM需要传输并加解密所有的数据项，因此，其计算复杂度和通信复杂度巨大，根本无法应用基于软件保护的背景，1996年Goldreich和Ostrovsky7】提出了两种非平凡的ORAM方案：平方根ORAM方案和分层ORAM方案，其中最高效的方案，对于刀个数据项，服务器端需要的存储空间为O(nlogn)，而访问每一个数据项，平均需要

13、O(1093n)次数据请求，最差的情况下需要O(nl092门)次数据请求由于该方案结构复杂，效率不高，因此ORAM技术在保护访问模式中的应用研究没有得到广泛的关注2010年，Pinkas8】描述了访问模式泄露对于用户隐私的危害，指出ORAM方案可以应用于访问模式保护，并改进了文献7】中提出的分层ORAM方案，提高了效率该方案中服务器端的数据是分层存储的，当用户访问某数据项时，服务器利用布谷鸟散列计算出该数据项对应每一层的两个位置，将这些位置存储的数据项发给用户，用户通过解密这些数据项，从而获取想要访问的数据内容，此后为了保证数据存储的随机性，用户还需要将这些数据项重新加密写回服务器，并进一步混

14、淆数据项的存储位置该方案的用户空间复杂度为D(1)，服务器空间复杂度为D(”)，平均计算复杂度为O(1092聍)，其中混淆操作最差情况下的计算复杂度为q行)，导致最差情况下的计算复杂度为O(nlogn)2011年，Goodrich和Mitzenmache9】发现Pinkas的方案在某些情况下，服务器可以高概率地获知用户的访问序列，因而他们提出了一种新的ORAM方案，该方案的空间复杂度和计算复杂度与Pinkas方案保持同一个数量级此后，分层ORAM方案得到了进一步的研究【l”J由于分层ORAM方案中混淆过程效率较低，为了避免混淆过程，2011年，Shi等人【14】提出了基于二叉树的ORAM方案在

15、该方案中，服务器端数据项以二叉树的形式存储，用户端存储一个索引表，当用户访问某数据项时，用户从索引表中读取到该数据项对应的叶子节点，从而得到包含该数据项的路径(从根节点到其叶子节点的通路)，并提供给服务器，服务器依次返回该路径上每一个数据项，用户通过解密数据项，可以获取想要访问的数据内容，此后为了保证数据存储的随机性，用户将他要访问的数据项重新加密后以新的路径存储到服务器，并且使用一个空数据项代替他想要搜索的数据项，与其他数据项一起重新加密后存储到原路径该方案的平均计算复杂度最好可达到O(1092nloglogn)，最差情况下的计算复杂度为O(1093nloglogn)，有效改进了最差情况下的

16、计算复杂度2013年Stefanov等人【15】采用树的思想，提出了Path ORAM方案，极大地改进了文献14】的方案，将计算复杂度改进为O(1092nlogc)，其中C是描述数据分块大小的参数但该文并没有对Path ORAM方案的安全性进行形式化证明，后期有很多学者基于Path ORAM方案进行改进，并给出形式化的安全证明【l 617J万方数据孙晓妮等：基于二叉树存储的多用户ORAM方案 1477在已有的绝大多数ORAM方案中，都是针对单一的用户，或者说多个相互信任的用户(共享秘密密钥)12,18】，但是云并不是为一个用户服务的，实现多用户的ORAM方案具有很强的应用背景2014年，Zha

17、ng等人【l 9J首次提出了真正意义上的多用户ORAM方案，该方案是基于分层ORAM方案设计的，通过在用户和服务器之间引入匿名器，借助代理加密机制，将不同用户加密的数据，通过匿名器再次加密为相同密钥加密的数据存储到服务器，为了防止单一匿名器权限过大，他们将单一匿名器设计为一系列串联匿名器Zhang等人【l 9】的方案中，用户的空间复杂度为D(1)；服务器端的空间复杂度为O(nloglogn)；在问询阶段，用户和匿名器的计算复杂度都是O(109nloglogn)；在混淆阶段，用户不需要参与，匿名器独立完成该过程，其计算复杂度为O(1093nloglogn)该方案进行安全证明时要求充当代理的多个匿

18、名器不能同时妥协本文提出了基于二叉树的多用户ORAM方案(binarytreebasedmultiuserORAM，简称BT-MORAM)本文方案中，服务器端采用基于二叉树的ORAM方案代替Zhang方案【l 9】中的分层ORAM方案，避免了最差情况下分层ORAM方案中混淆过程带来的堪玎)的高计算复杂度在本文方案的应用背景下，系统中的每一个用户都可以搜索所有用户的数据信息，不需要授权管理功能，因此本文只采用Dong等人【20】提出的代理加密方案，同时，为了降低代理端的空间复杂度，对Dong等人的方案进行了改进，代理端只需要保存代理主密钥(一个常数和一个哈希函数)就可以实现代理端密钥的计算，并不

19、需要保存每个用户对应的代理密钥本文提出的BT-MORAM方案在最差情况下的计算复杂度为O(1092胛)，比Zhang等人【l 9】的方案中混淆阶段最差情况下带来的j夏疗)有很大的改进；平均计算复杂度为O(1092玎)，比Zhang等人【19】的混淆阶段引起的平均计算复杂度O(1093疗loglog行)也要小1预备知识11基于二叉树的ORAM方案111 符号声明聍：需要存储的数据项数目D：构造的二叉树的深度D=J logn 1s：数据id每个数据项拥有唯一的id谚数据内容，：数据存储路径所对应的叶子节点P(，)：从叶子节点，到根节点这一条路径曰：数据明文，形式为B=(J，们B+：数据明文，形式为

20、B+=(s，dO上：空数据块，数据id为0，数据结构同正常数据0，坊相同index：索引表，用于存储每一个数据项的存储路径所对应的叶子节点，索引表项为(s，|)indexs：s数据项存储路径所对应的叶子节点的编号，xu：用户”f的密钥xf：用户Ui对应的代理密钥112基于二叉树的ORAM方案基于二叉树的ORAM方案【14】涉及两个主体：用户和服务器用户既充当数据发布者，又充当数据查询者，用户既可以发布自己的数据到云服务器上，也可以向云服务器发起搜索请求，访问自己的数据云服务器上数据以二叉树的形式存储，二叉树中的每个节点可以看做是一个独立的ORAM，每个节点ORAM可以存储O(109n)个数据项

21、ORAM的3种基本操作如下：ReadAndRemove(s)：当用户想要访问id为S的数据项时，首先查询本地索引表index，获得该数据项对应的叶子节点，然后产生一个随机D位的01串，+，将其存储在一个全局变量中，并将indexs改写为，+依次读取P(D路径上的每一个数据项，当读到S数据项时，记住其内容，并将其从该节点删除，用上代替，重新加密写回；当没有读万方数据1478 Journal of Software软件学报V0127，No6，June 20 1 6到S数据项时，将读出的数据项重新加密写回最后，如果找到了S数据项，返回其内容，否则返回上Add(s，力：首先，从全局变量中读取，是由前面

22、的ReadAndRemove(s)操作产生的，然后用户将(s，a,O写入根节点evict(w)：每个Add操作之后，都要进行该操作用户从服务器端二叉树的每一层随机选择W个节点进行数据下移操作对选择的每一个节点，用户选取一个数据项(如果该节点有真实数据项，随机选取一个真实数据项，用上代替原数据项；如果该节点都是上数据项，则选取上数据项)如果选取的是上数据项，用户向该节点的左右孩子节点均写入重新加密后的上数据项；如果选取的是真实数据项，根据该数据项对应的叶子节点，将真实数据项重新加密后写入e(O指定的那个孩子节点，并将上数据项重新加密后写入另外一个孩子节点注意：每次写入左右孩子节点的顺序是固定的O

23、RAM执行读或者写操作时，首先执行ReadAndRemove(s)，用户读取id为S的数据项0，d,O，并将数据项从二叉树中删除(如果需要改写数据内容，则修改回而后执行Add(s，回，将(s，a,t)重新写回二叉树12代理加密方案系统模型代理加密系统由系统初始化、密钥生成、用户加密、代理加密、代理解密、用户解密6部分组成，即Init(1“)，KeyGen(x，f)，UEnc(x?，埘)，PEnc(xf，彳(m)，PDec(xj，c(m)，UDec(x；，c：(m)形式化描述如下：系统初始化：可信的密钥分发中心执行，以妫安全参数，初始化系统，生成公开参数G，g炉以及秘密参数X记为Init(1)一

24、G，g，P，x密钥生成：可信的密钥分发中心执行，新加入用户U；时，生成用户密钥工7记为KeyGen(x，f)寸x7用户加密：用户使用密钥，加密明文m，生成一级密文Ci(m)记为UEnc(x?，m)一ci(m)代理加密：代理使用用户砷对应的代理密钥r，再次加密一级密文cj(m)，生成最终密文c(聊)记为PEnc(ff，ci(m)一c(埘)代理解密：代理使用用户uj对应的代理密钥x?，对密文c(所)进行解密，获得一级密文c：(m)记为PDec(x?，c(脚)_c：(脚)用户解密：用户吩使用密钥工；，解密一级密文c：(坍)，获得明文m记为UDec(xy，c：(肌)一m2代理加密方案BT-MORAM方

25、案中多用户的实现依赖于在用户与服务器之间引入一个代理，数据先通过用户进行初次加密，代理再次加密后变成统一密钥加密的密文，从而实现多个用户参与的ORAM代理重加密方案已经得到了广泛的研究，取得了大量的成果，新成果大多关注用户数据授权的研究，数据拥有者可以指定特定的数据使用者来解密被重加密的数据，这样可以提供更加灵活的应用方式，但相比于无授权的代理加密方案，其代价是牺牲了一定的效率在本文系统背景下，允许用户搜索系统中所有用户的数据，所以不需要涉及到授权，而且Dong等人20】的无授权代理加密方案为基础由于Dong等人的方案中代理端需要存储系统中每个用户的代理密钥，并不适合云环境下海量用户的应用场景

26、因此，我们改进Dong等人的方案，得到一种基于El Gamal机制的代理加密方案船，代理端只需要保存一个常数和一个哈希函数就可以实现代理密钥的计算，并不需要保存每个用户对应的代理密钥21代理加密方案Init(1。)：可信的密钥分发中心执行选取一个大素数g，选取一个循环群G,g是群G的生成元，公共参数是(G,g，g)从乙中任意选取一个f，取一个哈希函数(，)：Z。ZjZ。密钥分发中心把t和(，)发送给代理，作为代理主密钥从乙中选取一个x，作为秘密的主密钥KeyGen0，f)：可信的密钥分发中心执行用户U；加入系统时，密钥分发中心执行该算法执行哈希函数，得到x?=h(t，f)计算一u=xx?，将x

27、?发送给“，作为U，的密钥万方数据孙晓妮等：基于二叉树存储的多用户ORAM方案 1479UEnc(x?，m)：用户加密算法从乙中任取r来加密数据，使用撕的密钥x?对数据m进行加密ci(m)=(97，g耐研)，Uf将密文c：(埘)发送给代理PEnc(i，t，h(v)，c；(m)：代理加密算法代理接收到甜f加密后的密文c：(朋)，首先根据已有的t和|lz(，)，计算x7=h(t，f)代理使用密钥x7对cj(埘)再次进行加密，执行(g)彳g衅m=g“m，得到最终的密文c(m)=(97，g“m)，代理将c(所)发送到服务器端存储PDec(j，t，(，)，c(小)：代理解密算法假设c(埘)最终要发送给u

28、j，代理首先计算uj在代理端的密钥z?，然后执行g“研(97)一巧=g“；m，得到代理解密后的一级密文c：(埘)=(97，g叫m)，将c：(肌)发送给吩UDec(x；，c；(m)：用户解密算法uj使用自己的密钥x；对c：(m)进行解密，执行g唧m(g)一巧=m，吩最终获得数据明文m22安全性证明以上代理加密是基于El Gamal加密方案设计的，其安全性是基于DDH困难问题的在代理和用户不勾结的情况下，雎方案在选择明文攻击下是不可区分的(INDCPA)假设存在一个PPT敌手A，代理加密方案的CPA不可区分实验s勉如下：执行1nit(1)，获得公共参数(G，g，g)，代理主密钥f，散列函数(，)和

29、主密钥x执行KeyGen(x，f)，获得Ui的密钥x7敌手爿拥有代理主密钥t和矗(，)，并且可以访问用户加密预言机UEnc(x?，)，敌手输出两个合法明文mo和m1，发送给“f用户坼随机选取b f-01)，执行沈kc(，)，获得挑战密文0()=(97，g硝)，发送给A敌手爿继续访问用户加密预言机UEnc(x?，)，输出b下面，考虑存在一个PPT敌手彳，尝试解决DDH难题：参数G，g，q,91，92,93，t，(，)被发送给敌手彳，其中gI=ga 92=94，93僖7，g中)，其中，屈堤随机选取的，敌手爿把G，g，q，t，(，)发送给敌手爿敌手爿计算g芹=91g山“ 当敌手爿访问用户加密预言机的

30、时候，都把明文m发送给敌手A4执行r士乙，返回(97，g嘶m)当敌手彳输出两个明文mo和m1时，敌手爿7执行6士0，1)，把(92，g；”力93m6)发送给敌手A，作为其挑战密文敌手彳会输出6f如果b=b4输出1；否则4输出0以下分两种情况进行讨论：若g，=97，由于堤随机选择的，所以93是群G中一个随机的元素g；6中也不包含m6的任意信息所以敌手A并没有关于m5的任何额外信息，所以有PrA(G，g，q，t，矗(，)，gl，92，97)=l】=12 (1)若93=g印，可以计算出g(t,093m6=g-4h(t,Og印m6=g(-h(tO)m6=g肼m6，(92，酊h(t,093m6)可以化简

31、成(94，ga4m。)，是PE方案的合法密文，所以有PrA(G，g，q，t，厅(，)，gl，92，g舻)=1】=s：刍 (2)由于DDH问题是困难的，所以有PrA(G，g，q，t，(，)，gl，92，g掣)=l卜PrA(G，g，q，t，矗(，)，gl，92，97)=1】negl (3)根据式(1)式(3)可以推出s您negl+l2因此，代理加密方案朋在选择明文攻击下是不可区分的万方数据14803基于二叉树存储的多用户ORAMJournal of Software软件学报V0127，No6，June 2016BT-MORAM方案包括3个主体：用户、代理和云服务器假设存在一个可信的密钥分发中心负责

32、各种初始化工作可信的密钥分发中心会给每个加入系统的新用户分配一个密钥，给代理分发代理主密钥，用以计算每个用户对应的代理密钥服务器端采用二叉树的形式存储密文【14】，每一个节点都是一个独立的ORAM，节点ORAM可以是任何形式的ORAM，比如Goldreich和OstrovskytTj提出的平方根ORAM、分层ORAM，或者Damgard2q提出的基于二叉搜索树的ORAM，更甚至说仅仅是一个平凡的ORAM考虑到现实背景以及本文方案描述的简洁、清晰，本文详细介绍节点为平凡ORAM的BTMORAM方案当用户要上传数据到不可信的服务器时，首先用户用自己的密钥加密数据，将加密后的一级密文发送给代理，代理

33、在不解密的情况下，再次加密，从而获到最终的密文，将其发送给服务器存储在单用户的基于树的ORAM方案中，当用户需要查询一个数据项时，首先需要检查本地索引表，在多用户场景下，数据使用者检索的数据可能来自于多个数据拥有者，这时，如果依然由各个数据拥有者维护自己的索引表，必然带来应用的不便，因此我们建立了一张联合索引表，记录所有用户的数据索引，并将此索引表存储于代理端系统模型如图1所示index 器Fig1 System model图l系统模型31平凡的节点。删本文BT-MORAM方案中，二叉树节点采用平凡的ORAM方案，存储能力为D(109n)由于在用户与服务器端之间引入一个代理，使用第21节中描述

34、的代理加密方案完成数据加密存储，所以，节点ORAM的操作涉及到用户和代理两方的加解密过程平凡ORAM提供两种ORAM操作：bucketRead4ndRemove(s)：用户在该节点搜索s数据项，顺序读取服务器端这个节点的每一个数据项，发送给代理，代理解密后发送给用户，用户再次解密获得明文当读到id为s的数据项时，用户记下这个数据内容，并用上代替s数据项：如果读到的数据项不是s，则保留原数据项用户重新加密数据项发送给代理，代理再次加密后写回该块具体操作见算法1bucketAaa(s，们：逐个读取服务器端该节点的数据项，发送给代理，代理解密后发送给用户，用户再次解密获得明文当第1次读到J-时(数据

35、id为0)，将要插入的数据项加密后发送给代理，代理再次加密后写入该块，其余情况，只需要用户和代理共同加密原内容写回该块即可具体操作见算法2算法1bucketReadAndRemove(s)输入：要搜索的数据项的数据id为s：输出：j数据项对应的数据内容01：data-l万方数据孙晓妮等：基于二叉树存储的多用户ORAM方案02：for(every block ofthis node)03：proxy卜(gr，g“5，g“d)04： c；(s)卜(97，g科s)卜朋PDec(i，t，(，)，(97，g“J 7) 请求是Uf发出的05： c；(d)一(97，g硝d)-PE，Dec(i，t，(，)，(

36、97，98d)06： “，-(gr,g rXPs，g,rd)07： 0，d)卜(PEUDec(x?，(97，g耐s)，PEUDec(x?，(g，g衅d)08： if(s习)09：data卜(s，d)10： (J，吐)卜上11： else12： (s，4)卜(s,d)13： endif14： cT(s，)-(g，g耐s，)卜PEUEnc(x7，s，)15： ci(dr)卜(97，g,Xp吐)卜阳UEnc(x?，矾) 两次加密取同一个，16：proxy-(97，g耐s，g耐吐)17： (97，gHs，)-PEPEnc(i，t，(，)，(97，g酵s，)18： (97，g履4)一PEPEnc(i，r

37、，(，)，(97，g耐4)1 9： write堪。矿sI。矿da back to this block20：endfor2l：return data算法2bucket彳aa(s，奶输入：待插入的新数据(J，回；输出：将新数据写入服务器。返回数据d0l：for(every block)02：proxy一(97，g“s，g“d)03： c；(J)-(97，g耐s)卜艘PDec(i，t，Il(，)，(97，g“5)请求是l，f发出的04： c；(d)一(97，g衅d)卜PEJDec(i，t，|Il(，)，(97，g珂d)05： “i-(gr，grxUs，gH?d)06： (j，d)(PEUDec(x

38、?，(97，g=rs)，船UDec(x7，(g，grd)07： if(the first time s=0)即第1次读到上块08： (s，4)卜(J，d)09： else10： 0，4)卜0，d)ll： end if12： c；(s，)-(g，g钟Jf)卜朋UEnc(x?，s，)13： c?(吐)-(97，g衅吐)卜PEUEnc(x7，吐)两次加密取同一个，14：proxy卜(97，g彬s，g聊4)15： (g，g肛J，)一PEPEnc(i，t，(，)，(97，g对j，)148l万方数据1482 Journal of Software软件学报V0127，No6，June 201616： (gr

39、，g“吐)卜雎PEnc(i，t，(，)，(97，g唧4)1 7： write 09r。窖xslgxda back to this block18：endfor19：returnd32基于二叉树的多用户ORAM方案系统初始化可信的密钥分发中心首先执行雎Init(1)，然后选择一个伪随机发生器只，可以输出D位的伪随机串当一个新用户Ur加入系统时，这个可信的密钥分发中心会执行朋KeyGen(x，f)给U，发送一个密钥数据发布每个用户会发布自己的数据到服务器端，以便其他用户查找比如，用户U，要发布新的数据0，力到服务器端数据发布时，都是写入根节点首先，代理执行伪随机函数E得到，把P(O作为新发布数据的

40、初始存储路径，并将，)作为一个索引表项存储在联合索引表index中然后，对根节点执行bucketReadAndRemove(s)，返回给蜥的数据一定为上，因为S是唯一的，这是第1次写入id为s的数据最后，对根节点执行bucketAaa(s，们，从而实现将数据(s，们以密文的形式存储在服务器端数据搜索用户uj要搜索一个id为S的数据项(注：s数据项可以是系统内任意一个用户发布的)，具体过程如图2所示。，H。一 bucketRead and RemoveO)L。1。1。1。一。，。!I!：一 bucketAddO，d)Fig2 Data search process图2数据搜索过程(a)获取s数据

41、项的存储路径获取s数据项的存储路径：用户给代理发送数据id s，代理查询本地索引表index，获得S数据项对应的叶子节点，从而获得S数据项的存储路径P()代理更新索引表index：代理执行伪随机函数F，获得，0数据项的新存储路径为P(，)，将代理本地索引表index中S数据项对应的索引表项更改为(5，)(b)搜索S数据项，并删除S数据项：对于路径P(，)上的每一个节点，执行bucketReadAndRemove(s)操作如果存在id为J的数据项，那么，一定在操作执行过程中获得了s数据项的内容，并且将s数据项从服务器端删除，万方数据孙晓妮等：基于二叉树存储的多用户ORAM方案 1483算法返回的

42、数据就是S数据项的内容如果不存在id为S的数据项，算法返回的数据是上(C)将S数据项重新发布到服务器：返回的数据项0数据项或者J-)的存储路径已经在(a)中更新为P(I+)，对根节点执行bucketReadAndRemove(s)和bucketAaa(s，cO将数据项写入根节点(d)数据下移：对0Dl层的每一层”，都执行以下操作：从第r层中任意选取两个节点(取w=2)，对于每个节点：选取要下移的数据项：服务器将该节点中的所有数据项依次发送给代理，执行PEPDec(，)，获得一级密文发送给用户，用户执行PEUDec(，)，获得数据明文如果该节点都是上数据项，则选取上数据项，记为B4=上；如果该节

43、点存在真实的数据项，任意选取一个真实数据项，记为曰4，并从该节点中删除该数据项用户执行PEUEnc(，)加密数据项，获得一级密文c+“)，把，c+8)发送给代理确定下移路径：代理根据54查询本地索引表index，获得s“数据项对应的叶子节点，从而获取数据的存储路径P(广)；若没有查询到对应的索引表项，说明曰4是上，此时随机选取一个D位的01串，作为，代理执行PE艘珂c(，)再次加密c(B4)，获得最终密文c(B。)下移到孩子节点：若广的第n+l位为O，把c(B4)写入左侧孩子节点，把上写入右侧孩子节点；若，的第n+l位为1，把上写入该节点的左侧孩子节点，把c(B8)写入该节点的右侧孩子节点4方

44、案分析41安全性分析BT-MORAM方案的目的是在实现多用户的前提下，隐藏访问模式第32节中描述的BT-MORAM方案记为n，将n中的伪随机函数F改为真随机函数苁输出一个D位的真随机0l串)变成新的方案n存在一个PPT敌手彳攻击方案兀，敌手彳腐蚀一个用户甜。，挑战者由未被腐蚀的用户和代理充当一算法如下：初始化：可信密钥分发中心首先执行阳Init(1。)，然后选择个伪随机发生器只输出D位的伪随机串，最后，可信密钥分发中心执行船KeyGen(x，a)和朋KeyGen(x，c)，U。和U。分别获得密钥和x；问询：敌手彳腐蚀用户“。，可以让Ua搜索任意数据项；让甜。搜索任意一个没被搜索的数据项及访问一

45、个已经被搜索的特定的数据项请求：敌手彳让U。随机搜索一个数据项，记为So；敌手A让甜。再次随机搜索一个数据项，记为S1问询：敌手4可以让U。搜索任意数据项；让材。搜索任意一个没被搜索的数据项及搜索So或Sl数据项挑战：挑战者随机选取b七一0，1，Uc搜索岛数据项问询：敌手爿可以让U。搜索任意数据项；让U。搜索任意一个没被搜索的数据项及搜索S6或S1曲数据项应答：敌手爿输出b敌手4攻击方案兀时，由于节点采用平凡的ORAM方案，因此节点ORAM是安全的当任意一个用户发起一个搜索请求时，代理会通过联合索引表index查询数据的存储路径尸(，)步骤(a)从步骤(a)可以看出，任意一个，都是由真随机函数

46、厂选取的一个随机的D位01串，因此步骤(b)访问的节点可以看做是随机访问一条路径上的所有节点步骤(c)中，对根节点进行写操作，由于节点ORAM是安全的，所以步骤(c)也是安全的步骤(d)中，下移数据时，左右孩子节点都会被重新加密的数据写入，所以也不会泄露任何信息用户之间是完全独立的，没有任何密钥共享或者交流整个过程中，彳的视图是一样的，并没有Jo和Jl数据项任何额外的信息，所以=12下面，假设存在一个PPT敌手爿，试图区分伪随机函数F与真随意函数fA可访问预言机()：问询：当爿让U。随机搜索一个数据项时一会访问O()，产生新的叶子节点，并将路径P(O(I是以前爿7访问()产生的)上的数据返回给A挑战：当4已经搜索So和s1后4任意选取b卜0，1)，访问()，获得新叶子节点，让U。搜索S6数据项万方数据1484 Journal of Software软件学报V0127，No6，June 2016问询：敌手A可以让Ua搜索任意数据项，通过彳7访问()，选取新叶子节点，应答：彳输出6，如果b=b4输出1；否则4输出0以