, 徐紫枫东北大学 软件学院, 辽宁 沈阳 110169
收稿日期：2017-04-12
基金项目：国家自然科学基金资助项目(61772127, 61472184);国家科技重大专项(2013ZX03002006)；辽宁省科技攻关项目(2013217004)；中央高校基本科研业务费专项资金资助项目(N151704002)。
作者简介：李宇溪(1990-)，女，辽宁朝阳人，东北大学博士研究生;
周福才(1963-)，男，吉林长春人，东北大学教授，博士生导师。
摘要：围绕当前云存储环境中用户数据机密性和隐私泄露问题, 提出一个隐藏访问模式的高效安全云存储方案.该方案首先将文件分为固定大小的数据块, 利用伪随机函数和抗碰撞哈希函数将数据块编码、加密, 并将密态数据块上传至云服务器的伪随机集合超集内, 构建安全云存储结构; 同时, 设计两轮用户访问策略, 在隐藏访问模式的同时降低了存储代价和访问交互次数, 实现文件的动态高效更新.安全分析表明, 选择适当的安全参数, 方案满足L1L2-动态自适应安全性.实验结果表明, 本方案在保证数据机密性的同时, 更适用于实际的云存储环境.
关键词：云存储访问模式伪随机函数抗碰撞哈希函数机密性
An Efficient and Secure Cloud Storage Scheme with Hidden Access Patterns
LI Yu-xi, ZHOU Fu-cai
, XU Zi-fengSchool of Software, Northeastern University, Shenyang 110169, China
Corresponding author: ZHOU Fu-cai, E-mail: fczhou@mail.neu.edu.cn
Abstract: Aiming at the problems of data confidentiality and user's privacy leakage in cloud, this paper proposes an efficient and secure cloud storage scheme with hidden access patterns. Firstly, the files are divided into data blocks with fixed sizes, and encrypted by pseudo-random functions and collision-resistant Hash functions. Then, in order to construct the secure cloud storage structure, the blocks are uploaded into pseudo-random collection superset in the cloud server. Meanwhile, a two-round access strategy that hides the access patterns, reduces the storage cost and access interaction is designed. Security analysis shows that the proposed scheme achieves L1L2-dynamic adaptive security. Experimental results show that the proposed scheme can not only protect data confidentiality, but also be more suitable for the actual cloud storage.
Key words: cloud storageaccess patternpseudo-random functioncollision-resistant Hash functionconfidentiality
面对大数据和物联网等应用环境中的多元化需求, 数据不再像传统信息系统一样采用集中式的存储, 云存储等新模式被广泛应用, 吸引了越来越多企业和个人用户的关注和使用; 然而现有的云存储服务在数据安全保护方面存在严重不足, 很多潜在的云存储用户会因为担心数据泄露而不得不使用传统的存储服务, 这在很大程度上阻碍了云存储服务的推广.
为了能够让用户放心地将数据存储在云服务器, 加密成为确保数据存储安全的隐私保护手段; 但是, 加密不能保护云存储中数据的访问模式, 即用户访问的数据在云存储中的位置、大小以及访问频率等信息, 而访问模式通常也蕴含了用户的隐私信息, 已成为泄露用户隐私的一种潜在途径.文献[1]指出, 基于频率统计的攻击方式, 通过分析访问模式能够成功地推断一个加密邮件库搜索内容的概率大约为80%.由此可见, 在云存储环境中, 隐藏访问模式对于保护用户数据隐私十分必要, 因此, 急需一种高效、安全的云存储方法，能够在不可信环境中对访问模式进行有效保护.
本文从保护数据隐私的角度出发, 针对不可信的云存储环境, 提出隐藏访问模式的高效安全云存储方案.该方案首先将文件拆分成固定大小的数据块并进行编码、加密, 利用伪随机函数将密态数据块上传至云服务器的伪随机集合超集内, 构建安全云存储结构; 同时, 针对用户的上传、下载以及更新文件等操作, 设计两轮访问策略, 访问过程中服务器无法获得文件个数、大小以及访问频率信息, 在隐藏访问模式的同时实现文件的动态高效更新.
1 相关工作目前能够实现隐藏访问模式的方法主要有隐私信息检索(private information retrieval, PIR)[2]和不经意随机存取(oblivious random access memory, ORAM).近年来, 许多学者将PIR的安全模型进行扩展, 提出了SPIR模型[3-4], 即不仅仅考虑单方的隐私问题, 而且要求协议双方都不能获取另一方的访问模式.PIR协议计算复杂度较高且均面向明文数据, 即假设云服务器是可信的, 因此不满足本方案的安全模型.
ORAM最早由Goldreich在1987年提出[5], 其目的并非用于保护用户的隐私, 而是用于防止逆向工程等软件的攻击.2013年, Stefanov等人提出了面向轻量级客户端的ORAM方法——PathOram[6].2016年, 孙晓妮等人在基于二叉树ORAM方案的基础上, 构造了一个多用户的ORAM方案[7], 但目前ORAM方法仍存在很多问题, 因而, 需要一种高效安全的云存储方法，能够在不可信环境中对访问模式进行有效的保护.
2 方案模型图 1所示为方案的架构图.方案包括两个类型的实体:用户和云服务器.其中, 用户为数据的拥有者, 云服务器向用户提供数据存储服务.在本场景中, 数据以文件形式进行组织, 用户将文件进行处理并加密, 外包至云服务器进行存储, 随后用户可以对云服务器中的存储结构进行访问.
图 1(Fig. 1)
 | 图 1 方案架构Fig.1 Scheme architecture |
2.1 形式化定义本方案主要由以下5个多项式时间算法或协议组成:
K←KeyGen(k):密钥生成算法, 运行于用户端, 用于生成用户在方案进行中所需的密钥.算法输入安全参数k, 输出密钥集合K.
D←Build(K, d0, {idi, datai}i=1t):构建算法, 运行于用户端, 主要用来构建存储结构.算法输入密钥K、系统中存储数据块的总数量上限d0、文件数据datai和文件标志idi，输出存储结构D.
(S:D′)←Upload(U:idf, dataf, sizef, K; S:D):上传协议, 主要用于完成向存储结构中写入文件数据.用户端输入文件标志idf、数据dataf和文件大小sizef, 服务器端输入存储结构D, 服务器端输出一个新的存储结构D′.
(U:Data)←Download(U:idf, K; S:D):下载协议, 主要用于完成从存储结构中读取文件数据.客户端的输入为文件标志idf和密钥K, 服务器端输入存储结构D.客户端输出文件内容Data.
(S:D′)←Update(U:idf, dataf, K; S:D):更新协议, 主要用于更新存储结构中的文件内容.客户端输入文件标志idf和密钥K, 服务器端输入存储结构D, 服务器端输出更新后的存储结构D′.
2.2 安全性定义本文定义L1L2-动态自适应安全性.假设服务器为一个诚实并好奇的敌手, 即其会试图获取用户数据, 具有从存储结构和访问协议两个过程中不断分析用户数据的能力.自适应指敌手可以根据之前的质询结果来发起新的质询, 拥有更大的攻击能力.定义RealA(k)为敌手A和用户之间的交互式实验, 使用真实的方案算法.定义IdealA, S(k)为敌手A和一个有状态的模拟器S之间的交互式实验.L1L2-动态自适应安全性指的是, 存在模拟器S, 使得任何具有多项式时间计算能力的敌手都无法区分viewReal和viewIdeal.
定义1??L1L2-动态自适应安全性:令A为一个有状态的敌手, S为一个有状态的模拟器, L1, L2分别为初始化构建阶段和访问阶段(包括上传、下载以及更新)的泄露函数.考虑以下两个实验:
 |
 |
3 隐藏访问模式的高效安全云存储方案3.1 设计思路方案主要分为构建存储结构和动态访问两部分.在构建存储结构时, 用户首先要对上传至服务器的文件进行处理, 将每个文件转换成多个固定形式的数据块格式并进行加密, 然后存放在云服务器存储结构的随机位置上; 之后用户可以对存储结构进行动态访问, 包括下载文件、上传新文件及更新文件等.在下载过程中, 用户需要对服务器进行两轮访问, 从云服务器的存储结构中读取出想要查找的文件所对应的数据块, 并对其进行解密和整合, 最终得到完整的文件内容; 更新文件则在两轮访问的基础上, 对文件进行修改并重新上传到云服务器中随机位置.
3.2 详细算法与协议方案选择完全定义域抗碰撞哈希函数H, 伪随机函数F, 完全定义域伪随机函数P和一个伪随机生成器G.设存储空间D中数据块的个数为nD, 每个数据块的大小为mD.其中为了解决数据块存储中可能出现的冲突问题, 引入了膨胀参数α来生成比实际数据块个数大的随机序列, 并且将每轮交互中的最少操作数据块个数设置为κ.
1) KeyGen(k):密钥生成算法.算法输入安全参数k, 生成伪随机函数F的密钥kF以及完全定义域伪随机函数P的密钥kP, 得到存储结构的密钥K=(kF, kP).
2) Build(K, d0, {idi, datai}i=1t):构建算法.用于初始化构建存储结构.算法的主要步骤如下:
设文件集合为{idi, datai}i=1t, 其中任意一个文件f={idf, dataf}, idf为文件标志符, dataf为文件内容.对dataf进行分块处理, 每一个数据块都具有两个短头部域:包括初始化为0的版本号和H(idf).除此之外, 第一个数据块需要多保存一个头部域以存储记录文件包含的数据块个数sizef.
对于文件列表中的每一个文件f:
① 利用idf、伪随机函数P和对应的密钥kP, 生成伪随机生成器G的种子σf=PkP(idf)；
② 将种子σf作为伪随机生成器G的输入, 在得到的伪随机序列中选取序列长度为max(|α·sizef|, κ)的前段作为Sf；
③ 选择大小为sizef的伪随机子序列
④ 对文件的每个数据块进行处理:对于第i个数据块D[i], 将其表示为vi‖B[i](vi是版本号), 使用伪随机函数F和密钥kF处理B[i], 将B[i]更新为B[i]⊕FkF(vi‖i).
最后将构建好的存储结构D上传至云服务器.
3) Upload(U:idf, dataf, sizef, K; S:D):上传文件协议.主要步骤如下:
用户:在已知文件标志idf, 文件内容dataf和文件大小的情况下, 利用构建算法构建大小为sizef的数据块, 发送至云服务器.
服务器:接收到sizef个数据块后, 将其按照
4) Download(U:idf, K; S:D):下载文件协议.协议的主要步骤如下:
用户:利用文件标志idf和密钥kP, 计算σf=FkF(idf), 并定义大小为κ的集合Sf0, 其包括了序列Λ[σf, κ]中前κ个整数, 并向云服务器发送检索Sf0数据块的请求.
服务器:按照在Λ[σf, κ]中的顺序将D[Sf0]返回给用户U.
用户:对返回的数据块进行解密, 得到D[i]=(vi‖B[i]).找到一个标志为idf的数据块, 并从其头部域恢复出文件的大小sizef.令l=?α·sizef?, 如果l＜κ, 设Sf = Sf0, 否则设Sf为在Λ[σf, l]中整数的集合.最后向云服务器请求返回数据块集合D[Sf/Sf0].
服务器:将数据块集合D[Sf/Sf0]返回给用户.
用户:解密通过Sf被检索的剩余的数据块D[Sf/Sf0].设
5) Update(U:idf, dataf, K; S:D):更新文件协议.用于完成客户端用户U更新云服务器中某个文件的内容.协议的主要步骤如下:
用户:执行步骤4)，将待更新的文件idf下载到本地, 随后对文件内容进行修改和更新, 命名为data′.同时对新内容data′分块编码为size′f个数据块.
① 选择Sf中一个大小为size′f的子集S′f?Sf, 在序列Λ[σf, l]中找到包含size′f个数据块的一个最短前缀, 并且将这些数据块都标记为属于idf(即存在于
② 对所有通过Sf检索到的数据块进行处理.即对于第i个数据块D[i], 首先将版本号vi加1, 使用伪随机函数F和密钥kF处理B[i], 将B[i]更新为B[i]⊕FkF(vi‖i), 最终将数据块表示为更新后的vi‖B[i].
③将加密后的数据块发送给云服务器S.
服务器:将接收到的数据块更新到D中通过
4 安全性证明针对存储结构构建阶段和访问阶段, 分别定义两个泄露函数L1和L2来描述在方案执行期间向服务器泄露的信息.具体内容如下:
1) 构建阶段.此阶段用户通过输入密钥K以及(d0, {idi, datai}i=1t)生成数据块数组D, 并且将数据块数组D发送给服务器, 在此过程中, 服务器得到的信息为d0, 即存储的数据块的总数量的上限.将此信息记为L1, 即L1((d0, {idi, datai}i=1t))=(d0).
2) 访问阶段.此阶段服务器能够获得的信息主要分为以下三类:①服务器可以获得用户当前进行访问的操作op; ②在某次访问质询过程中, 当前需要操作的文件在之前最后一次被访问的情况j, 如果j=0, 则认为此文件之前没有被访问过; ③在某次访问质询中, 被访问的文件大小size.将这些信息记为L2, 即L2(id, op)=(op, j, size).除此之外, 定义存储松弛参数γ, 即服务器中数据块的数量nD与文件被分块处理后的数据块的数量的比值.需要注意的是，γ会随着文件的添加(或更新成更大的)而减小, 随着文件的删除(或者更新成更小的)而增大.
定理1??若伪随机函数F, P和伪随机生成器G具有CPA安全性, 哈希函数H具有抗碰撞性, 且方案保证γ至少为2/(1-1/α), 并且nD≥κ=ω(logk), 则本方案在标准模型下针对诚实并好奇的敌手具有L1L2-自适应安全性.
证明??本文构造如下游戏序列来证明任何具有多项式时间计算能力的敌手都不能区分真实的和理想的实验.
游戏1:这个游戏对应一次真实实验RealA(1k)的执行, 用户利用敌手提供的文件数据进行存储结构构建, 对于任意文件f=(idf, dataf), 利用伪随机函数P和哈希函数H对其进行分块处理，σf=PkP(idf), 并利用伪随机函数F对数据块进行加密.然后将包含所有文件的数据块的存储结构D发送给敌手.再后, A向用户发起至多q次的质询, 其中q为多项式级.在所有q次质询结束后, A所收集到的所有信息构成了viewReal.A最后输出一个比特作为整个实验的输出.
游戏2:游戏2与游戏1相同, 除了以下内容:在构建存储过程中, 与敌手交互的不是真正用户, 而是一个模拟器S.在初始化过程中, S不能利用伪随机函数P、哈希函数H以及伪随机函数F来生成真正的加密数据块, 而是利用泄露函数L1的内容, 并通过D的大小nD, 构建模拟包含加密数据块的D′; 它通过挑选均匀随机比特串来模拟D中数据块的内容, 其中D′中每个数据块的版本号都设置为0.
如果伪随机函数P以及伪随机函数F的伪随机性成立, 哈希函数H的抗碰撞性成立, 则对于所有多项式时间计算能力的敌手A,
 |
游戏3:这个游戏对应于一次理想实验IdealA, S(1k)的执行, 与游戏2的区别为，与敌手交互的模拟器用到的信息全部为泄露函数L2的内容.除此之外, 另一个区别是异常中止, 在之前的游戏中, 用户在伪随机子集中不能找到足够的空闲数据块时方案会中止, 然而模拟器则不会中止.
如果方案保证存储松弛参数γ≥2/(1-1/α), 并且nD≥κ=ω(logk), 则对于所有多项式时间计算能力的敌手A,
 |
情况1:j=0, 那么S会在[0, nD]的范围内选取一个由l个不同的整数组成的随机序列, 记为Λj*.
情况2:j＞0, 如果|Λj|≥l, 设置Λj*=Λj; 否则j＞0, |Λj*|＜l, 将Λj扩展成长度为l的随机序列，记为Λj*.
接下来, S创建模拟view, 即服务器首次接收到通过Λj*得到的首个κ条目所检索到的要下载的κ个数据块; 如果l＞κ, 则下载通过Λj*中的下一个条目所检索到的数据块.而对于读以外的操作, 应该紧接着上传一个新版本(包括数据块版本号的递增, 以及作为内容的新的随机字符串), 这个新版本是通过Λj*中的首个l条目所检索到的数据块的新版本.
方案满足(d/nD)≥2/(1-1/α), 即1-2(d/nD)≥1/α.因此, 除了可忽略概率, 对于选择|Sf|个数据块, 有(1-2(d/nD))≥sizef个空闲数据块.同理, Sf0至少会有|κ/α|个空闲数据块.所以, 用户向存储结构中写文件时方案异常中止的概率是可忽略的，即ε2是可忽略的.
综上所述, 对于所有敌手A, 实验RealA(1k)与实验IdealA, S(1k)的输出是一致的, 除了可忽略的概率negl(k)，即
 |
5 性能分析5.1 方案评估与对比将本文构建的方案进行全面的性能评估, 并与近几年经典的能隐藏访问模式的ORAM方案[6-9]进行效率对比分析，结果见表 1.
表 1(Table 1)
 表 1 不同方案的性能对比Table 1 Performance comparison of different schemes
| 表 1 不同方案的性能对比 Table 1 Performance comparison of different schemes | |||||||||||||||||||||||||||||||||||||||||||||||||
表 1对比分析了本方案与其他方案的各个指标, 从表中可以看出：安全性方面, 本方案主要抵抗半可信服务器; 通信代价方面, 客户端与服务器交互时的通信代价为O(B), 与数据块大小相关, 相较于文献[6, 8, 9]的方案来讲, 本方案的通信代价并非与文件总数量直接相关, 通信负担较小; 除此之外, 在存储代价方面, 相较于文献[6, 9]提出的方案, 本方案对服务器端预计客户端的存储代价进行了改进.值得说明的是, 本方案无需本地存储任何文件相关数据, 仅需存储密钥等参数, 释放了本地存储空间; 而且相较于其他所有方案, 本方案没有ORAM特有的洗牌过程, 并且无需服务器对数据本身进行任何计算, 降低了服务器的计算代价.
5.2 实验分析本文对方案进行了实验分析.实验使用了2015年最新版本的Enron数据集, 在邮件集中选取3 000个邮件作为实验文件集合.分析结果如图 2所示.图 2a表明, 随着文件数量的增多, 系统构建存储耗时增加, 但增幅较小.文件大小对上传文件耗时的影响如图 2b所示.从图 2c可以看出, 文件体积越大，下载耗时越长, 并且A类文件和B类文件的下载耗时相差较大, 而B类、C类、D类文件的下载耗时相差较小且增幅较缓.更新内容大小对更新文件耗时的影响如图 2d所示, 随着更新内容的增加，更新耗时也不断增加, 但增幅较小.综上所述, 本文提出的隐藏访问模式的高效安全云存储方案在时间上有良好的效率, 具有较高的实际应用价值.
图 2(Fig. 2)
 | 图 2 本文方案的实验分析Fig.2 Experimental analysis of the proposed scheme (a)—构建存储耗时；(b)—上传文件耗时；(c)—下载文件耗时；(d)—更新文件耗时. |
6 结语本文提出的隐藏访问模式的高效安全云存储方案, 既能解决云存储系统中的数据机密性问题, 又能抵抗访问模式泄露.方案设计二层访问协议, 使得用户在不泄露访问模式的前提下, 实现对于文件的高效上传、下载及更新, 降低了存储代价和访问交互次数.安全性方面方案满足L1L2-动态自适应安全性.性能对比分析与实验结果表明, 本方案的提出对于当前云存储中的数据安全问题有一定的理论意义和实际应用价值.
参考文献
| [1] | Cao N, Wang C, Li M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 222–233.DOI:10.1109/TPDS.2013.45 |
| [2] | Chor B, Goldreich O, Kushilevitz E, et al.Private information retrieval[C]// Proceedings of the 36th Annual Symposium on Foundations of Computer Science.New York: IEEE, 1995: 41-50.http://dl.acm.org/citation.cfm?id=795662.796270 |
| [3] | Jarecki S, Jutla C, Krawczyk H, et al.Outsourced symmetric private information retrieval[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security.New York: ACM, 2013: 875-888.http://dl.acm.org/citation.cfm?id=2516730 |
| [4] | Hazay C, Zarosim H.The feasibility of outsourced database search in the plain model[C]//International Conference on Security and Cryptography for Networks.[S.l.]: Springer International Publishing, 2016: 313-332.https://link.springer.com/chapter/10.1007/978-3-319-44618-9_17 |
| [5] | Goldreich O.Towards a theory of software protection and simulation by oblivious RAMs[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing.New York: ACM, 1987: 182-194.http://dl.acm.org/citation.cfm?id=28416 |
| [6] | Stefanov E, van Dijk M, Shi E, et al.Path ORAM: an extremely simple oblivious RAM protocol[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security.New York: ACM, 2013: 299-310.http://dl.acm.org/citation.cfm?doid=2508859.2516660 |
| [7] | 孙晓妮, 蒋瀚, 徐秋亮. 基于二叉树存储的多用户ORAM方案[J].软件学报, 2016, 27(6): 1475–1486. ( Sun Xiao-ni, Jiang Han, Xu Qiu-liang. Multi-user binary tree based ORAM scheme[J].Journal of Software, 2016, 27(6): 1475–1486.) |
| [8] | Ren L, Fletcher C W, Kwon A, et al.Ring ORAM: closing the gap between small and large client storage oblivious RAM[J/OL].[2017-01-15].http://citeseerx.ist.psu.edu/viewdoc/download?doi=1<0.1.1.691.5259&rep1&type=pdf. |
| [9] | Devadas S, van Dijk M, Fletcher C W, et al.Onion ORAM: a constant bandwidth blowup oblivious RAM[C]//Theory of Cryptography Conference.Berlin: Springer Berlin Heidelberg, 2016: 145-174.https://link.springer.com/chapter/10.1007/978-3-662-49099-0_6 |
