Page 305 - 《软件学报》2021年第10期

张明武 等:医疗大数据隐私保护多关键词范围搜索方案 3277

 0 0 b  3 1,3 a  41,4   0 0  b  3 1,3  a  41,4 
ˆ  * S ˆ   0 b  a  0  ,I ˆ  I * S ˆ   0  b   a  0  .
a a  6 2,1 7 2,3  b b  6 2,1 7 2,3 
 a  b     a   b  
 9 3,1 0 0 12 3,4   9 3,1 0 0 12 3,4 
ˆ
显然,  ˆ a * S ˆ a  I ˆ  I b * S 值为 0 矩阵,则检索成功.
b
6 安全性分析

本方案的应用场景为面向医疗云中可搜索加密,我们主要考虑半诚实医疗云服务器.对于外包半诚实云服
务器,云服务器会“诚实地”按照协议的各项流程执行协议,也会按照索引标识符找到对应的安全索引,完成授权
用户搜索请求后,会如实地返回结果.同时,这类云服务器又是“好奇的”,通过陷门以及收集信息去窥探用户查询
的内容以及加密 EHRs 文件的各种信息.
6.1 搜索模式的隐藏

方案在半诚实医疗云中可以实现搜索模式的隐藏:给定搜索向量 ,S 数据拥有者生成两次搜索陷门 TD S 以
,
及 TD 云服务器无法区分 TD S 和 TD 证明云服务器在获得“两个搜索是由相同的关键词生成”的前提下而无
,
S
S
法获取的任何知识,即实现了搜索模式的隐藏,证明过程如下.  



1. 数据拥有者通过搜索向量 S 计算差分向量 S  Q  , S 将 S 排列成为一个 lh 的矩阵 S;
2. 数据拥有者选取两个随机矩阵 B=[ i,j ] lh 以及  B [ , ij l h
] , 计算 B 与 S 以及 B与 S 的哈达马积:
S ˆ  *,  ˆ B   BS S * ; S
ˆ
ˆ
ij
ij
ij
3. 数据拥有者使用划分矩阵 P 对 S 和  S 进行划分,生成 S ˆ a [, ] 和 S ˆ b [, ] 以及  S ˆ a [, ] 和  S ˆ b [, ]. 最后生
ij
1 ˆ
1 ˆ
1 ˆ
1 ˆ 



成搜索陷门 TD S  (M SM S 以及 TD S  (M SM S b ). 


,
()
()
)
,
b
a
1
1
2
a
2
对于云服务器而言,对 TD(S)以及 TD(S)执行匹配算法:
1 ˆ
1 ˆ


ˆ 
I ˆ  *TD (M IM I ˆ   )*(M S M S b ).
,
,
2 b
1 a
a
1
2
ˆ
由方案正确性分析可知:TD(S)与 TD(S)在执行匹配运算后具有相同的查询结果,即匹配文件运算中 I *TD
为 0 矩阵,云服务器无法从匹配算法中获得任何有用的区分信息.若云服务器仍能区分不同检索向量的陷门
ˆ
ˆ
TD(S)和 TD(S),则云服务器不仅能区分 B 和 B,同时能够区分划分矩阵 P 对 S 和  S 的随机划分.而方案中,矩阵
B 和 B均是随机选取的,矩阵 B 每一位置上元素的取值范围为[1,u],而查分矩阵中值为 1 的数量为 v,云服务器
区分 B 和 B的概率为
p  1 .
1 u v
ˆ
ˆ
假定划分矩阵 P 中值为 1 的个数为,则服务器区分划分矩阵 P 对 S 和  S 随机划分的概率为
p  1 .
2 2 
最后,服务器区分 TD(S)和 TD(S)的概率为
P  p p  1 2 1 .
2
u v 
可以得到,云服务器能够区分 TD(S)和 TD(S)取决于随机矩阵 B 中每个位置的取值范围以及差分矩阵和划
分矩阵中 1 的个数.对于一个关键词总数为 n 的搜索系统而言,服务器直接猜测两次搜索是否来自同一个查询
n
成功的概率为 P=1/(2 ).
在本方案中,我们假定随机矩阵 B 每个位置上的取值范围为[1,2],而我们需要搜索关键词总数一半的 EHRs
n/2
文件,则 p 1 =1/(2 ).由于划分矩阵是随机生成的[0,1]矩阵,随机选取的值为 0 或 1 的概率相同,其中,为 1 的个数
n
n/2
n/2,即约为关键词总数 n 的一半,p 2 =1/(2 ).在这种最小假设下,服务器成功区分的概率为 P=p 1 p 2 =1/(2 ).可以
得到:在最小假设下,本文方案中服务器成功区分的概率 P 与服务器直接猜测的概率 P相同.
一般而言,作为范围搜索,一次搜索请求中需搜索的关键词个数远远小于不需要搜索关键词的个数.因此,