随着大数据与云计算技术的发展, 越来越多的数据可以在云端进行存储、计算以及共享.但是这也带来了一系列安全问题, 例如:个人用户如果直接将敏感数据以明文形式存储在云服务器, 那么对于不可信的云服务提供商或者其他攻击者可以直接获取用户的隐私信息, 并通过数据挖掘的方式推测用户的其他个人信息.因此, 为了保证用户的隐私数据不被恶意的窃取, 传统的手段是对数据内容进行加密, 密钥由用户个人持有.用户通过上传、下载密文数据来保护个人的隐私信息不被泄露^{[1, 2]}.

但是事实上, 加密只能保证数据内容的机密性, 却不能保证其他的隐私信息不被泄露^[3].在云存储场景中, 用户需要查询某一个数据块的内容.为了保证数据隐私性, 通常会对数据库中的数据进行加密.但是在执行查询请求的过程中, 数据块的索引并不能加密, 这就泄露了用户访问数据库元素的位置.这使得攻击者可以通过用户的访问模式(access pattern)来推断存储数据的重要性, 例如统计每一个数据块的访问频率; 同时, 攻击者还可以通过匹配前后两个连续的访问模式来推断数据查询之间的关联关系^[3], 甚至是加密数据的内容^[4].在实际场景中, 这些信息潜在性地暴露了用户的行为特征、兴趣爱好、社交范围等, 例如, 一个人查询某一类药物, 可以推断他患有什么疾病.另一方面, 在安全计算领域, 当用户将隐私数据和任务以加密方式存储在内存中, 如果暴露了处理器对内存的访问模式, 就可能泄露数据和任务本身的信息^{[6, 7]}.因此, 在大数据与云计算等应用场景中, 仅通过对数据本身的内容加密并不能完全的保护用户的隐私.对用户的访问模式的保护, 也是目前重点的研究目标.

不经意随机访问机是目前保护访问模式的一种重要手段.这一技术的目的是隐藏对真实数据块的访问, 使得攻击者不能区分每一次访问是真实的还是随机的.研究表明:不经意随机访问机应用于云存储系统可以有效的防止攻击者利用访问模式获取隐私信息, 减小数据存储系统的攻击面, 打破了单纯使用传统加密方式来保护数据隐私的系统框架, 为用户提供更完善的安全存储服务.同时, 利用不经意随机访问机来模拟安全多方计算的执行过程已被证实比传统用电路模拟的方法更高效^[8], 它极大地提升了对于海量输入数据的安全计算性能.因此, 不经意随机访问机为多方计算应用于大数据场景提供了可能^[9], 这对于设计更安全高效的分布式计算框架有着重要的意义.但是, 不经意随机访问机也会带来额外的开销, 比如:为了隐藏访问模式, 需要对多个数据块进行访问, 这增大了客户端与服务器之间的带宽, 客户端需要更大的缓存空间来存储从服务器端返回的额外数据块.所以, 不经意随机访问机的实用性还面临很大的挑战.针对这个问题, 学术界的学者已经提出了多种设计方案与优化策略.本文通过整理并归纳了近10年关于不经意随机访问机的研究工作, 介绍了模型常见的设计方案以及性能优化策略, 并且结合云存储以及安全计算场景分析不经意随机访问机在实际应用中的问题与挑战, 为在该领域的研究人员提供方法总结与研究思路, 并对今后的研究方向进行探讨.

本文第1节给出在暴露访问模式场景下推测加密信息的威胁场景, 并对不经意随机访问机的定义以及相关概念进行概述.第2节对不经意随机访问机研究领域关注的问题以及研究现状进行总结.第3节对已有的不经意随机访问机设计方案以及优化策略进行总结, 并比较不同方案在性能上的差异.第4节分析不经意随机访问机在云存储场景下的问题以及已有的解决方案.第5节总结不经意随机访问机结合安全计算场景的问题以及已有的解决方案.本文最后对全文进行总结, 阐述不经意随机访问机仍然需要解决的问题并展望未来的研究方向.

1 不经意随机访问机概述 1.1 加密环境下隐私泄露的威胁场景

一些研究工作已经证实, 仅通过加密方式是不能完全保护数据隐私的.在一些环境下, 攻击者依然可以通过观察数据的访问模式推测加密数据的隐私信息.例如在可搜索加密模式(searchable encryption scheme)下推测用户的查询内容^[4]、加密数据的顺序^[5]以及在分布式计算框架, 如MapReduce或者Spark的洗牌(shuffle)过程中推测用户的隐私信息^[10-12]等.

以文献[4]中的场景为例, 用户Alice将一个文本集D用可搜索加密模式进行加密, 并提交至半诚实服务器Bob, D中一共包含m个不同的单词.Alice通过提交请求Q, 查询某一个单词K在D中的哪些文本中出现.为了保证查询的隐私性, Alice首先将K转化成可识别的陷门单词Trapdoor_K, 查询结果R=(doc₁, doc₂, …, doc_n)以明文形式返回(暴露了访问模式).当Bob搜集到从Alice提交的l个查询请求$\tilde Q = ({Q_1}, {Q_2}, ..., {Q_l})$以及返回结果集合$\tilde R = $(R₁, R₂, …, R_l)后, 可以推断出Alice每一次查询的单词K是什么, 即, 确定查询单词的顺序集合${K_A} = \left\langle {{K_{{a_1}}}, {K_{{a_2}}}, ..., , {K_{{a_l}}}} \right\rangle $, 使得$\forall i \in [1, l], Trapdoo{r_{{K_{{a_i}}}}} = {Q_i}$, 如图 1所示.

在这一攻击场景中, Bob可以监听Alice与其之间的通讯信道, 并且拥有以下两种背景知识.

●  Bob知道Alice提交l个查询请求中, k个请求具体对应什么单词.即, ${K_Q} = \{ \langle x, y\rangle |(x \in {K_A}) \wedge (y \in \tilde Q) \wedge (y = Trapdoo{r_x})\} $, 并且k=|K_Q|.那么, 这k个请求可表示为$\tilde S = \{ y|\exists x, \langle x, y\rangle \in {K_Q}\}, \tilde S \subset \tilde Q$;

●  Bob知道关于D中单词的分布M, M是一个mxm的矩阵, M中的每一个元素M_ij表示第i个单词和第j个单词在均匀采样的文本d$\in $D中同时出现的概率, 即M_ij=Pr[(K_i$\in $d)$\wedge $(K_j$\in $d)].

因为Bob已经知道了l个查询请求中k个请求所对应的单词, 他只需要通过观察查询结果来确定剩下的$\tilde Q - \tilde S$个查询.实际上, 根据Bob拥有的第2个背景知识, 对于任意查询$Q' \in \tilde Q - \tilde S$, 其返回结果R'应与先验知识M相一致.因此, 可以将攻击过程转化成求解一个优化问题:

$ \mathop {\arg \min }\limits_{\langle {a_1}, ..., {a_l}\rangle } {\sum\limits_{{Q_i}, {Q_j} \in \tilde Q} {\left( {\frac{{{R_{{Q_i}}} \cdot R_{{Q_j}}^T}}{n} - ({K_{{a_i}}} \cdot M \cdot K_{{a_j}}^T)} \right)} ^2} $

(1)

$ {\rm{s}}{\rm{.t}}{\rm{. }}\left\{ {\begin{array}{*{20}{l}} {\forall j, {Q_j} \in \tilde S;\forall {a_j} = {x_j}, \langle {K_{{x_j}}}, {Q_j}\rangle \in {K_Q}}\\ {\forall j, ||{Q_j}|| = 1} \end{array}} \right. $

(2)

对于公式(1)中两个查询Q_i和Q_j, 可以根据它们的查询结果计算出两个单词在文本中联合出现的频率, 即$({R_{{Q_i}}} \cdot R_{{Q_j}}^T)/n$.然后, Bob通过背景知识计算出两个单词联合出现的先验概率, 即${K_{{a_i}}} \cdot M \cdot K_{{a_j}}^T$对应的单词尽可能准确, 即令先验概率和后验概率之间的距离最短即可.通过实验验证, 这一方法可以推测出大约80%的查询请求.

1.2 相关概念

不经意随机访问机(oblivious RAM, 简称ORAM)的概念最早起源于RAM(random access machine)模型, RAM是一种重要的计算仿真手段.在这个模型中, 处理器通过对存储器的读写来实现程序的执行.上个世纪80年代, 为了隐藏程序对内存的访问模式来避免软件的逆向工程, Goldriche等人在此基础上提出了ORAM^[13].所谓的访问模式, 指的是处理器访问内存的操作序列和地址序列^[14].ORAM保证了在存储器中的任意数据块不会永久驻留在某一个物理地址中, 这确保了任意两次访问不会产生关联.同时, ORAM将每一次读写访问(access)细化成一次读取加一次写回的原子操作(operation), 其中读访问转化成读取内容再写回相同内容, 写访问转化成读取内容再写回更新后的内容, 使得攻击者不能够区分具体的访问方式, 如图 2所示.

因此, ORAM可以很好地保护以下4种属性:(1)访问数据块的位置; (2)数据块请求的顺序; (3)对相同数据块的访问频率; (4)具体的读写访问方式.这使得在访问结束之后, 攻击者不能根据访问模式来区分任意两个相同长度的访问序列.在第1.1节的场景中, 可以使用ORAM来隐藏客户端对服务器的访问模式, 避免攻击者直接获取查询结果R.通常, ORAM的定义是基于客户端与服务器之间有状态的交互式两方协议^[15].我们用((c_out, c_state), (s_out, s_state))$\leftarrow $protocol((c_in, c_state), (s_in, s_state))来表示客户端与服务器之间的执行协议, 其中, c_in与c_out表示客户端的输入与输出, s_in与s_state表示服务器的输入与输出, c_state与s_state表示协议执行前后客户端与服务器的状态.

定义1(oblivious RAM (ORAM)^[15]). ORAM通常包含以下客户端与服务器之间的交互行为:

●  (($\bot $, C), ($\bot $, D))$\leftarrow $Setup(1^λ, (Input, $\bot $), ($\bot $, $\bot $)):表示客户端与服务器构造ORAM的交互协议, 其中, λ表示安全参数, Input表示客户端提交的初始数据集, 服务器的输入为空($\bot $), 同时, 客户端与服务器的初始状态也为空.在Setup协议执行完之后, 客户端达到状态C, 服务器达到状态D, 同时, 两方均没有输出;

●  ((data, C'), ($\bot $, D'))$\leftarrow $Access((op, C), ($\bot $, D)):表示客户端访问服务器的执行协议, 其中, op表示一个读操作read(addr)或者是一个写操作write(addr, data).addr表示被读取或者写入的数据块的地址, data表示被写入的数据.C与D分别表示客户端与服务器执行访问协议之前的初始状态.当协议执行完之后, 如果是读操作, 客户端获得对应地址addr的数据, 如果是写操作, 客户端获得更新之前对应地址addr的数据.C'与D'分别表示客户端与服务器执行访问协议之后的状态.

定义2(oblivious RAM的安全性^[16]).用 $\vec y = ((o{p_1}, add{r_1}, dat{a_1}), (o{p_2}, add{r_2}, dat{a_2}), ..., (o{p_M}, add{r_M}, dat{a_M}))$表示一个长度为M的数据请求序列, 其中, 每一个操作op_i表示一个读操作read(addr_i)或者是一个写操作write(addr_i, data).用$A(\vec y)$表示对于给定的数据请求序列$\vec y$所产生的访问序列.如果一个ORAM是安全的, 那么对于两个长度相同的数据请求序列 $\vec y$和$\vec z$, 它们的访问模式$A(\vec y)$和$A(\vec z)$是计算不可区分的.

定义3(oblivious RAM的正确性^[17]). 如果一个ORAM的设计是正确的, 那么以数据请求序列$\vec y$为输入得到的数据返回结果与直接通过$\vec y$得到的数据返回结果有超过 $1-negl(|\vec y|)$的概率是一致的, 其中$negl(|\vec y|)$表示以$\vec y$为输入的可忽略函数.

在ORAM的设计中, 通常考虑两个重要的组成部分:一个是ORAM的初始化, 另一个是利用ORAM进行数据访问.在初始化阶段^{[8, 18]}, 服务器为客户端创建ORAM空间, 客户端通过安全参数获得用来加密数据库的密钥.然后, 利用语义安全(semantic secure)加密的方式加密数据库中的每一个数据块.通常, 数据块中不但包含数据内容, 还包括数据块索引以及数据块的位置、是否被访问过等属性信息.最后, 客户端将加密好的数据块上传至ORAM.在有些ORAM设计以及应用^{[9, 19, 20]}中也提到:在执行正式访问之前, 还包含一个预热过程(warm-up), 这是通过预先访问O(N)个数据块, 使得ORAM达到一个稳定状态, 其中, N指的是服务器存储数据块的数量.在通用的ORAM研究中, 一般不考虑它的初始化开销; 但是在结合安全计算场景中, 由于初始化需要结合协议来完成, 这一部分必不可少, 而且开销很高^[21].

在利用ORAM对服务器进行访问时, 通常包含两种主要操作:读(read), 写(write).读操作和写操作是ORAM的两种原子操作.读操作是将访问的数据块取回客户端本地; 写操作是将取回本地后的数据块更新后再写回服务器.客户端对服务器的任意读写访问都可以通过这两种原子操作来表示.为了维护访问的隐私性与ORAM系统稳定性, 不同设计模型还需要设计其他的离线操作.对于平方根模型和层次模型, 在一个访问周期(epoch)结束后, 需要将所有的数据块位置重新混淆, 这称为混洗操作(reshuffle).对于树状模型, 为了保证每一个数据块集合(bucket)不溢出, 需要不断的将数据块从一个物理地址移动到更大空间的物理地址, 这称为驱逐操作(eviction).因此可以看出, 不经意随机访问机主要有以下特性.

(1) 低效性:相比于正常的访问, 不经意随机访问机需要执行额外的操作来保护访问模式的隐私性, 这种访问模式往往带来昂贵的开销, 包括带宽以及本地存储等, 这严重的限制了ORAM的实用性;

(2) 安全性:不经意随机访问机提供了保护访问模式的可证明安全性, 相比于传统的加密手段, 该技术可以很大程度上减少攻击者利用访问模式推断隐私信息的可能性;

(3) 用途广:不经意随机访问机可以广泛地应用于安全存储以及安全计算领域, 对于存在数据访问的应用, 都可以利用ORAM提供访问模式的保护.

2 不经意随机访问机研究的现状分析

不经意随机访问机面临的最大问题是性能开销大.纵观不经意随机访问机的发展, 其设计模型大致可以分为5类:简单模型、平方根模型、层次模型、分区模型和树状模型.不同的设计模型表示服务器存储数据块的数据结构不同, 用户通过对服务器ORAM的访问来获取所需的数据块.这些模型设计的目标主要还是提高性能.

●  简单模型:服务器以数组的方式连续存储客户端的数据块.为了隐藏客户端访问了哪一个数据块, 客户端每一次访问需要遍历所有数据块.对于不需要的数据块, 客户端读取之后再写回相同的数据块; 对于目标数据块, 客户端读取后在本地更新, 再写回更新后的数据块.同时, 即使客户端找到目标数据块, 依然继续访问;

●  平方根模型:将服务器划分成两部分:排列数组(permuted array)与缓冲区(shelter).排列数组中包含N个真实数据块(real block)和$\sqrt N $个无效数据块(dummy block).客户端每次访问之前需要将排列数组中的所有的数据块混洗.在每一次访问中, 客户端先查找目标数据块是否在缓冲区中:如果在缓冲区中, 就从排列数组中读取一个无效数据块; 如果没有在缓冲区中, 就从排列数组中读取目标数据块.为了混淆数据块的访问位置, 每一个访问周期($\sqrt N $次访问)需要重新混洗排列数组;

●  层次模型:将服务器的存储划分为层, 第i层包含2ⁱ个数据块集合(bucket), 对于每一层而言, 当一个访问周期(2ⁱ次访问)结束后, 需要将当前层的数据块和下一层的数据块合并并且混洗后放入下一层.每一层实际上都是一个hash表, 并且包含一个hash函数.每一层的访问周期结束后, 需要更换hash函数.当客户端访问一个数据块时, 从最顶层到最底层依次查找, 通过计算hash函数来判断目标数据块是否在当前层:如果在, 则根据hash函数计算所得的偏移量获得对应数据块; 如果不在, 则继续查找下一层.与简单模型类似, 为了保护访问模式的隐私, 即使找到了目标数据块也会继续查找下一层, 之后, 每一层会随机访问一个无效数据块, 直到所有层都被访问.当客户端更新完数据块后, 将其写入服务器最顶层.由于顶层的访问周期短, 其中的数据块会频繁地混洗到下一层, 因此不用担心顶层数据块溢出的问题;

●  分区模型:将数据存储在$\sqrt N $个服务器(partitions)中, 每一个服务器利用平方根模型或者层次模型构建, 同时, 客户端存储数据块索引到数据块在服务器位置之间的映射表以及每一个服务器的缓存(cache slots).对于客户端每一次访问, 先根据映射表查找数据块所在的服务器, 然后使用对应ORAM模型的访问方式获取数据块.当获得数据块之后, 将其重新分配一个新的服务器, 并写入对应服务器的缓存中.缓存满之前执行将数据写回对应的服务器;

●  树状模型:在层次模型上进行改进, 将每一个数据块集合分配到树的节点上, 客户端本地存储每一个数据对应树的叶子节点的映射关系(position map).以Tree ORAM^[27]为例, 每一次访问先查询数据块所在的叶子节点, 将从根节点至这个叶子节点上所有的数据块集合取回本地.更新完之后, 将目标数据块写入根节点.每一次访问结束之后, 在每一层随机选择v个数据块集合执行驱逐操作, 将一个真实数据块写入它对应叶子节点那条路径上的子节点数据块集合中.同时, 再选出一个无效数据块写入它另一个子节点的数据块集合中.

表 1归纳了这5种设计模型的优缺点.

我们总结了近10年在信息安全顶级会议(CCS, S&P, USENIX Security和NDSS)上关于ORAM的研究工作.其主要研究方向大致分为以下3大类.

●  通用ORAM性能优化.这一类研究方向主要的目标是优化ORAM本身的性能, 减小与一般访问之间的开销差距.衡量的指标主要包括:(1)客户端与服务器之间的平均带宽(amortized bandwidth); (2)最坏情况的带宽(worst-case bandwidth); (3)带宽加速比(bandwidth blowup); (4)交互轮数(round-trips); (5)客户端存储空间(client storage)等.也有一些其他的指标, 例如在线带宽(online bandwidth)、离线带宽(offline bandwidth)、数据块大小(block size)、是否具有服务器计算能力(server-computation capability)等, 表 2总结了常见ORAM的性能.在绝大多数ORAM研究中^{[13, 16, 17, 25-28]}, 一般考虑存储加密数据的服务器是不可信的, 提交访问请求的客户端是可信的; 也有一些论文研究对于恶意客户端的场景^{[29, 30]};

●   ORAM安全存储系统设计.这一类方向主要考虑设计与实现利用ORAM保护访问模式的安全存储系统.除了优化系统性能之外, 还需要解决ORAM结合存储场景的实用性问题, 例如如何保证数据访问的完整性^[31-33]以及如何支持多用户在异步网络下并发访问的问题^{[20, 34, 35]}等;

●  结合ORAM的安全计算.一些研究工作证实^{[8, 37]}:在海量数据输入的场景下, 利用RAM模型模拟计算过程要比单纯利用传统电路实现安全计算要更高效.将ORAM与安全计算协议相结合, 既可以保证计算过程的安全性(基于Yao的混淆电路), 也可以保证在计算过程中数据访问的隐私性(基于ORAM).通常, 这一类方向主要包含两个研究点:(1)设计基于ORAM的安全两方或者多方计算协议^{[8, 37]};(2) 不经意数据结构的设计^{[38, 39]}等.

还有一些其他结合ORAM的研究方向, 例如安全处理器的设计^[40]、利用ORAM加密磁盘文件^[41]等.

3 通用ORAM性能优化方案分析

对ORAM进行性能优化, 是目前对ORAM研究的核心问题.这一类方向通常不考虑具体的应用场景, 主要是研究如何设计高效合理的ORAM结构, 或者是应用一系列优化策略提升ORAM的性能.用来衡量ORAM性能的指标有很多, 目前, 这一类问题最关注的指标有5种:客户端与服务器的平均带宽、客户端与服务器最坏情况的带宽、客户端的存储开销、服务器端的存储开销和客户端与服务器的交互轮数.

3.1 客户端与服务器平均带宽优化

客户端与服务器之间的平均带宽是考量ORAM性能的重要指标之一.在现有的C-S架构中, 通常客户端与服务器的内存空间可以达到几个GB甚至几十个GB, 磁盘空间也可以高达几百个GB, 甚至TB级.但是客户端与服务器之间的通信带宽通常只有MB级.因此, 带宽资源要比存储资源更珍贵是这一类问题的出发点.在ORAM中, 平均带宽指的是每一次访问客户端与服务器之间所需要传输的平均比特数.特别地, 在平方根模型和层次模型中, 由于混洗过程产生的离线带宽, 通常按一个访问周期中总共传输的比特数与周期内访问次数的比值作为平均带宽.对平均带宽的优化策略有很多, 研究比较多的有基于布谷鸟哈希(cuckoo hashing)的优化策略、基于服务器计算的优化策略、基于映射表的优化策略以及基于k叉树的优化策略等.

3.1.1 基于布谷鸟哈希的优化策略

在传统的层次结构中, 第i层包含2ⁱ个数据块集合, 并且每一个数据块集合包含O(logN)个数据块.在查询数据块时, 先根据哈希函数计算数据块所在的数据块集合, 然后在数据块集合中线性查找对应的数据块.而在利用布谷鸟哈希^[3]时, 可以直接将数据块存在每一层中, 不需要依赖于数据块集合.因此在每一次查询中, 可以减少O(logN)的线性搜索时间.文献[14, 42]在布谷鸟哈希的基础上结合了Hadoop MapReduce, 设计出MapReduce布谷鸟哈希(MapReduce cuckoo hashing), 通过并行的在两个哈希表构造出的二分图上执行宽度优先搜索算法, 可以更快地判断是否发生冲突.

在层次模型中, 两层数据块混洗后计算哈希值, 重新确定数据块的位置容易导致哈希值冲突, 进而产生数据溢出的问题.一种场景的解决策略是利用布谷鸟哈希^[43]的方法, 将每一层的哈希表替换成两个, 每一个哈希表都有一个哈希函数.如果其中有一个哈希函数计算的哈希值出现冲突, 就利用另一个哈希函数进行计算, 并将数据块放入对应哈希表中.当然也会存在两个哈希函数都冲突的情况, 那么就将第一个哈希表中对应的数据块取出, 用其第二个哈希函数重新计算哈希值, 如果对应位置为空, 那么就将其放入那一个哈希表的对应位置.但是布谷鸟哈希并不能完全抵抗哈希值的冲突, 如果两个哈希表依然存在冲突问题, 需要重新选择两个哈希函数, 并计算每一个数据块的哈希值.

3.1.2 基于服务器计算的优化策略

早期的ORAM研究中, 通常将服务器理解为只能提供存储功能的对象.在文献[13]中, Goldreich等人提到:在O(1)的客户端存储空间下, 不具备服务器计算能力的ORAM有着Ω(logN)的带宽下界.在近几年的研究中, 一些工作^{[25, 26]}为了进一步提升ORAM性能, 允许服务器有计算能力, 虽然其中有一些计算是不安全的.通常将没有计算能力的ORAM称为标准模型(standard model), 有计算能力的ORAM称为非标准模型(non-standard model).

在传统的基于树状模型的ORAM中, 当客户端提交一个数据请求后, 服务器需要将目标数据块所在的从根节点至叶节点路径上的所有数据块返回给客户端, 以保证数据访问的隐私性.但是这将导致至少O(logN)数量级的开销.文献[25, 44, 45]通过允许服务器执行异或计算, 将路径上的所有数据块执行异或.这样做使得每一次读取的返回结果只有一个数据块, 可以将在线带宽降为O(1).由于路径上除了目标数据块是有效的之外, 其余数据块均为无效数据块.因此, 客户端可以很容易地通过层数、偏移量等信息构造无效数据块, 进而恢复目标数据块^[45].但是由于在一般ORAM研究的威胁模型中通常考虑服务器是不可信的, 所以虽然这种方法降低了客户端与服务器之间的带宽, 但是允许服务器执行异或操作是不安全的.

还有一些工作结合隐私信息检索(PIR), 允许服务器执行一些安全的计算, 例如同态加密^{[15, 19, 26, 46, 48, 49]}.由于隐私信息检索本身就可以很大程度上避免服务器推测用户的隐私, 因此这一类工作也可以适用于ORAM.客户端通过提交一个加密的选择向量(select vector), 服务器利用其执行同态加密计算, 得到一个加密的目标数据块返回给客户端, 客户端通过解密得到结果.但是利用同态加密依然存在不足:(1)计算开销很大, 虽然有一些工作^{[26, 46]}使用了半同态或者是部分同态, 但是依然很难用于实际; (2)迭代的利用同态加密会导致密文大小持续性增长, 带来额外的存储开销, 文献[26]利用了Damgård-Jurik加密系统^[50]缓解了密文膨胀, 但是这个问题依然存在.除了同态加密之外, 允许服务器支持秘密共享^[28]也可以用来实现ORAM, 而且这种方法要比利用同态加密高效的多.客户端将数据以秘密共享的形式存放在多个服务器中, 通过将选择向量秘密共享发送给服务器, 每一个服务器执行隐私信息检索之后, 将目标数据块的秘密分块返回给客户端, 客户端根据秘密重构恢复数据块.但是由于秘密共享所基于的求解多项式方程组的数学原理, 使得其依赖于t-隐私(t-privacy)^[51], 很难应用于基于不可信云管理员的云场景中.

允许服务器执行隐私信息检索除了可以降低平均带宽, 还可以减少客户端的存储(见第3.3节).因此, 利用隐私信息检索的服务器计算来设计ORAM, 这一研究方法近年来受到了广泛的关注^[52].

3.1.3 基于客户端存储的优化策略

在传统的层次模型中, 可以通过计算每一层的哈希值确定数据块在层中的位置.但是如果数据块不在当前层, 需要继续查找下一层, 再一次计算哈希值.这会带来额外O(logN)的计算开销.一种解决方案^[53]是在客户端本地存储一个数据块与层数之间的映射关系, 当需要查找数据块时, 可以先通过定位数据块所在的层, 然后执行哈希函数确定所在的数据块集合.这样可以减少O(logN)的查询开销.

这种基于映射表的优化策略在树状模型中广为使用^{[17, 25-28]}, 客户端本地记录树中每一个数据块对应的叶子节点, 当需要查询数据块时, 可以直接定位到从根节点至叶子节点所在的路径.这样避免了复杂的遍历过程, 提升了平均带宽.明显地, 这种基于映射表的策略也可以降低交互轮数(见第3.5.1节), 避免复杂的客户端比较验证的过程, 因此, 这种方法在很多种ORAM中都有应用^{[17, 25-28]}.但是在客户端存储映射表也会带来额外的存储开销, 一种常见的解决方案是利用迭代构造的思想(见第3.3.1节).

还有一种客户端存储的优化是客户端存储一个缓冲区(stash), 当每一次数据写回时, 不直接将其写回服务器, 而是先保存在缓冲区中.当缓冲区满之前, 将其中数据块再全部写回服务器.这样的好处在于:每一次查找数据块时, 先在本地查找, 如果存在可以直接获取, 降低了与服务器之间的通信带宽.例如在Partition ORAM^[16]中, 客户端有着对应于每一个服务器的本地缓存, 大小为$O(\sqrt N )$.因此在这种情况下, 平均带宽仅为O(logN)(迭代构造时为O(log²N)).还有文献[41]提出将树状模型的前${\rm{log}}\sqrt N $层存储在客户端, 称为tree top caching.这样避免了每一次都需要访问整个服务器带来的开销.这种设计也被用于优化Ring ORAM^[25].

3.1.4 基于k叉树的优化策略

对于传统的树状模型, 通常使用的是二叉树结构, 每一个节点只允许有两个子节点.由于在查询过程中, 树状模型是按树的层数返回数据块, 例如Tree ORAM^[27]中, 当查找到目标数据块后还要继续查找, 直到叶子节点, 以保证访问的隐私性; Ring ORAM^[25]中, 需要将O(logN)个数据块返回客户端, 其中一个为目标数据块, 其余的均为无效数据块(如果不考虑XOR计算).因此, 查询的次数与返回的数据块与树的层数有很大关系.一种常见的解决方案是使二叉树扩展为k叉树.这样可以保证在不增加存储容量的前提下, 降低树的层数.对于二叉树而言, 访问的层数为O(log₂N), 而k叉树仅有O(log_kN), 因此可以降低O(logk)的平均带宽.但是这种方法并不是没有缺点, 降低了层数导致每一层数据块集合增加, 使得树状模型的驱逐操作会更复杂.

3.1.5 方案比较与讨论

以上4种优化策略是常见的提升ORAM平均带宽的方法.为了更直观地表达和对比每一种具体方案的优缺点与性能, 我们做了如下总结(见表 3).

通过分析这4种优化策略的方案与优劣性, 实际上可以将这4种方案的出发点归为3个角度.

●  从存储角度以空间换时间.基于布谷鸟哈希和基于客户端存储的优化策略都是通过在服务器或者是在客户端添加额外的存储来保证在访问过程中减少带宽, 从而降低访问的响应时间, 但是这会导致存储开销的增大;

●  从计算角度减少访问的传输量.对于基于服务器计算的优化策略而言, 它将访问过程中所需要传输的数据块定位到一个数据块, 减少不必要的传输; 同时, 在访问过程中不会暴露数据块本身的信息, 客户端也可以在访问结束之后重构目标数据块;

●  从优化设计模型角度降低平均带宽.由于树状模型每一次访问所需传输的数据块来源于同一条路径上的每一层, 因此这一类方案尝试通过改变树结构来提高效率.基于k叉树的优化策略从设计结构上降低了树的高度, 从而减少传输带宽.与前两者不同, 这种方法没有采用额外的技术, 但是这也会带来驱逐操作的复杂性.

3.2 客户端与服务器最坏情况带宽优化

在很多场景下, 我们不能期望ORAM每一次访问都可以达到平均带宽的开销.当一次访问伴随混洗和驱逐操作时, 复杂的后台计算将制约当前访问的响应时间.这种情况有时需要几倍甚至几十倍的平均带宽.因此, 只追求平均带宽的最优是很难应用于实际场景的.最坏情况带宽考虑了这一问题, 通过定量计算在一个访问周期或者是多次访问中最坏情况时的带宽, 可以帮助我们更好地衡量ORAM的性能.这一类指标的优化方案一般包含以下4种:基于de-amortization的优化策略、基于树状模型的优化策略、基于改进混洗操作的优化策略和基于改进驱逐操作的优化策略等.

3.2.1 基于de-amortization的优化策略

分析最坏情况发生的原因, 往往是因为一个访问周期中的一次访问与复杂的混洗和驱逐操作并发执行.例如在层次模型中, 如果一个访问的目标数据块此时恰好在执行混洗, 需要合并写入下一层, 当前的访问必须等混洗操作执行完之后才能执行.一种常见的解决策略是不用等复杂的混洗和驱逐操作最后执行, 而是将其均摊到每一次访问, 或者是每一个较短的时间段内执行, 这种优化策略称为de-amortization.例如在Partition ORAM^[16]中设计了均衡器(amortizer)模块, 每一个时间周期内写回O(logN)的数据, 这样就将原来复杂的$O(\sqrt N )$的最坏情况降低为O(logN).De-amortization优化策略也被应用于文献[25, 26]中, 对于每A次访问执行一次的驱逐操作, 可以将其平均到每次访问中执行, 这样, 每一次访问只需要驱逐1/A的节点, 缓解了最坏情况下的带宽问题.

3.2.2 基于树状模型的优化策略

树状模型是一种经典的ORAM设计模型, 也是目前最常用、变种最多的模型.最初, 树状模型提出的初衷就是为了解决平方根模型和层次模型在最坏情况下的带宽问题.这两者都需要复杂的混洗操作, 其中:平方根模型需要利用不经意排序将缓冲区的数据写回排列数组, 需要O(nlogn)的复杂度; 而层次模型也需要将写满数据块的层与下一层的数据块执行不经意排序后写入下一层.在最坏情况下, 层次模型的不经意排序要涉及到所有的层.树状模型继承了层次模型的思想, 并做了创新:它将每一层的多个数据块集合划分到树的每一个节点中.这样的优势在于:当每一次执行驱逐操作, 每一个数据块集合只与其父子节点有关, 而与其兄弟节点无关, 这样可以将驱逐操作的复杂度降到O(logN), 如图 3所示.很大程度上提升了ORAM在最坏情况下的性能.如今, 几乎所有的通用ORAM性能改进所衍生的ORAM都是基于树状模型^{[17, 25-28]}, 这也继承了树状模型在最坏情况下带宽的优势.

3.2.3 基于改进混洗操作的优化策略^**

**由于平均带宽需要将混洗操作的带宽平均到每一次访问中, 因此基于改进混洗操作的优化策略实际上也可以优化平均带宽, 这里我们考虑最直接的影响.

在平方根模型和层次模型中, 复杂的混洗操作是提升性能的最大阻碍.为了保证访问的隐私性, 需要将数据块在一个访问周期结束的时候更新位置, 并且在同一个访问周期内, 每一个无效数据块都只能被访问一次.一些工作尝试改进复杂的混洗过程来间接地提升ORAM性能.

对于混洗过程而言, 为了保证数据在排序过程中的隐私性, 通常采用不经意排序(oblivious sorting)^[3], 它要求排序过程中的访问模式不依赖于具体数据.冒泡排序是一种不经意排序, 但是需要O(n²)的排序复杂度.一些其他工作在不经意排序算法上提出了改进, 如Batcher提出了一种排序网络方案^[22], 复杂度为O(nlog²n); Atjai等人^[23]提出了更为优化的改进AKS排序网络, 复杂度为O(nlogn), 但是有着很大的常数项(大约是6 100), 因此实用性较差.2010年, Goodrich等人^[24]利用随机希尔排序构造出一种复杂度同样为O(nlogn)、但是常数项很小(大约是7~8)的不经意排序算法.平方根模型和层次模型默认采用复杂度为O(nlogn)的不经意排序算法.文献[51]中也给出了一种基于归并排序的不经意排序方法, 复杂度也为O(nlogn).还有一些工作改进了混洗操作, 例如文献[54]中利用客户端存储, 通过本地计算两个数据块集合的位置, 然后将其发送给服务器.将每一层的混洗转化成只涉及4个数据块集合(两个在客户端, 两个在服务器)的归并操作.因此, 这种方法被称为四联归并(quadruplet merge).

3.2.4 基于改进驱逐操作的优化策略^***

与基于改进混洗操作的优化策略类似, 由于平均带宽需要将驱逐操作的带宽平均到每一次访问中, 因此基于改进驱逐操作的优化策略实际上也可以优化平均带宽, 这里我们考虑最直接的影响.

与混洗操作类似, 在树状模型中, 驱逐操作是影响性能的最大因素.由于在树状模型中, 每一次访问结束需要将目标数据块放入数的根节点中, 为了保证每一个节点数据块集合不溢出, 需要周期性的将数据块不断的写入其子节点中.

在Tree ORAM^[27]中, 对于每一次访问后的数据写回, 需要先在树中每一层随机选择v个数据块集合, 并从每一个数据块集合中选出一个真实数据块写入它对应叶子节点那条路径上的子节点数据块集合中.同时, 再选出一个无效数据块写入它另一个子节点的数据块集合中, 以保证访问的隐私性.但是这种驱逐操作需要在每一次访问之后都执行.为了避免这个问题, 文献[46]提出了一种基于逆字典序(reverse lexicographical)的驱逐策略.在这种策略中, 每一次驱逐操作并不是像Tree ORAM那样是随机的, 而是固定的(通过模运算确定); 并且是在根节点至叶节点的一条路径上执行驱逐操作.具体对应哪一个路径, 可以通过将模运算的结果以二进制形式表示, 再逆序来确定.这样做的目的是使任意连续两次驱逐操作重叠的路径尽可能的少.同时, 这种驱逐策略有以下两个优点:(1)不需要每一次访问后都执行, 仅需要给定一个驱逐频率的参数, 用来表示一个访问周期中访问的次数, 当一个访问周期之后再执行; (2)这种驱逐策略可以减少服务器的计算量, 驱逐路径仅需要通过一个模运算确定, 而且驱逐的节点仅与路径中的节点有关.这种驱逐策略被广泛应用在ORAM设计中, 例如Onion ORAM^[26], S3ORAM^[28]等.

还有一些工作改进了树状模型的驱逐操作, 例如, 文献[55]中设计了一种基于贪婪方法的驱逐策略, 当客户端执行访问之后, 将本地缓冲区中当前访问的数据块尽可能地写入从根节点到与其分配叶节点相一致路径的数据块集合中.这种基于贪婪方法的驱逐策略也被用于文献[17, 56]中.

3.2.5 方案比较与讨论

通过比较以上4种优化最坏情况带宽的方法, 其实可以总结归纳为一点:都是通过优化在ORAM中最复杂的混洗和驱逐操作来降低带宽.稍有不同的是:基于树状模型的方案是从模型层角度进行优化, 包括基于树状模型的变种^{[17, 25, 26, 28]}也都继承了树状模型在最坏情况下的带宽优势; 而其他3种都是从方法角度优化, 通过分析混洗和驱逐模型本身在设计与实现上的缺点, 找出可能提升性能的方法, 因此这一类方法往往可以适用于一大类的ORAM模型.通过分析以上4种方法的特点, 我们可以归为3类.

●  平均化的思想.由于混洗和驱逐在ORAM中是非常复杂的执行过程, 因此这种方法将这个执行平均到每一次或者每一段时间中, 可以保证不会出现最坏情况下响应时间太长的情况.但是这也导致了每一次访问时间要比原来的访问时间略有提升;

●  优化混洗操作.树状模型的提出, 实际上也可以理解为优化平方根模型和层次模型在混洗过程中的缺点, 但是带来了驱逐操作.由于混洗操作通常依赖于不经意排序, 因此这一类优化工作主要是设计或者选择一个最优的排序算法;

●  优化驱逐操作.在树状模型的节点中可能会出现数据溢出的问题, 因此对于驱逐操作的优化通常只针对树状模型.并且在不同场景下驱逐操作的优化也略有不同, 例如在云存储场景中, 需要结合多用户, 考虑驱逐操作时客户端数据的备份问题, 在安全计算场景中需要考虑驱逐操作电路实现的复杂度等.

值得一提的是, 也有一些工作, 例如Onion ORAM, 通过结合树状模型和优化驱逐操作的策略(3节点的驱逐(triplet eviction))来提升带宽, 从而达到更好的效果.

3.3 客户端存储开销优化

对客户端的存储优化也是目前通用ORAM性能提升的主流指标之一, 由于客户端主要负责对数据的更新和计算, 因此尽可能少地占用客户端的存储资源, 是这个问题的出发点.对于优化客户端的存储, 常用的优化策略包括以下3种:基于迭代构造的优化策略、基于隐私信息检索的优化策略和基于布隆过滤器的优化策略.

3.3.1 基于迭代构造的优化策略

为了降低服务器与客户端的平均带宽, 一种常见的策略是在客户端本地存储一个映射表, 以避免线性查询的需要(见第3.1.3节).但是这种方法无疑会增加客户端的存储开销.针对这个问题, 文献[26]提出一种基于迭代构造的优化策略, 将存储在客户端的映射表以另一个ORAM的形式存储在服务器中.当需要查询一个数据块的位置时, 先在这个小ORAM中查询数据块在大ORAM中的位置.通过迭代构造, 这个小ORAM在本地的映射表也可以用一个更小的ORAM存储在服务器.以Tree ORAM^[27]为例, 假定树的高度为H, 那么服务器一共可以存储2^H-1个数据块集合(由于通常服务器存储量很大, 因此可以近似看成2^H个), 其中, 叶子节点为2^H-1个, 所以服务器的存储是叶子节点的常数倍, 将这个ORAM记为ORAM₀.此时, 客户端存储的映射表记录ORAM₀中每一个数据块与2^H-1个叶子节点的映射关系.通过迭代, 可以将这2^H-1个叶子节点以另一个高度为H-1的小ORAM存储在服务器, 记为ORAM₁.这样, 本地只需要存储ORAM₁中每一个数据块与其2^H-2个叶子节点的对应关系, 分区模型的迭代构造方法如图 4所示.通过对数级的迭代构造, 最终客户端本地的映射表存储可以降低为O(1).这种迭代构造在通用ORAM性能提升中很常见^{[16, 17, 25-27]}, 但是迭代构造会增加客户端与服务器的交互轮数.

3.3.2 基于隐私信息检索的优化策略

基于隐私信息检索的技术这几年受到研究人员的关注, 利用PIR设计ORAM不仅可以很大程度上降低客户端与服务器之间的平均带宽(见第3.1.2节), 还可以减小客户端的存储.对于传统的树状模型, 每一次访问服务器都需要遍历从根节点到叶子节点的完整路径, 有时还需要将其中每一个节点的数据块返回给客户端以保证访问的隐私性.因此, 客户端需要用一个缓冲区存放从服务器返回的所有数据块(见第3.1.3节).但是利用隐私信息检索技术不需要依赖于遍历多个节点来保证隐私性, 相反, 客户端将选择向量发送给服务器, 服务器只需要通过少量的计算可以直接获得对应的数据块结果, 而计算过程的本身并不泄露任何隐私.因此, 客户端不需要设计复杂的存储结构来记录服务器返回的数据, 只需要用一个存储单元记录目标数据块即可.这样, 客户端的存储可以降为O(1).这种技术被应用于Onion ORAM^[26], S3ORAM^[28]中.

3.3.3 基于布隆过滤器的优化策略

基于布隆过滤器(Bloom filter)的技术也是一种常用的降低客户端存储的优化策略.通常, 为了降低客户端与服务器的平均带宽, 客户端可以存储一个数据块与逻辑地址之间的映射表(见第3.1.3节)来降低在逻辑地址内线性搜索的开销, 但是这无疑会增加客户端的开销.一种基于布隆过滤器的解决方案是不需要本地存储映射表, 而是将查找的方法封装在一个加密的布隆过滤器中, 并且存放在服务器ORAM中的每一层.当客户端提交查询时, 会利用每一层加密的布隆过滤器来判断数据块是否在当前层:如果存在, 就返回对应的结果; 如果不存在, 就随机查找无效数据块以保证访问的隐私性.这种技术被应用于文献[26, 31, 54]中.

3.3.4 方案比较与讨论

以上3种优化方法都是针对客户端存储, 但是3种方法优化目标不同, 并且各有优缺点.针对这些方法的不同特征, 表 4对这3种方法进行了总结:

通过比较分析以上3种优化方法, 我们发现这3种方法主要是从两个角度优化客户端存储.

●  用服务器存储空间替换客户端存储.相比客户端, 服务器存储要更低廉.基于迭代构造的优化策略和基于布隆过滤器的优化策略都是尝试在服务器端存储额外的数据, 使得客户端需要通过执行更多的查找来获取相应的检索信息, 而这些信息本可以在客户端本地存储后直接获得.因此, 这些方法的缺点就在于增加了交互轮数;

●  从计算角度来减少客户端存储.结合第3.1.2节利用隐私信息检索可以降低平均带宽, 这种方法使得客户端不需要更多的存储空间来缓存从服务器返回的数据.因此, 这种基于隐私信息检索的ORAM优化策略在很多ORAM设计中经常使用.

3.4 服务器存储开销优化

在大多数ORAM设计中, 为了保证访问的隐私性, 服务器中不仅存储对用户有用的真实数据块, 还存储一部分无效数据块.对于每一种具体的ORAM, 存储无效数据块的数量有很大差异, 有时为了提升查询的性能, 服务器也存储一些额外的工具(例如布隆过滤器等).这些都会给服务器带来额外的存储开销.针对这些问题, 也有一些工作尝试对服务器的存储进行优化来提升服务器的效率.这一类方法主要是针对ORAM中数据块集合大小, 通过设计可变大小的数据块集合或者是增加(减少)部分数据块集合大小等.

在传统的树状模型中, 每一个节点可以包含O(k)个数据块, 但是实际上只有O(1)个数据块是真实数据块, 因此带来了O(k)的存储开销.文献[46]提出了一种改进策略, 允许每一个节点多存放m个真实数据块, 那么每一个节点容量变成O(m+k), 但是存储开销降为O(m/k).当m=k时, 开销仅为O(1).由于只增加了真实数据块的数量, 此时依然可以保证节点溢出概率不变, 为e^-k.Sánchez-Artigas等人^[57]也发现:除了数据块集合的大小对服务器存储有很大的影响之外, 还会影响驱逐操作.因此, 他们提出两种改进策略:首先, 根据每一次在同一路径上数据块的访问对数据块执行分组; 同时, 将Tree ORAM中的驱逐操作优化为对父节点和两个子节点数据块集合的驱逐.通过实验验证:相比于Tree ORAM, 在服务器端存储2¹⁵个数据块时, 这样的优化可以降低大约80%服务器端的存储开销, 同时降低大约8倍的通信开销.Moataz等人^[58]发现:传统树状结构的ORAM如果想扩展树的大小, 只有通过添加叶子节点, 但是这有可能破坏数据结构的概率完整性.因此, 他们通过设计一种节点数据块集合大小可变的ORAM, 通过实验验证, 这种优化方法可以降低87%的服务器存储开销和7%的通信开销.

对于服务器存储开销的优化策略主要出现在ORAM早期研究的一些论文中, 近几年, 针对这一问题的改进策略相对较少.但是这一问题依然不容忽视, 例如, Path ORAM^[17]需要28倍的存储空间, Ring ORAM^[25]需要6~8倍的存储空间.也就是说, 对于1GB的真实数据, 服务器需要存储几倍甚至几十倍的额外数据, 这还不考虑数据备份的问题, 因此, 这种开销在实际应用中是非常昂贵的.提供一种更好的解决服务器端的存储开销问题的方案, 是未来的研究重点之一.

3.5 客户端与服务器交互轮数优化

客户端与服务器之间的交互轮数也是通用ORAM性能提升的考虑指标之一, 因为复杂的交互轮数会导致一次访问的响应时间延长, 如果再考虑网络延迟的影响, 使得ORAM很难应用于实际.因此, 也有一些技术尝试通过优化交互轮数使得ORAM获得性能上的提升, 这一类问题的解决方案通常有两种:一种是基于映射表的优化策略, 另一种是基于混淆分支函数的设计.

3.5.1 基于映射表的优化策略

在第3.1.3节中, 我们给出了允许客户端存储数据块索引与ORAM逻辑地址之间的映射表可以很大程度上减少客户端与服务器之间的平均带宽.其实从另一角度来说, 映射表也是通过快速准确地定位目标数据块的位置, 减少不必要的访问来降低带宽.因此, 基于映射表的优化策略也可以用来降低客户端与服务器之间的交互轮数.Boneh等人^[53]将平方根模型和层次模型相结合, 设计出一种可以降低服务器与客户端访问轮数的优化策略.他们保留了平方根模型中的缓冲区, 并将其结合层次模型, 设计出层次结构的缓冲区.同时, 客户端存储每一个数据块索引与缓冲区层数之间的映射关系.当客户端访问数据块时, 可以直接根据索引找到所在的层, 进而执行访问, 使得仅通过一次访问就可以得到数据块, 避免了传统层次模型中需要遍历所有层的开销.同时, 这在树状模型中使用也很广泛^{[17, 25-28]}, 如果没有映射表, 服务器需要通过深度优先搜索或者是广度优先搜索的方法去先查找数据块的位置, 这种方法的交互轮数将是很高的.

3.5.2 基于混淆分支函数的优化策略

在第3.3.3节中, 我们提到了利用布隆过滤器可以降低客户端的存储, 但是在层次模型中, 每一层都需要有一个布隆过滤器, 因此依然需要计算O(logN)次才能完成一次访问, 因此, 这也会带来O(logN)的交互轮数.文献[54]将整个查找过程定义为一个分支函数, 并将其在客户端编译成混淆程序后, 外包给服务器进行计算.当服务器计算完成后, 将结果返回给客户端, 不需要每一层执行完之后返回结果.因此, 这种方法也可以将整个查询过程的交互轮数降为O(1).

3.5.3 方案比较与讨论

以上两种优化交互轮数的方法有很大的不同, 并且各有优缺点.

●  第1种基于映射表的优化是通过及时地定位目标数据块, 避免复杂的查找过程, 从而降低查询次数.这种方法直接并且高效, 因此被广泛的使用.但是这种方法也会带来客户端存储的开销;

●  另一种基于混淆分支函数的优化策略主要是针对利用布隆过滤器优化客户端存储后, 导致交互轮数增加的问题, 因此这种方法往往是应用在有布隆过滤器的场景下, 因此使用较少.但是这种外包计算的思想完全可以借鉴.利用类似于Yao电路计算的协议, 使得客户端和服务器之间执行一个安全计算, 从而让客户端获得目标数据块.但是需要添加额外的应对恶意服务器场景的措施, 提供相应的检测方法, 以应对服务器返回错误的计算信息.

3.6 小结

性能提升是目前ORAM研究的主流方向, 除了在通用ORAM设计方向, 在结合云存储和安全计算场景中也都有所涉及.通过分析与讨论已有工作的优化策略, 我们大致可以对现今ORAM设计与性能提升的工作总结为以下4点.

●  每一种方案都有优缺点.在设计一种优化策略时, 很难达到在改进一种性能指标之后保持其他性能的不变.以优化平均带宽为例, 其中, 基于布谷鸟哈希和基于客户端存储的优化策略都是通过在服务器存储部分数据来实现带宽提升, 但是这同样会增加服务器的存储开销.因此, 很多类似的优化方法都是通过针对目标问题, 在不影响全局性能的情况下, 尽可能地做出优化;

●  一种方案有时可以解决多个问题, 不一定只局限于某一种特定的性能.以基于隐私信息检索的优化策略为例, 它可以通过定位ORAM服务器中某一个具体的数据块来实现O(1)的平均带宽; 相应的, 客户端不需要很大的缓冲区来存储多余的数据块.这种方法在一定程度上实现了ORAM两个主要性能的提升, 因此受到了广泛的关注.除了隐私信息检索, 基于映射表的优化可以实现平均带宽和交互轮数的优化等;

●  不同方案可以叠加, 在设计ORAM时, 可以尝试利用多种优化策略, 有时可以起到更好的效果.例如, 树状模型在设计时就针对最坏情况下的带宽, 因此其本身就具备一定的优化最坏情况带宽的特点.所有树状模型的变种也都继承了这个特征, 但是例如Onion ORAM就在树状模型的基础上使用3节点的驱逐来进一步优化最坏情况的带宽.因此, 从多个角度来优化可以更好地解决问题;

●  ORAM的性能优化设计往往是多种方案的权衡.在设计一种ORAM时需要全局考虑, 考量每一种指标的重要性, 因为每一种方案都有优缺点, 一种性能提升, 往往会导致其他性能的降低.例如在利用布谷鸟哈希优化平均带宽的时候, 会导致服务器开销增加, 可以利用针对服务器存储的优化策略, 但是这也可能导致新的问题.同时, 我们还要考虑不同方案叠加的效率问题.因此, 要获得全局最优解, 往往需要从多个角度共同考量.

4 结合云安全存储场景的ORAM

结合云存储场景的ORAM安全存储系统设计, 也是目前ORAM重点研究方向之一.利用传统的加密手段保护存储系统, 只能够保护数据本身的机密性, 利用ORAM设计的安全存储系统可以抵御攻击者通过访问模式推断用户的隐私信息.而这种存储系统应用于云场景, 除了本身的性能问题之外, 也会有很多实用性的问题.因此, 这一类研究方向重点考虑如何解决ORAM安全存储系统在实用场景下带来的挑战, 例如, 如何保证数据在存储与访问过程中的完整性以及如何支持多用户并发访问的问题等.

4.1 ORAM的数据完整性保护

数据完整性保护是利用ORAM设计存储系统考虑的目标之一.对于恶意的云存储服务提供商来说, 他可以通过随意地篡改数据、违反用户的执行协议来推测隐私信息.但是这会导致用户在访问过程中获得错误的数据, 进而影响计算的准确性.因此, 有一些工作通过在ORAM访问数据中添加少量的验证信息, 来检测攻击者是否存在恶意篡改数据的行为.

一种经典的方法是对于存储在服务器中的每一个数据块都添加一个消息认证码(MAC), 对于每一次访问, 客户端通过随机检测从服务器中返回数据块中的MAC值是否正确:如果存在错误, 就可以证实服务器存在恶意的数据篡改.同时, 为了抵抗重放攻击, 每一次客户端验证完MAC值后, 会利用一个随机数重新计算MAC值, 使得恶意的云存储提供商不能够自主地计算验证码, 并且利用以往的返回信息来混淆用户.由于这种基于MAC值的保护数据完整性的方法有着相对少量的存储开销, 并且容易被用户验证, 因此被广泛使用^[32].除了这些基本的利用MAC值保护访问完整性的方法之外, Williams等人^[31]也尝试在ORAM中的每一层添加一个利用抗冲突的增量哈希(incremental hashing)计算的校验和来避免恶意的服务器在混洗过程中隐藏或者复制数据块.通过增量哈希, 用户不需要在每一次混洗之后重新计算哈希值, 也便于用户维护服务器的存储信息.在PrivateFS^[33]中, Williams等人利用sha256算法验证数据块的完整性.

部分完整性保护工作在ORAM设计的时候也考虑到了, 例如在Partition ORAM^[16]中, 每一次混洗之后, 利用了一个随机值来保证当前层的完整性, 使得当前层在下一次混洗之前不能被攻击者篡改.Path ORAM^[17]将整个树状ORAM看成是一棵Merkle树, 其中每一个节点都存储一个哈希值H(b₁||b₂||…||b_Z||h₁||h₂), 其中, b_i, i$\in ${1, 2, …, Z}表示当前节点中的每一个数据块, h₁, h₂表示其子节点的哈希值.通过这种方法, 也可以来验证数据完整性.

4.2 支持多用户的并发访问

绝大多数ORAM设计^{[13, 16, 17, 25-28]}通常只考虑一个客户端的场景, 然而在云场景中, 用户往往是很多个, 因此在设计结合ORAM的安全存储系统的时候, 需要考虑多用户并发访问的问题.尤其是在异步通信的网络中, 这种问题通常很难处理, 需要考虑的问题包括:(1)数据同步问题, 多用户访问同一个数据的时候数据更新会很复杂, 需要对每一个客户端的数据进行统一的管理, 如果处理不当会导致数据丢失, 甚至出现安全问题; (2)当服务器在执行混洗或者驱逐操作的时候, 数据块位置发生变化, 此时如果客户端还保留着更新完的数据, 需要添加一些额外的模块来保证驱逐完成以后数据能够准确地写回.

考虑多个客户端同时访问一个服务器的场景, 为了保护每一个客户端访问数据时的访问模式, 并且维护数据的一致性.最简单的一种思路是每一个客户端轮流访问, 服务器端存储关于客户端的状态信息(state), 以判定当前客户端能否执行访问操作.一个客户端必须等前一个客户端执行完之后才能继续访问.但是这种方法严重制约了访问的响应时间, 并且不利于并发访问的设计.2012年, Goodrich等人^[59]创新性地提出了一种无状态(stateless)ORAM, 它利用伪随机hash函数以及布谷鸟哈希的方法实现了对数据库的不经意访问的仿真.无状态ORAM服务器端不需要保存任何关于客户端的状态信息, 因此可以用来实现对多用户的并发访问.Williams等人^[33]利用无状态ORAM的构想, 结合Hierarchical ORAM实现了一种不经意文件存储系统PrivateFS.其中利用了一个日志模块(remote results log)来记录数据块的访问顺序以及数据块中的值.当用户需要请求一个数据块时, 服务器先将这个日志模块发送给客户端, 用来判定当前是否有相同的数据块被访问:如果有, 就执行一个虚假访问(fake query), 以保证数据访问的隐私性; 如果没有, 就执行真实访问(real query).但是对于PrivateFS而言, 用户的并发访问并不是完全的并发, 因为在用户获得访问结果、将其写入日志模块的时候, 必须等之前的访问写完才能继续写入.因此, PrivateFS依然存在访问性能的瓶颈.

为了解决PrivateFS^[33]中依然存在的线性访问的性能瓶颈, Stefanov等人利用Partition ORAM实现了一种分布式安全存储系统ObliviStore^[20], 并给出了分布式ORAM的完整定义.ObliviStore首次将存储系统定义在异步网络(asynchronous network)中, 使得任意用户可以在任意时间提交请求, 并且不会泄露访问模式的隐私.同时, ObliviStore还实现了以下几个优化策略:(1)利用块混淆(batch shuffling)的策略提高了每一个分区内ORAM的混淆性能; (2)为了避免并发访问以及延迟对客户端存储的影响, 利用信号量对客户端存储进行定量的表示.但是ObliviStore并没有完全意义上实现并发访问的安全性.文献[34, 35]都发现了:在ObliviStore中, 如果一个客户端同时对一个数据块访问两次, 与对不同数据块访问两次, 服务器返回的时间不同, 如图 5(a)所示.

这样会导致攻击者可以根据服务器的响应时间来判断客户端是否访问了同一个数据块, 从而泄露了用户的隐私.这是因为ObliviStore对于处理同一数据块的访问请求采用了序列调度机制.为了解决这个问题, 文献[34]提出了一种同样基于Partition ORAM的新的分布式文件存储系统CURIOUS, 取消了ObliviStore中的信号量, 同时, 对于一个客户端对同一数据块的连续两次访问请求, CURIOUS只允许第一次访问请求执行真实访问, 之后, 所有请求都执行虚假访问, 直到真实访问将数据写回.这样, ORAM可以直接处理连续的异步请求, 而不需要等待前一个访问结束.但是在异步通信中, 真实访问有可能比虚假访问有更长的响应时间, 对于CURIOUS来说, 如果发生这种情况, 在客户端获得目标数据块之前, 虚假访问会等待真实访问结束后, 再将数据返回给客户端.因此, 文献[35]中证明, 这种处理方式依然不安全.在真实的部署中, 很难向攻击者隐藏响应时间的信息.如果响应时间暴露, 攻击者依然可以推断出客户端是否访问同一个数据块的隐私信息, 如图 5(b)所示.

Sahin等人^[35]针对ObliviStore^[20]和CURIOUS^[34]存在的攻击者对相同数据块的连续访问会依据响应时间推测是否访问同一数据块的攻击, 提出了针对异步网络的新的安全性定义, 称为aaob-security(adaptive asynchronrous obliviousness), 并基于Path ORAM实现了支持多用户并发访问的文件存储系统TaoStore. TaoStore提供了两个额外的模块:一个是处理器(processor), 用来处理客户端与服务器之间的请求; 另一个是序列器(sequencer), 用来序列化服务器的请求, 使请求结果的顺序与请求提交的顺序相一致.

4.3 小结

为了更直观、明确地分析和对比不同的ORAM安全存储系统, 我们从攻击者模型、基于的ORAM设计模型、完整性保护、是否支持多用户并发以及是否考虑异步网络等角度进行比较, 见表 5.

综上所述, ORAM在结合云场景下的安全存储系统研究取得了一定的发展, 但是总体来说, 与真正可以应用在云环境依然有很长的距离, 主要体现在:

●  能够支持分布式的存储系统还很少.从ORAM本身的模型角度来说, 只有分区模型是真正意义上的分布式系统, 其他的模型都以单服务器为主, 因此很难应用于目前的云环境.考虑用多个树状模型组合设计ORAM存储集群, 是未来的研究方向之一;

●  效率依然很低, 尤其是访问时间.以ObliviStore^[20]为例, 对于一般的不需要保护访问模式的数据访问, 完成一个访问任务需要38.5s, 而ObliviStore需要181s;同时, ObliviStore需要产生17倍的流量^[34].因此在真实的云场景中, 这种开销是非常巨大的;

●  满足真正安全的ORAM存储系统几乎没有.真正实现异步网络下多用户并发访问的安全ORAM存储系统只有TaoStore^[35], 但是TaoStore也不是很完美, 例如它是一个单服务器的存储系统, 并不适用于云场景.那么是否存在多服务器下的异步网络访问的攻击场景, 还有待进一步研究;

●  安全存储系统的功能还不够完善.存在的ORAM存储系统只是从完整性和安全性角度考虑, 但是实际上, 一个存储系统的功能远不止这些, 例如数据备份等问题.

5 结合安全计算场景的ORAM

不经意随机访问机还有一个重要的用途就是可以用于安全计算.因为ORAM来源于RAM模型, 与图灵机(turing machine)、布尔电路(boolean circuit)和分支程序(branching programs)一样, RAM是一种重要的可以模拟计算过程的模型^[37], 因此, ORAM最初被用来保护程序的执行过程, 不被恶意的攻击者逆向.利用ORAM应用于安全计算场景, 通常是与安全多方计算(secure multi-party computation, 简称SMC)相结合.传统的实现安全多方计算的方式是构造电路, 并在其上设计相应的协议, 例如Yao协议^[64]、GMW协议^[65]等.但是这种基于电路实现安全计算有一个局限性, 电路大小与输入数据成正比^[8].考虑一个场景:客户端想对服务器执行一次隐私信息检索f, 传统的方法是构造一个客户端与服务器之间查询的电路, 客户端输入要查询哪一个数据的比特串x, 而服务器输入的是整个数据库D, 因此, 设计一个隐私信息检索的电路是非常庞大的.但是利用RAM可以更高效地实现这种海量输入数据的计算, 通过实验证实, 利用RAM实现计算所需要的时间是与输入数据大小呈亚线性(sublinear)关系^[8].因此, 利用RAM来实现安全计算是一种重要的途径.

Ostrovsky等人^[36]指出:利用ORAM可以安全地执行任何RAM程序, 其中的计算部分可以利用Yao的混淆电路(garbled circuit)^[64]实现, 对存储的访问部分可以利用基于ORAM的安全计算协议(SC-ORAM^[66])来实现.并且, 文献[36]也给出了从一般性的ORAM转化成SC-ORAM的方法, 称为Ostrovsky-Shoup编译器^[37].因此, 如今绝大多数结合安全计算场景的ORAM研究都是将SC-ORAM与电路相结合, 并且主要分为两类:结合ORAM的安全计算协议设计和不经意数据结构(oblivious data structure)的设计.

5.1 结合ORAM的安全计算协议设计

与通用ORAM性能提升的角度不同的是:在安全计算领域, ORAM中的客户端与服务器通常指的是CPU和内存单元.而利用总线通信的CPU和内存之间的传输速度要比一般基于网络通信的客户端与服务器之间的速度快得多.因此在安全计算中, 一般不以带宽作为衡量ORAM性能的指标.相反, 服务器和客户端的计算复杂度在这其中起到了决定性的作用, 这一部分的研究工作通常以优化协议中服务器与客户端的计算复杂度和电路复杂度作为目标, 设计更为高效的ORAM安全计算协议.

5.1.1 基于优化计算复杂度的协议设计

Gordon等人^[8]最早将ORAM应用于安全两方计算, 首次利用Tree ORAM实现了一种可以在亚线性时间内实现安全两方计算的协议.他们的工作主要基于两个发现:(1)利用RAM实现的很多计算, 其执行时间与输入数据的大小呈亚线性关系, 这比电路要高效得多; (2)如果计算方多次执行非平凡函数(non-trivial function)的计算, 那么有可能实现其性能的进一步优化.文献[8]将Tree ORAM^[27]与Yao的混淆电路相结合, 并利用了异或计算与不经意传输扩展(OT extension)等优化策略.假定一个利用RAM实现的函数f可以在时间大小为t和空间大小为s中被执行, 那么利用文献[8]中的方案将f转化成一个客户端与服务器之间的安全两方计算协议, 执行的平均时间为O(t)×polylog(s), 客户端需要O(logs)的空间, 服务器需要s×polylog(s)的空间.

Lu等人^[37]利用Hierarchical ORAM^[13]设计了一种可以用于安全两方计算的ORAM计算协议.他们将Hierarchical ORAM按层次的不同划分在两台服务器上, 并且在协议的执行过程中两台服务器始终没有交互.由于Hierarchical ORAM性能低效的原因在于复杂的混洗操作, 文献[37]利用对数据块的标记(tagging), 客户端每一次访问之前都需要通过计算目标数据块的标记获得访问地址, 而不用依赖于数据块本身.同时, 对数据块的标记可以简单地利用伪随机函数进行维护, 不需要利用针对所有数据块的混洗操作.如果一个用RAM实现的函数f, 其输入与函数本身大小为Λ, 函数运行时间为T, 那么应用文献[37]中方案将f转化成一个安全两方计算协议, 那么协议的通信和计算复杂度为O((Λ+T)log(Λ+T)).如果允许对数据集执行预处理的话, 那么在线的通信和计算复杂度可以降为O((ε+T)log(Λ+T)), 其中, ε表示在线输入的大小.

第5.1.2节中的文献[8]和文献[9]都提出了在SC-ORAM中, 当数据的总量N小于一个阈值时, 利用线性搜索所需要的时间要比设计更复杂ORAM的时间更短.Zahur等人^[21]利用这个特征分析了通用ORAM研究与基于安全计算ORAM研究的区别, 同时结合了Square-root ORAM^[13], 进一步降低了阈值.在传统Square-root ORAM设计中, 客户端利用一个hash函数来计算映射表, 文献[21]将其替换为利用共享数组直接存储.这样的好处在于:当初始化以及混洗的时候, 只需要利用简单的混洗网络, 而不用对数据块执行复杂的不经意排序.同时, 文献[21]将Square-root ORAM结合迭代技术, 降低了客户端的存储.

Doerner等人^[67]发现, 文献[8, 21, 68]的设计其实都有缺陷, 例如都使用了迭代构造的方法, 这种方法虽然可以优化客户端存储的大小, 但是会增大通信轮数, 同时, 他们的方法都有着很高的存储开销, 都需要存储每一比特数据的线路标记(wire label); 其次, 这些ORAM的初始化也需要很大的开销.针对以上ORAM存在的问题, Doerner等人提出一种新的ORAM设计, 称为flORAM.与传统SC-ORAM设计不同的是:flORAM将读写隔离, 设计成只写存储(write-only memory, 简称WOM)和只读存储(read-only memory, 简称ROM)两部分, 并将它们看成是分布式ORAM的两个服务器, 加快了读取数据的速度; 其次, flORAM通过存储数据的密文来代替传统存储线路标记, 降低了存储开销; 同时, flORAM创新性地利用基于函数秘密共享(function secret sharing)^[40]的隐私信息检索, 实现了对WOM数据写入和对ROM的数据读取不暴露隐私信息.

考虑到文献[37]中每一次访问都需要O(logN)轮次的交互, 同时, 基于层次模型需要周期性的混洗操作, Wang等人^[69]结合Tree ORAM^[27]与隐私路径检索技术提出了一种基于两服务器的高效ORAM计算协议.在协议中, 客户端通过两服务器的隐私信息检索来读取目标数据块所在的路径.这样的优势在于避免了传统Tree ORAM每一次访问之后更新映射表, 进而避免了迭代构造, 并使得每一次访问只需要与服务器交互一次.同时, Wang等人对隐私路径检索进行了优化, 减少并行读取路径中数据块的次数.在文献[69]中, Wang等人还创新性地提出了在ORAM初始化时随机生成映射表的方法, 降低了安全计算中ORAM初始化的开销.

5.1.2 基于优化电路复杂度的协议设计

与计算复杂度相类似, 由于基于ORAM的安全计算协议在实现中需要编译成电路, 所有的计算过程将以电路形式表达.一种直观的想法就是利用电路的复杂程度来衡量协议的计算性能.从这个角度出发, wang等人^[68]创新性地将电路复杂度(circuit complexity)引入基于ORAM的安全计算协议设计的评估中, 通过计算不同ORAM在实现后电路中的与门电路的数量, 来比较ORAM的性能.

Wang等人还发现, 文献[37]的方案存在两个缺点:(1)由于使用层次模型, 当查找一个数据块时, 需要迭代地计算每一层的hash函数以确定数据块的位置, 这会导致安全协议不能高效地执行; (2)为了解决层次模型中数据块哈希值冲突的问题, 文献[37]也给出了应用布谷鸟哈希^[26]的方法, 但是基于布谷鸟哈希的层次模型需要更大的存储空间.针对这两个问题, Wang等人^[68]提出了一种基于Path ORAM^[17]设计的适用于安全计算的ORAM, 称为Path SC-ORAM.其中应用了3个不经意排序, 使Path ORAM的电路复杂度从理论上性能降低了O(logn)的数量级, 同时还提出了一种启发式的最高效ORAM的设计方式.由于Path ORAM中最复杂的部分在于驱逐操作, 文献[37]中应用不经意排序将驱逐部分的电路优化至O(DlogNloglogN)ω(1)大小.因为有更大的常数级开销, 这在实用性上依然低于传统的O(Dlog²N)大小的电路.

为了避免设计复杂的驱逐电路、优化整体的ORAM性能, Wang等人^[9]进一步优化了在Path ORAM上的电路复杂度, 设计出了Circuit ORAM.这种ORAM将每一次查找数据块的路径与驱逐路径合并.为了达到这个目标, 在原有数据块的基础上增添了两种元数据, 使得一次查找就可以提前知道数据块驱逐所需要的信息, 包括数据块放置的位置等.通过这种方法, Circuit ORAM的性能比文献[37]中启发式渐进最优的ORAM性能提升了5.1倍.

5.2 不经意数据结构的设计

在结合ORAM的安全计算领域, 还有一类研究方向是设计不经意数据结构.与第5.2节研究的角度不同的是, 这一个方向主要是从实现角度设计或者优化ORAM性能, 而之前的方向是从算法、协议层进行设计优化.不同的数据结构的设计通常需要结合具体的使用场景, 例如在图搜索计算, 还是共享数据存储等.在多方计算的SC-ORAM的实现中, 通常需要客户端与服务器的状态进行共享, 因此, 设计和利用不经意数据结构存储数据可以保证访问的隐私性和高效性.

基于文献[36]中ORAM应用于安全计算的思想与文献[8]中利用ORAM构造平均亚线性时间下的安全两方计算协议, Keller等人^[38]首次设计了多种在多方计算中常用的数据结构, 并利用不经意技术进行实现, 其中包括数组、字典、优先队列等.利用文献[38]中的优先队列实现Dijkstra算法可以在O(|E|log⁵|E|+|V|log⁴|V|)的时间内实现单源点最短路径的计算, 并且可以保证源点与汇点的隐私性, 其中, E和V分别表示图中边和点的数量.同时, 文献[38]还证明了利用提出的不经意数据结构对结合安全计算的ORAM进行块初始化(batch initialization), 要比简单地按序初始化提升O(log³N)的数量级.

Wang等人^[39]在文献[38]的基础上一般化不经意数据结构的设计原则, 将其归纳为两点:一种是基于指针(pointer)的技术, 另一种是基于位置(locality)的技术.基于指针的技术通常用于树状ORAM构建中, 通过父节点存储一个指向子节点的指针, 可以在查找父节点到子节点的路径中直接获取子节点的位置, 避免重复地查找映射表, 这样可以降低O(logn)数量级的复杂度.基于位置的技术通常应用于有着二倍维度(doubling dimension)的访问模式图中.图中每一个点被划分至一个簇(cluster)中.每一个簇包含O(logN)个点, 通过图中每一个点对其他簇的访问, 可以追踪整个访问过程.每一个簇可以像ORAM的数据块一样被访问, 这样, 当需要读取或者更新点的信息时候, 先将点所在的簇与其临近的所有簇读入缓冲区, 对于其临近的簇执行虚假访问, 目标点所在的簇执行真实访问, 这样保证了访问的隐私性.

当ORAM直接用于密文数据库系统时, 存在很大的局限性.Hoang等人^[70]对存在的局限性进行分析.

1)  对于面向行的数据库, 在利用ORAM进行改进时, 会将数据库中的每一行作为ORAM中的数据块, 例如SEAL-ORAM^[71].但是这种方案在执行插入、删除或者更新时, 需要移动ORAM中的所有数据块; 同时, 如果在数据库中执行类似统计或者条件查询等列相关操作时, 需要下载ORAM中的所有数据块, 这将导致很大的带宽问题;

2)  另一种方法是将数据库中的每一个数据单元作为ORAM中的数据块, 但是这会增加映射表的大小. Hoang等人^[70]分析:可以利用文献[39]中的思想, 将O(logN)个数据单元存入一个ORAM的数据块中来避免映射表的问题.但是这会增加按行或列查询所有数据单元的请求次数, 不适用于大型数据库.

针对这两个局限性, Hoang等人^[70]提出了两种用于密文数据库系统的不经意数据结构:oblivious matrix structure(OMAT)与oblivious tree structure(OTREE).前者为数据库中每一个表构造不经意的矩阵结构, 可以支持多种查询操作而不需要下载整个ORAM数据库; 后者为基于树的数据库实例提供不经意访问操作.对于不经意条件查询, 利用文献[70]中的OTREE要比利用文献[39]中的方案更高效.

5.3 小结

结合安全计算场景的ORAM与传统意义上客户端-服务器ORAM有较大的不同, 具体总结为以下几点.

(1) 保护对象不同:在安全计算中, 存储的数据由多方共享, 任意一方的访问模式都不能泄露, 而一般ORAM中, 访问模式的保护只针对客户端, 是单向的;

(2) 实现方式不同:在研究结合安全计算ORAM的协议设计时, 需要考虑初始化过程的复杂度, 这一部分往往是通过协议实现的.而一般意义上的ORAM数据库初始化是默认存在的;

(3) 优化策略不同:传统研究的ORAM主要针对客户端与服务器的带宽以及客户端本地的存储, 而结合安全计算场景的ORAM更多地考虑计算的复杂度.

通过分析总结上述的研究工作, 并结合以上与传统ORAM研究的不同, 我们分析总结了结合安全计算ORAM协议目前的研究方向.

●  以优化协议性能为主要目标.与通用的ORAM性能优化一样, 结合安全计算场景的ORAM也存在着复杂度太高的问题, 但是优化角度不同.这里更倾向于降低ORAM在安全计算上的实现复杂度;

●  推广ORAM的使用以实现在更多场景下的安全计算.由于ORAM本身扎实的安全理论基础及其广泛的适用性, 将ORAM迁移到其他安全领域实现多种类的安全计算也是研究热点之一, 例如图计算、社交网络挖掘等.

6 不经意随机访问机研究展望

由于不经意随机访问机本身低效性的特点, 导致其应用于实际的问题更加突出, 例如设计安全存储系统与安全计算协议等.所以, 这项技术目前的研究重点依然在于性能的提升.同时还有一个不容忽视的挑战就是不经意随机访问机应用于实际所产生的额外问题, 例如在安全存储场景中的数据备份问题等.所以, 未来不经意随机访问机研究需要兼顾性能、功能、应用等多方面的因素, 具体表现为:

●  性能的进一步提升.不只局限于传统的讨论客户端与服务器之间的带宽以及客户端本地的存储问题, 还会涉及进一步优化服务器的存储、交互轮数等其他之前很少考虑的指标.在结合安全存储场景下, 也会着重考虑多用户并发访问下系统的响应时间; 在安全计算场景下的计算复杂度等.因此, 这一类性能优化问题将一直是ORAM研究的主流, 这也推动ORAM本身不断的发展;

●  功能的进一步完善.未来的ORAM将会支持更多的操作, 不只支持简单的读写访问, 甚至可以在其上完成较为复杂的数据结构操作, 例如, 可以用读写进行组合实现查询删除等^[27].其他场景下的功能也可以利用不经意数据结构实现(见第5.2节).因此, 这一类方向将促进ORAM应用于实际;

●  实用型ORAM应用系统的出现.对于存储系统而言, 将不仅仅像ObliviStore^[20]和TaoStore^[35]那样的原型系统, 真正可以应用于存储海量数据, 支持多用户并发访问以及快速响应的系统会逐步推出.同时, 对于安全计算, 也会出现基于ORAM的安全计算系统, 或者是安全计算模块, 可以兼容目前大多数分布式计算系统, 例如MapReduce, Spark等.这使得云计算与大数据的技术与安全计算领域相结合.

我们认为, 未来不经意随机访问机研究应该重点包含以下几个方面.

(1) 基于隐私信息检索技术的多指标性能优化的ORAM设计

隐私信息检索技术可以用来优化ORAM的平均带宽(见第3.1.2节)和客户端存储(见第3.3.2节), 相比于一般的优化方案, 隐私信息检索具有两种优点:(1)可以同时解决通用ORAM性能提升中的两个重要指标, 这是其他优化策略所不具有的; (2)这种技术的缺陷很少, 因此今年来受到广泛的关注.以隐私信息检索技术为出发点, 在保证平均带宽和客户端存储最优的情况下优化别的性能指标将是未来性能提升的重点.从第2节的表 2可以看出, 如今在性能优化上平均带宽和客户端存储这两种性能已经达到最优的O(1).但是其他的指标依然存在相对的劣势, 例如数据块的大小、交互轮数等.能否在保证前面两种性能依然是最优的基础上优化其他的性能指标, 是一个非常重要的问题, 继续以隐私信息检索技术为研究对象是未来的一种重要研究趋势.

(2) 不经意并行随机访问机(OPRAM)的设计与实现

OPRAM最初是由Boyle等人提出^[72], 用来解决多主体对ORAM的并行访问问题.与第4节中多用户并发访问存储系统不同的是, OPRAM是从模型层实现, 不参考任何应用场景; 而第4节是ORAM结合安全存储场景设计系统, 需要添加一系列的模块才能从应用层实现.可以将OPRAM理解为支持多用户并发访问的ORAM在模型层的抽象, 因此, OPRAM将更适用于云平台以及多核处理器结构.针对OPRAM的设计依然以性能改进作为驱动力.其衡量指标与传统ORAM类似, 主要是针对通信带宽以及客户端的存储.当OPRAM用于多核计算上时, 也需要考虑计算复杂度的问题.因此, OPRAM作为ORAM在并行性上的扩展, 在保留ORAM所有的能力之外, 也针对一些特殊的应用场景添加额外的功能.这一类设计将ORAM推向更广的应用, 也是未来ORAM研究的重要途径之一.

(3) 基于ORAM的安全计算系统的设计与实现

结合ORAM的安全计算(见第5节)依然以优化计算协议的复杂度作为目前的主流工作.相比于安全多方计算, 这一类工作在保证计算协议的安全性上还保证了每一个计算方访问数据的隐私性.之前已经有一些工作实现了基于安全多方计算的安全计算系统, 例如基于电路技术的安全两方计算系统FairPlay^[73]、多方计算系统FairPlayMP^[74]、基于秘密共享技术的多方计算系统Sharemind^[75]等.但是目前, 结合ORAM的安全计算依然只停留于协议的设计, 还没有出现基于ORAM的安全计算系统.因此, 未来的一个重要研究方向是将结合ORAM的安全计算应用于实际, 设计出实用型的系统.

同时, 针对已有计算系统的改进也是未来的一种研究方向.例如设计实现基于MapReduce, Spark的安全计算模块, 其上使用ORAM来保护计算节点对文件系统或者是内存单元的读写访问.也可以基于流式计算系统Storm或者是Spark Streaming, 在实现快速的流水计算同时, 保护对内存的访问模式, 这种场景对ORAM的响应时间要求会很高.因此, 未来将ORAM结合系统来实现是研究的一种重要的趋势.

7 结束语

不经意随机访问机是当前保护访问模式隐私的重要手段, 其研究受到了学术界的广泛关注, 近几年也有较大的进展, 主要集中于模型在平均带宽与客户端存储上的性能优化以及与安全存储、安全计算领域相结合的应用.但是从目前来看, ORAM在实用性上依然面临严峻的挑战, 未来还有很多的工作值得去做.

本文对不经意随机访问机的研究进行综述, 包括ORAM的相关概念、设计方法以及优化模型性能的常见策略及其优劣性, 讨论了将ORAM用于安全存储系统设计以及安全计算领域的一般性问题, 并对未来不经意随机访问机的依然存在的问题、挑战与趋势进行了分析.期望通过我们的工作, 能给以后的研究者提供有益的借鉴与参考, 为不经意随机访问机的进一步发展做出贡献.

致谢 在此, 我们向对本文的工作给予支持和宝贵建议的评审老师和同行表示衷心的感谢!