不经意随机访问机在动态对称可搜索加密中的应用
一、引言 随着大数据与云计算技术的迅猛发展，将数据存储到外包服务器上并允许安全地进行动态维护与访问成为一个重要的理论课题，可搜索加密技术（Searchable Encryption, SE）应运而生。 在对外包数据进行加密与访问的过程中，研究表明，仅仅依赖于对数据的加密不足以保护用户数据的隐私，客户端访问数据的存储位置，时间和频率（即访问模式，Access Pattern）可以通过统计推断泄
一、引言
随着大数据与云计算技术的迅猛发展，将数据存储到外包服务器上并允许安全地进行动态维护与访问成为一个重要的理论课题，可搜索加密技术（Searchable Encryption, SE）应运而生。
在对外包数据进行加密与访问的过程中，研究表明，仅仅依赖于对数据的加密不足以保护用户数据的隐私，客户端访问数据的存储位置，时间和频率（即访问模式，Access Pattern）可以通过统计推断泄漏大量有关数据的敏感信息。不经意随机访问机（Oblivious Random Access Machine, ORAM）能够保护访问模式，混淆使得服务器不知道真实访问数据的地址以及对应的原子操作。ORAM的特性使其能够融合到动态对称可搜索加密（Dynamic Symmetric Searchable Encryption, DSSE）中来减少访问过程中的信息泄漏，从而提高方案安全性。
本文首先简要地介绍了不经意随机访问机和对称可搜索加密的相关理论知识，接着简要阐述了多个基于ORAM的SSE方案，最后对于ORAM在SSE中的应用进行总结和对未来可能出现的新技术的展望。
二、相关理论
1、不经意随机访问机（ORAM）
不经意随机访问机是目前保护访问模式的一种重要手段.这一技术的目的是隐藏对真实数据块的访问,使得攻击者不能区分每一次访问是真实还是随机的。ORAM应用于云存储系统可以有效防止攻击者利用访问模式获取隐私信息,减小数据存储系统的攻击面,打破了单纯使用传统加密方式来保护数据隐私的系统框架,为用户提供更完善的安全存储服务。此外ORAM来模拟安全多方计算的执行过程已被证实比传统电路模拟方法更高效,它极大地提升了对于海量输入数据的安全计算性能。但是ORAM也会带来额外的开销,例如为了隐藏访问模式,需要对多个数据块进行访问,增大了客户端与服务器之间的带宽,客户端需要更大的缓存空间来存储从服务器端返回的额外数据块。所以ORAM的实用性还面临很大的挑战。
2、动态对称可搜索加密：前向安全与后向安全
对称可搜索加密的构造基于对称密码原语来设计，一般有两方参与者：数据拥有者与云服务器。整个搜索过程可以归纳为：客户端加密关键字与文件标识符生成可搜索密文并上传，客户端生成检索陷门并上传，服务器返回搜索结果客户端解析获得所需文件。
动态可搜索加密方案允许用户动态地添加或删除可搜索密文，动态对称可搜索加密的形式化定义可以看作由三个多项式时间协议的元组：
Π
=
{
S
e
t
u
p
,
S
e
a
r
c
h
,
U
p
d
a
t
e
}
Π=\{Setup,Search,Update \}
Π={Setup,Search,Update}组成：
( σ , E D B ) ← S e t u p ( λ , D B ) (σ,EDB)←Setup(λ,DB) (σ,EDB)←Setup(λ,DB)：输入初始数据库 D B DB DB，输出加密数据库 E D B EDB EDB和客户端状态 σ σ σ；
(
(
σ
′
,
D
B
(
w
)
)
;
E
D
B
′
)
←
S
e
a
r
c
h
(
(
σ
,
w
)
;
E
D
B
)
((σ',DB(w));EDB')←Search((σ,w); {\,}EDB)
((σ′,DB(w));EDB′)←Search((σ,w);EDB)：客户端向服务器发送搜索请求，输入状态
σ
σ
σ和关键字;
w
w
w，服务器端输入加密数据库
E
D
B
EDB
EDB，客户端更新状态为
σ
′
σ'
σ′并收到包含关键字
w
w
w的文档标识符的集合
D
B
(
w
)
DB(w)
DB(w)，服务器端输出协议后更新的加密数据库
E
D
B
′
EDB'
EDB′。
(
σ
′
,
E
D
B
′
)
←
U
p
d
a
t
e
(
(
σ
,
o
p
,
i
n
d
)
;
E
D
B
)
(σ',EDB')←Update((σ,op,ind);EDB)
(σ′,EDB′)←Update((σ,op,ind);EDB):输入客户端状态
σ
σ
σ，以及对应文件标识符及其成对应操作(添加/删除)，最终服务器端输出已更新的数据库
E
D
B
′
EDB'
EDB′。
对于DSSE方案，我们假设服务器是半可信的，即攻击者在进行关键字搜索查询或更新查询中好奇地推断有用信息并获取隐私，但是服务器端仍正确地执行上述查询操作。“自适应”指攻击者可以自适应地执行查询操作，即观察之前的查询结果之后可以再次发起关键字搜索或更新查询。攻击者在DSSE方案实施过程中除了规定的信息泄露以外无法获得其他信息。我们可以将泄漏量化，定义泄漏函数
L
=
(
L
S
e
t
u
p
,
L
S
e
a
r
c
h
,
L
U
p
d
a
t
e
)
L=(L_{Setup} ,L_{Search} ,L_{Update} )
L=(LSetup,LSearch,LUpdate)，并且分别对应于
S
e
t
u
p
Setup
Setup,
S
e
a
r
c
h
Search
Search和
U
p
d
a
t
e
Update
Update操作中存在的泄漏。攻击者试图区分真实世界的游戏
S
S
E
r
e
a
l
SSE_{real}
SSEreal 和理想世界的游戏
S
S
E
i
d
e
a
l
：
S
S
E
r
e
a
l
SSE_{ideal} ：SSE_{real}
SSEideal：SSEreal 游戏指
D
S
S
E
DSSE
DSSE方案被诚实地执行，攻击者可以观察到所有操作过程中的真实记录；
S
S
E
i
d
e
a
l
SSE_{ideal}
SSEideal 游戏指攻击者可以看到模拟过程来仿造真实过程。这些模拟的过程可以由多项式时间的模拟器S生成并充分学习泄漏函数。最终敌手将输出一个比特存在两种情况：0或者1，即
S
S
E
r
e
a
l
SSE_{real}
SSEreal或者
S
S
E
i
d
e
a
l
SSE_{ideal}
SSEideal 。在通用的安全模型中,每当客户端进行其中一个操作时，敌手只能学习到相应泄漏函数的输出。DSSE方案的适应性安全可以定义为：
我们称一个DSSE方案关于泄漏函数
L
\mathcal{L}
L的集合是满足
L
−
\mathcal{L}-
L−适应性安全的，对于一个多项式时间敌手
A
\mathcal{A}
A,存在一个模拟器
S
S
S使以下不等式成立：
∣
Pr
[
SSE
real
Σ
(
λ
)
=
1
]
−
Pr
[
SSE
ideals,A,L
(
λ
)
=
1
]
∣
≤
n
e
g
l
(
λ
)
\left|\operatorname{Pr}\left[\operatorname{SSE}_{\text {real }}^{\Sigma}(\lambda)=1\right]-\operatorname{Pr}\left[\operatorname{SSE}_{\text {ideals,A,L }}(\lambda)=1\right]\right| \leq negl (\lambda)
∣∣Pr[SSEreal Σ(λ)=1]−Pr[SSEideals,A,L (λ)=1]∣∣≤negl(λ)
前向安全性考虑的是文档更新添加关键字操作的泄漏问题。前向安全性保证了服务器不知道新添加的文档是否包含之前检索的关键字，即以前的搜索操作不能搜到以后的密文，或者说以前的搜索操作与新更新的密文不产生关联关系。不满足前向安全性的DSSE方案会遭受到毁灭性的文件注入攻击，该攻击会高效恢复用户检索的关键字。我们给出前向安全性的形式化定义，即更新阶段的泄漏函数
L
U
p
d
t
(
w
)
\mathcal{L}^{Updt} (w)
LUpdt(w)满足:
L
U
p
d
t
(
w
)
=
L
(
o
p
,
i
d
)
\mathcal{L}^{Updt} (w)=\mathcal{L}(op,id)
LUpdt(w)=L(op,id)
后向安全性考虑的是已删除的文档信息不会在后来关键字搜索查询中泄漏。2017年，Raphael Bost等人提出了三种安全级别强度依次减弱的后向安全性方案：
后向
T
y
p
e
−
I
\pmb{Type-I}
Type−IType−IType−I安全:
L
S
r
c
h
(
w
)
=
L
(
T
i
m
e
D
B
(
w
)
)
\mathcal{L}^{Srch} (w)=\mathcal{L}(\pmb{TimeDB}(w))
LSrch(w)=L(TimeDBTimeDBTimeDB(w))
后向
T
y
p
e
−
I
I
\pmb{Type-II}
Type−IIType−IIType−II安全:
L
S
r
c
h
(
w
)
=
L
(
T
i
m
e
D
B
(
w
)
,
U
p
d
a
t
e
s
(
w
)
)
\mathcal{L}^{Srch} (w)=\mathcal{L}(\pmb{TimeDB}(w),\pmb{Updates}(w))
LSrch(w)=L(TimeDBTimeDBTimeDB(w),UpdatesUpdatesUpdates(w))
后向
T
y
p
e
−
I
I
I
\pmb{Type-III}
Type−IIIType−IIIType−III安全:
L
S
r
c
h
(
w
)
=
L
(
T
i
m
e
D
B
(
w
)
,
U
p
d
a
t
e
s
(
w
)
,
D
e
l
H
i
s
t
(
w
)
)
\mathcal{L}^{Srch} (w)=\mathcal{L}(\pmb{TimeDB}(w),\pmb{Updates}(w),\pmb{DelHist}(w))
LSrch(w)=L(TimeDBTimeDBTimeDB(w),UpdatesUpdatesUpdates(w),DelHistDelHistDelHist(w))
其中
T
i
m
e
D
B
(
w
)
TimeDB(w)
TimeDB(w)代表目前包含关键字
w
w
w的文件和被存的时间，
U
p
d
a
t
e
s
(
w
)
Updates(w)
Updates(w)代表关于
w
w
w被更新的时间戳，
D
e
l
H
i
s
t
(
w
)
DelHist(w)
DelHist(w)代表关于
w
w
w哪次删除对应了哪次添加。
三、ORAM在DSSE中的应用
近年来针对融合ORAM与DSSE的方案设计与研究成为了目前的热点。其中树状模型在DSSE领域的应用最为突出，2016年，Garg等人提出了TWORAM方案，在树状ORAM结构上设置混淆电路(garbled circuit)使得一次关键字搜索仅需两次交互便可获得多个
(
w
,
i
n
d
)
(w,ind)
(w,ind)对的结果。这个过程需要客户端和服务器之间执行大量安全计算来获得多个数据信息，同时还存在混淆电路的重用性问题。基于TWORAM，2017年提出了满足后向安全性的Moneta方案，它用最原始的办法达到了极高的后向安全性：在客户端下载所有操作，移除已经被删除的文档标识符信息，再将对应的未被删除文档标识符信息传输到服务器端来获取文档数据信息。在每一次关键字搜索之后，客户端进行重加密上传至服务器索引部分。这一系列操作导致了大量的通信开销。
另外一种比较热门的解决方案是利用ORAM达到低客户端存储开销的方案。代表方案有基于AVL树和Path-ORAM设计出的不经意隐藏访问位置的Orion方案，客户端只需要存储Path-ORAM中AVL树根节点的位置，对于访问有着N节点的AVL树的一个节点，需要对Path-ORAM做
O
(
l
o
g
N
)
O(logN)
O(logN)次访问。
基于上述分析，我们观察到ORAM本质上需要大量的服务器端存储空间，用空间换高安全性，因为ORAM访问模式保护主要依赖于真实读写数据与其他数据的混淆来完成，这会导致大量虚假块在服务器端存储。同时在ORAM与DSSE相结合的方案中，ORAM可能会出现通信开销较大以及交互轮数过多的问题，因为在相结合方案的关键字搜索过程中需要检索大量文档数据，然而最后满足条件的有效真实数据块可能只有一个。此外在许多其他方案中依然存在客户端存储开销较大等问题，近年来通过递归构造的Path-ORAM得到了有效的解决。
四、总结与展望
我们总结了基于ORAM保护访问模式构造的DSSE方案，在保证安全性的条件下牺牲了存储与计算能力，至今依然存在许多值得继续研究的点：例如近五年来出现了基于环上的Onion ORAM模型，相比经典的Path-ORAM模型实用性更近了一步，是否存在将其与DSSE相结合的方案，使得性能更好？或者是，能不能直接在基础ORAM结构上进行改进，在增大带宽、减小存储、减少数据块大小等方面来优化现有问题？这些猜想亟待验证与解决。
参考文献
[1] Garg S , Mohassel P , Papamanthou C . TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption[C]// Springer, Berlin, Heidelberg. Springer, Berlin, Heidelberg, 2016.
[2] Shi E , Chan H , Stefanov E , et al. Oblivious RAM with O((logN)3) Worst-Case Cost[J]. Springer, Berlin, Heidelberg, 2011.
[3]王贇玲, 陈晓峰. 对称可搜索加密技术研究进展[J]. 电子与信息学报, 2020(10).
[4] Stefanov E , Dijk M V , Shi E , et al. Path ORAM: An Extremely Simple Oblivious RAM Protocol[J]. Journal of the Association for Computing Machinery, 2018, 65(4):18.1-18.26.
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
4
0- 0
已为社区贡献1条内容
所有评论(0)