一种基于BloomFilter的改进型加密文本 模糊搜索机制研究

第34卷第1期控制与决策Vol.34 No.1 2019年1月Control and Decision Jan. 2019 文章编号: 1001-0920(2019)01-0097-08 DOI: 10.13195/j.kzyjc.2017.0802 一种基于BloomFilter的改进型加密文本 模糊搜索机制研究 吴曦,俞能海y,张卫明 (1.中国科学院电磁空间信息重点实验室，合肥230026；2.中国科学技术大学 信息科学技术学院，合肥230026) 摘要:随着云计算的日益普及,为实现共享计算资源、节约经济成本等目的,越来越多的重要数据被从本地外 包迁移至云端.出于对保护云端数据安全和用户隐私等方面的考虑,数据所用者一般倾向对敏感数据进行加密处 理,在此基础上,如何能够对数据开展有效检索处理成为关注的重点.为此,提出一种改进的密文数据多关键字检 索机制,一方面,基于BloomFilter数据结构设计一种新的关键字转换方法,能够在保持模糊搜索功能及识别率的 同时,有效降低数据索引规模;另一方面,基于动态混淆参数调节的思路改进相似度评估算法,以提高数据的加密 强度,并且能很好地反映用户的检索偏好.实验结果验证了所提机制是可行和高效的. 关键词:云计算；隐私保护；可搜索加密；模糊检索；BloomFilter 中图分类号: TP37文献标志码: A An improved multi-keyword fuzzy search scheme based on BloomFilter over encrypted text WU Xi, YU Neng-haiy, ZHANG Wei-ming (1. CyberspaceInformationLab，ChineseAcademyofScience，Hefei230026，China；2. SchoolofInformationScience and Technology，University of Science and Technology of China，Hefei 230026，China) Abstract: With the popularity of the cloud computing, more and more data owners are motivated to outsource their complex data from local sites to the cloud for great shared comuputing sources and economic savings. But for protecting data security and privacy, sensitive data have to be encrypted before outsourcing, which obsoletes some traditional data utilization, for example the multi-keywords search. In this paper, we develop a enhanced multi-keywords fuzzy search scheme. On one hand, a novel method is designed to transfor keywords based on BloomFilter, which can reduce the index length effectively while keeping the fuzzy search rate. On the other hand, the similarity measure method is improved based on dynamic adaption of confusion parameters to achieve various stringent privacy requirements, which shows the data user’s favoritism better. Experiments on real-world data show that the proposed scheme is feasible, effective and accurate. Keywords: cloud computing；privacy-preserving；searchable encryption；fuzzy search；BloomFilter 0引言 随着云计算技术的日益成熟,其架构与产品已惠 及越来越多的用户,特别是云存储服务,成为大数据 时代最为普及的云计算应用之一.对于拥有和管理 着海量数据的终端用户,可以将数据外包至云服务器 上,以大幅减轻本地的计算和存储压力,降低因各类 事故或人为因素造成的数据损坏与丢失风险.与此 同时,随着云存储的广泛应用,如何保护云端数据的 安全和内容隐私成为最值得关注的问题之一.特别 是对于机密性或私密性较高的诸如健康、经济、军 事等相关领域的数据,数据拥有者会倾向于将其进行 加密之后再上传至云服务器,有许多传统的数据加密 方法可以用以实现这个目的.然而,在云计算环境和 数据加密上传的背景下,产生了一些新的问题与挑 战,主要体现在两个方面:一是数据通信量的大幅增 加给云环境网络带宽及能耗带来的压力,这一问题在 收稿日期: 2017-06-22；修回日期: 2017-12-23. 责任编委:刘德荣. 作者简介:吴曦(1980 ),男,博士生,从事信息安全及其应用的研究；俞能海(1964 ),男,教授,博士,从事网络安 全、多媒体内容安全等研究. y通讯作者. E-mail: ynh@ustc.edu.cn. 98控制与决策第34卷 混合云模式下移动终端大量应用普及的情况下尤为 突出,移动设备的计算能力和电池容量都相对有限, 大数据量的加密信息传输和加解密运算会严重降低 设备应用效率;二是传统加密方法对数据应用带来 了挑战,即由于数据的加密,使得云服务器端除了简 单的数据存储之外,无法执行更多的信息处理与运算 功能,从而影响了云计算根本优势的发挥,这也是本 文关注的重点. 总体而言,云计算环境下数据的隐私保护和安 全保密要求与云计算的有效应用形成了矛盾.聚焦 应对上述两类问题,从实际应用最为广泛的数据搜 索操作入手,面向能够在数据加密的前提下,由云服 务器执行如模糊检索等功能相对丰富、能够反映用 户查询偏好的数据检索需求开展研究.近年来,研究 者们针对加密数据搜索提出了一些良好的思路和方 法[1-7].从存在不足的角度而言,这些机制有的只能支 持单关键字搜索,有的执行效率较低,并且大多不支 持模糊搜索,很大程度地制约了算法的实用性. Cao 等[8]提出了基于Bloom Filter构建索引,运用局部敏 感哈希技术(LSH)实现支持模糊查询的机制;Fu等[9] 为了提升检索效率和精度,提出了一种改进的数据 结构,用以表达数据的索引.以上机制的不足在于数 据索引生成时初始化数据结构的规模仍然较大,影响 了实用效果,且检索算法无法有效反映用户的检索偏 好,本文重点针对这些开展研究. 目前的主要相关研究可分为不支持模糊查询的 密文检索机制和支持模糊查询的密文搜索机制两 类.其中不支持模糊查询的密文检索机制主要包括 以下两小类:1)单关键字搜索:文献[3]提出了一种基 于对称密码学算法的可搜索加密方案,其核心思想 是对密文文件进行按序扫描,计算是否存在与给定的 关键字的加密形式相匹配的内容,该算法的问题在于 检索效率不高.针对此问题,文献[4]提出了基于安全 索引的快速可搜索加密方案,索引结构是基于Bloom Filter来实现的;文献[5]研究提出了基于公钥密码的 可搜索加密方案PEKS,提升了密钥传递的安全性,但 仍然面临着计算开销很大的难题;文献[6]基于身份 加密(Identity based encryption)和对称密码学分别提 出了两种可搜索加密的方案,其应用场景为在加密后 的审计日志上进行关键字搜索,该方案的特点为需要 服务器端对文件进行加密,而且用户在进行检索时需 要访问服务器并自己承担搜索开销.为了进一步减 少用户在检索时的计算量并提高用户的检索体验,文 献[7]运用保序加密(Order preserving encryption)来 实现可支持结果排序的密文检索,云服务器可在不 掌握明文信息的情况下对密文索引进行快速排序并 按关联性返回结果,保序加密泄露了一定程度的密文 信息,其安全性有待进一步加强. 2)多关键字搜索:为 满足实际应用中常见的多关键字搜索需求,相关研 究得到了广泛的关注.文献[10]基于对称密码学和 公钥密码学分别提出了支持连接关键字搜索的可搜 索加密机制;文献[11]提出了多接受者公钥加密方法 (Multi-receiver public key encryption);文献[12]在先 前的单关键字可排序搜索的工作上进一步拓展,采 用kNN的思想实现了多关键字可排序搜索;文献[13- 14]改进地提出了基于相似性排序的可验证的隐私 保护多关键字的文本搜索;文献[15]提出了一个安全 的多关键字排序的可搜索加密方案,支持索引动态更 新. 支持模糊查询的密文搜索机制主要针对用户可 能的错误输入以及其他情况导致的无法精确进行关 键字搜索的场景.文献[13]研究了密文域上的模糊 关键字搜索问题,采用编辑距离的概念来界定哪些词 属于模糊检索范围内的词,即在某个编辑距离之内的 词都视作该关键字的变形,在上传和检索时所有该关 键字的变形都会被一并操作,这样的方案一方面实现 了其所提出的模糊检索,另一方面却线性增长了存储 开销和用户方面因为需要对不精确的结果进行进一 步筛选而带来的网络和计算开销.此后,文献[9]提出 了使用局部敏感哈希来实现多关键字的模糊搜索,此 方案是直接的模糊匹配,不需要将关键字的所有可能 拼写列举出来,不会增加索引的大小,但检索效率受 到一定影响. 1问题建模 1.1系统模型 作为研究基础,定义一个云存储和数据搜索系统 模型,其中包含3类角色:数据所有者、数据查询者 和云环境.云环境由多个私有和公有云构成,如图1 所示.在该系统模型中,数据所有者拥有数据文件集, 出于对本地存储容量不足、计算能力有限以及数据 集中管理规定等多方面的考虑,将该数据集上传至云 环境中;出于对安全保密的考虑,数据集要以加密的 形式上传,同时,这些上传的加密数据可能会根据管 理和使用的具体要求存储在云环境中不同的私有或 公有云服务器上.经授权的数据查询者可以向云环 境发起数据搜索请求,获取云环境反馈的相关数据文 件.假定云服务器是“诚实且好奇”的[16],即云服务器 在准确完成用户请求的操作同时,可能会试图从用户 第1期吴曦等:一种基于BloomFilter的改进型加密文本模糊搜索机制研究99 的搜索请求及返回结果等数据中分析获取其他敏感 的信息. UNI68c0 UNI7d22UNI8bf7 UNI6c42 UNI68c0UNI7d22UNI7ed3 UNI679c UNI4e91UNI73afUNI5883 UNI6570UNI636eUNI52a0UNI5bc6UNI4e0aUNI4f20 UNI6570UNI636eUNI6240UNI6709UNI8005 Dataowner UNI6570UNI636eUNI67e5UNI8be2UNI8005 Datauser UNI8bbfUNI95eeUNI63a7UNI5236UNI53c2UNI6570 UNI68c0UNI7d22UNI63a7UNI5236UNI53c2UNI6570 UNI68c0UNI7d22UNI8bf7UNI6c42UNI68c0UNI7d22UNI7ed3UNI679c 图1系统模型 1.2应用模型 在上述系统模型之下,围绕主要的应用需求,应 用模型可以作以下两类描述. 1.2.1安全搜索模型 每个云服务器可以获得加密的数据文件和索引, 记录用户的历史请求陷门,并统计相关密文频率信 息,云服务器可以据此利用比值分析(Scale analysis) 等方法推测搜索关键字等信息,因此安全的搜索模型 需要有效地抵御这一风险.在此基础上,搜索模型应 尽可能提供更为友好的功能,比如模糊查询、反映用 户偏好等. 1.2.2效率提升模型 在云环境中,降低云服务器与终端的通信量、提 升云服务器计算能力使用率是很重要的挑战.按照 传统的方式,在搜索过程中,终端需要对从云服务器 返回的数据索引进行解密,计算相关度并排序,再将 排序结果反馈给云服务器提取相关数据文件.在这 样的搜索过程中,云服务器与用户交互次数过多,必 然会使带宽压力陡增,同时也影响了云服务器计算优 势的发挥.效率提升模型应充分体现云计算高效率 低能耗的设计理念,将更多的计算压力释放到云服务 器端[17],同时减少应用通信的数据量,降低终端与服 务器的通信传输压力. 1.3设计目标 本研究的主要目标是:在已有多关键字密文搜 索算法[9,12,18]的研究基础上,聚焦保护数据安全、拓 展搜索功能、反映查询者偏好等方面,设计实现一个 有效的密文搜索机制,解决上述模型中面临的主要问 题,并对其中的密文搜索核心算法开展有针对性的设 计和改进. 2核心算法设计 2.1改进的密文搜索算法 2.1.1预备知识 1)布隆过滤器(Bloom Filter). Bloom Filter是一 种具有很高空间效率的数据结构,它利用队列来表示 一个集合,可以确定某个元素是否属于该集合.初始 化的时候,将队列中所有的位置都置为0,对于一个给 定的集合S = (a1;a2; ;an),使用l个独立的哈希 函数,形如H =fhijhi : S!m;1 ⩽ i ⩽ lg,通过将队 列相应的位置置为1,将属于S的元素a逐一插入到 Bloom Filter中.当要检查某个元素q是否属于S时, 通过哈希函数获取q在Bloom Filter队列中对应的l 个位置,如果有任何一个位置为0,则q /2 S;对应的l 个位置均为1,则要么q2S,要么出现了“假阳性”,实 际上q /2S.假阳性概率为(1 e lnm )l,当l = mn ln2 时,最理想的假阳性概率为(1/2)l. 2)局部敏感哈希(Locality-sensitivehashing). LSH 是一个用于解决在高维空间中近似距离搜索问题的 算法,该算法能够将相似的输入参数以较大的概率映 射到同一区间中.对于一个局部敏感哈希函数H,其 是(r1;r2;p1;p2)敏感的,则对于任意两个输入参数x 和y,满足8 : Pr[h(x) = h(y)] ⩾ p1; d(x;y) ⩽ r1; Pr[h(x) = h(y)] ⩽ p1; d(x;y) ⩾ r2: 其中d(x;y)为参数x与y之间的距离. 2.1.2主要技术 1)关键字集合压缩.目标数据集F = (F1;F2; ;Fn)中往往包含大量文件,其中有海量的关键字 W = (w1;w2; ;wm).为了提高索引生成效率(特 别是在云环境中,对网络带宽和数据传输量要求较高 的情况下),尽可能地控制索引规模.采用文献[9]的 方法,首先进行数据预处理,运用传统的Porter分词算 法[20]对从数据集中提取出的关键字集合进行“词根” 过滤,例如“walks”、“walking”、“walked”等近似的 关键字,词根均为“walk”.后续的检索操作基于词根 进行,大幅减少了计算量,且由于该操作只是在索引 生成时执行一次,对整个系统的运行效率不会产生过 大的影响. 2)关键字转换与索引生成.关键字转换是本研 究所提机制中最关键的步骤.与文献[9,17]中类似, 利用映射向量来表示关键字.在文献[9]中,使用了 26 26比特的大向量来对关键字进行表示.在文献 [17]中,将相关向量的长度降为130比特,但在数据集 合检索量较大的情况下,这样的索引规模仍将对算法 100控制与决策第34卷 执行效率产生负面影响,存在进一步优化的空间.因 此,本文针对进一步缩小映射向量长度开展研究.首 先通过统计研究,构建一个普适的关键字匹配特征体 系,这些特征能有效反映索引关键字与检索关键字之 间的近似关系;然后依据这个特征体系,将关键字转 换到映射向量中去;进一步,为了更好地反映数据查 询者的偏好,向索引及查询的关键字映射向量中分别 嵌入相关统计信息,进而基于这样的关键字映射向量 进行可搜索加密. i)特征体系.注意到,作为数据查询者,输入检索 关键字时可能会出错,但在大多数情况下不会错得 很“离谱”,也就是说,即使在错误拼写的情况下,准 确关键字与有误关键字之间仍存在一定的关联关系, 通过突出体现这种关联关系的特征,能够有效地表达 准确关键字与有误关键字的相似性.经过统计分析, 提出两项最有代表性的特征,一是准确关键字与有误 关键字首字母一致且长度相同;二是准确关键字与 有误关键字包含某个字母的位置和数量相同.因此, 将上述两点作为设计判断关键字近似特征体系的基 本依据.需要强调的是,特征体系各成员之间是相互 关联的有机整体,通过动态调节不同拼写出错情况下 的特征权值,应尽可能降低对某些特征成员的依赖程 度.接下来的问题在于,如何在关键字的映射向量中 以尽量短的长度有效表达这些特征,以及特征之间的 权值如何分配. ii)基本算法.在所提的关键字转换算法中,映射 向量的总长为87个比特,将每个关键字分割为4个部 分表示,如图2所示.其中:首字母标识字段由5个比 特构成,用于通过二进制数表示关键字的首字母是哪 一个;关键字长标识字段由4个比特构成,用于通过 二进制数表示关键字总长度;包含字母标识字段由 26个比特构成,用于表示关键字中包含哪些字母;包 含字母数量标识字段由52个比特构成,用于表示关 键字所包含的字母数量分别是几个. UNI9996UNI5b57UNI6bcd UNI6807UNI8bc6UNI5b57UNI6bb5 UNI5173UNI952eUNI5b57UNI957f UNI6807UNI8bc6UNI5b57UNI6bb5 UNI5305UNI542bUNI5b57UNI6bcdUNI6570UNI91cf UNI6807UNI8bc6UNI5b57UNI6bb5 UNI5305UNI542bUNI5b57UNI6bcd UNI6807UNI8bc6UNI5b57UNI6bb5 图2映射向量构成 对于关键字“hello”,可以转换为f′8′; ′5′; ′e′; ′h′; ′l′; ′o′; 1;1;2;1g,进而通过算法向87比特映射向量 中的相应位置赋值.关键字转换成映射向量的细节 由以下伪代码描述. input: A plain-text keyword set W; A null vector {0,1}87 output: A mapping-vector V for Wi W1 to W0 do Stem Wi to STi whose length is sti, Translate STi to STi[j]; and generate a vector{yjyj[j] = 1;0 j sti; and generate a vector {STYijSTY[j] = 0;0 ⩽ k ⩽ 86}; for STi[j] STi do set STi[1] to a new element STYi[]; set sti to a new element STYi[]; for k = 1 to k = j 1 do if STi[j] = STi[k] then y[j] + +; end end for STYi[0] to STYi[86] do Set all corresponding position inf0;1g87 to 1; Set the rest position to 0; Output the vector VWi for the keyword Wi; end Output the V =fVWijWi2Wg; end end iii)索引生成.通过上述算法的表示,一个有拼写 错误的关键字可以大概率地与准确的关键字保持近 似性,由于用向量来表示关键字,这种近似性可以通 过欧氏距离进行测量.接下来,将关键字映射向量作 为输入,利用布隆过滤器生成关键字索引.通过选用 合适的局部敏感哈希函数,两个相近的输入能够被大 概率地映射到布隆过滤器的相同索引输出向量,最 终使得关键字模糊搜索得以实现.为了更好地反映 用户偏好,检索到更有用的文档,本文提出在布隆过 滤器的输出向量中嵌入统计信息,对索引向量嵌入 关键字的词频(TF)均值TF,对查询向量嵌入关键字 的文档频率倒数(IDF)均值IDF.这样,当查询向量中 包含文档频率较低即重要性更强的关键字时,对应的 TF和IDF数值将会增大,并在密文搜索过程中通过 TF IDF体现在最终的查询相似度数值中.至此,完 成关键字转换和索引生成的全部过程. 3)基于改进的安全内积相似度评估的搜索.在 关键字转换为映射向量,并通过局部敏感哈希函数 插入布隆过滤器的基础上,为保护数据在云服务器 端的安全和隐私,需要对索引和搜索关键字映射向量 进行加密,同时在云服务器端不解密的前提下进行搜 第1期吴曦等:一种基于BloomFilter的改进型加密文本模糊搜索机制研究101 索.采用安全内积相似度计算作为基本思路,主要步 骤如下. i)密钥生成.密钥SK由数据所有者生成,可以表 示为三元组fS;M1;M2g,其中包括一个jTjbit的随机 生成向量S2f0;1gm和两个jTj jTj的可逆随机矩 阵fM1;M2g;jTj为存储索引的布隆过滤器长度.如 果数据查询者即为数据所有者,则密钥在本地生成并 处理;如果数据查询者为云环境中其他用户,则需采 用离线拷贝、广播加密或其他方式进行安全传递,还 需考虑管理与传输的效率问题,关于这方面内容非本 论文重点,可另行研究. ii)关键字向量加密.利用随机向量作为指示器, 将每个索引关键字向量I按以下规则随机分割成两 个向量fI′;I′′g:如果Si 2 S为1,令I′i = 12I;I′′i = 1 2I,否则令I ′ i = I ′′ i .利用fM1;M2g分别对这两个随 机向量进行乘运算,生成加密的索引向量I : fMT1 I′; MT2 I′′g,利用同样的方法对整个文档集F生成加密 索引集IF.类似地,对每个查询关键字向量Q进行加 密,生成加密查询向量Q :fM 11 Q′;M 12 Q′′g. iii)相似度评估.利用索引关键字与查询关键字 向量的内积,即计算两向量之间的余弦夹角,能够实 现在不对关键字解密的前提下,对两者的相似度进行 评估,有 Sim_Score(DI;Q) = Sim_Score(DI;Q) = I Q = MT1 I′ M 11 Q′ + MT2 I′′ M 12 Q′′ = I Q = cos(I;Q): 从安全性角度分析,对于索引和查询关键字向 量,只要保证密钥SK三元组的机密性,索引IF或查 询向量Q就难以通过计算被逆推出来.但是,上述算 法的问题在于,同样的检索关键字得到的相似度数值 是相同的,如果云服务器能够跟踪访问节点和记录相 似度结果,则可以发起已知密文攻击,根据相同的相 似度数值统计,分析某个关键字的相似度分布,并可 能关联推测和识别出该关键字.因此,基本思路存在 着较大的安全隐患,这在对机密性要求较高的云环 境中是不可接受的.本文提出根据每次检索的相对 随机性动态变化地调节原始密钥和插入哑元关键字 数的思路,通过引入与每个独立检索行为相关的更为 随机的混淆参数,对数据加密和安全检索算法加以改 进. iv)算法改进.两个混淆参数定义如下:检索目标 云服务器的数据集合保密等级Mj = fmjg;mj = 1;2; ;5;检索关键字数目Cs =fcsg;cs = 1;2; . a)密钥生成与加密阶段的改进.对于索引向量 I,将密钥三元组fS;M1;M2g扩展为四元组fS;Mj; M1;M2g,其中每个元素Ii 2 I,按以下规则分割成 fI′i;I′′ig:如果Si 2 S为1,则令I′i = 1M j I + r;I′′i = Mj 1Mj I + r,否则令I ′ i = I ′′ i .进而通过随 机可逆矩阵fM1;M2g将索引向量I加密为I : fMT1 I′;MT2 I′′g,实现对索引向量更为随机的分割与 加密. 对于查询向量Q,将密钥三元组fS;M1;M2g扩 展为五元组fS;Mj;Cs;M1;M2g,首先计算Mj与Cs 的平均值 = 12(Mj + Cs),进而计算均方差 =√ 1 2[(Mj ) 2 + (C s ) 2],查询向量Q中的每个 元素Qi 2 Q,按以下规则分割成fQ′i;Q′′ig:如果Si 2 S为0,则令I′i = 1 I + r;I′′i = 1 I + r,否则令 Q′i = Q′′i .进而,通过随机可逆矩阵fM1;M2g将查询 向量Q加密为Q :fM 11 Q′;M 12 Q′′g. b)相似度计算阶段的改进. Cheng等[2]介绍了一 种安全的kNN算法,通过引入新的随机数,将相似度 计算改进为rI Q,提高了算法的加密强度,但仍存在 遭受比值攻击的隐患;Cao等[8]修改了这种安全kNN 技术,对加密三元组向量及矩阵进行维度扩展,向每 个查询向量的扩展维中引入新的“哑元”随机数,将 相似度计算改进为rI Q + ∑ “vi,进一步增强了安 全强度,但由于每次检索过程中选取的随机变量“i数 量是固定的,使得 ∑ “vi的分布仍存在规律性,在面 临大数据分析时仍存在较大安全隐患.为了进一步 抵消这种相对固定属性,提出利用前述引入的“混淆 参数”对插入哑元关键字数进行扰动的改进思路,即 根据每次查询的目标文件集合保密等级Mj和查询 关键字数目Cs,对加密三元组向量及矩阵进行动态 维度扩展,即每次相似度计算插入的关键字数量为 MjQ) = I Q“ = MT1 I′ M 11 Q′ + MT2 I′′ M 12 Q′′ + Mj另一种思 路[9]在此基础上进行了改进,使用一个130比特的 uni-gram向量进行关键字转换.本文从关键字特征体 系的角度设计提出的关键字映射向量长度仅为87比 特,与现有技术相比,能够使生成索引的初始向量总 长度下降50% 70%.就针对不同拼写错误的表达 而言,可以从以下几类示例来分析. 1)有一个字母错误拼写:比如,关键字“work” {′23′;′4′;′w′,′o′,′r′,′k′;1,1,1,1}被错误拼写为“wark” {′23′; ′4′; ′w′; ′a′; ′r′; ′k′;1;1;1;1},首字母和长度未 变,而该特征权值占比较大,因此正确与错误的关键 字的欧式距离小于p2,优于现有技术中的数值. 2)两个字母拼写颠倒:仍以“work”为例,如除首 字母外的任意两字母拼写颠倒,映射向量的表达完全 一致,因此正确与错误的关键字的欧式距离为0. 3)少写或多写一个字母:比如,关键字“work” {′23′;′ 4′;′ w′;′ o′;′ r′;′ k′;1;1;1;1}被错误拼写成 “wok”{′23′;′ 3′;′ w′; ′o′;′ k′;1;1;1},则通过权重调节, 欧氏距离小于3,接近现有技术中的数值;如被错误拼 写成“worrk”{′23′;′ 5′;′ w′;′ o′;′ r′;′ k′;1;2;1;1},则通 过权重调节,欧氏距离小于p2,优于现有技术中的数 值.对比结果也体现了前述通过权重调节平衡关键 字相似度对特征体系各成员依赖程度的观点. 就检索机制的安全性而言,在加密阶段,通过密 钥元组的扩展和算法改进,使得对索引和查询向量的 分割更加随机,实现了更为安全的数据加密.在相似 度计算与评估阶段,本研究与现有机制的思路都是通 过插入随机数来提升安全性,因此可以针对以下两种 情况进行分析. 1)唯密文可知模式. 定理1在唯密文可知模式下,本文所提机制比 现有机制更加安全. 证明现有机制中,若通过插入一个随机数来混 淆相同索引及查询之间的关联性,则两次查询中该 随机数相同的概率p = 1v;若插入固定的n个随机 数“i,则两次查询中随机数之和相同的概率仍为固定 值.本文提出的对每次查询中插入随机数进行动态 调节,任意两次查询中 Mj2;0:56;0:28)-LSH来构建索引,BloomFilter长度 设为m = 6000;l = 30;k = 10.与现有研究类似,在 查询关键字中随机选择替换一个字母,并在一个查询 中设置多于两个关键字. 3.1效率 1)索引生成与加密.虽然索引生成主要是在初 始化时运行,但在实际应用中,随着新的文档和关键 字的补充,不可避免会进行更新,陷门生成则是在每 个检索过程都要做的操作.索引生成针对每个文件 (包括词根提取和布隆过滤器)生成两个步骤,如图3 所示.根据文件包含的关键字数目不同,这两个步骤 的时间都呈线性增长,但由于使用了本文所提的改 进索引生成机制,每个关键字映射向量长度大幅缩 短.因此,与现有机制相比,索引生成效率有较大提 升,同时实现了对构建索引所需布隆过滤器长度的适 当缩减.如图4所示,索引加密主要通过矩阵的相乘, 其时间消耗随文件数量的增加呈线性增长,但本机制 加密效率有20%左右的提升. 0 2 4 6 8 10 120 100 200 300 400 500 UNI5173UNI952eUNI5b57UNI6570UNI91cf UNI65f6UNI95f4 ms/ UNI8bcdUNI6839UNI63d0UNI53d6UNI8017UNI65f6 UNI5e03UNI9686UNI8fc7UNI6e21UNI5668UNI751fUNI6210UNI8017UNI65f6 图3单文件关键字词根提取及索引构建耗时 第1期吴曦等:一种基于BloomFilter的改进型加密文本模糊搜索机制研究103 0.5 1.0 1.5 2.5 3.00 100 200 250 300 350 UNI6587UNI4ef6UNI6570UNI91cf/103 UNI52a0UNI5bc6UNI65f6UNI95f4 s/ 2.0 150 50 UNI672cUNI6587UNI7b97UNI6cd5UNI7d22UNI5f15UNI52a0UNI5bc6UNI8017UNI65f6UNI73b0UNI6709UNI7b97UNI6cd5UNI7d22UNI5f15UNI52a0UNI5bc6UNI8017UNI65f6 图4完整索引加密时间 2)搜索时间.由于本文基于对每个文件对应的 索引进行搜索,影响搜索时间的重要因素在于目标文 件数量.图5显示,在查询关键字k = 10的情况下,搜 索时间随文件数量的增加呈线性增长,由于索引规模 的下降,搜索效率略有提升.同时,不论查询关键字数 量为多少,其都将被映射到一个布隆过滤器中,因此 关键字数量的多少对搜索时间的影响很小,图6显示 了这一结论. 1.0 1.4 1.8 2.6 3.01 3 4 5 UNI6587UNI4ef6UNI6570UNI91cf/103 UNI641cUNI7d22UNI65f6UNI95f4 s/ 2.2 2 UNI672cUNI6587UNI7b97UNI6cd5UNI641cUNI7d22UNI8017UNI65f6 UNI73b0UNI6709UNI7b97UNI6cd5UNI641cUNI7d22UNI8017UNI65f6 图5不同文件集规模下的搜索时间 0 10 15 250 3 4 5 UNI67e5UNI8be2UNI5173UNI952eUNI5b57UNI6570UNI91cf UNI641cUNI7d22UNI65f6UNI95f4 s/ 20 1 UNI672cUNI6587UNI7b97UNI6cd5UNI641cUNI7d22UNI8017UNI65f6 UNI73b0UNI6709UNI7b97UNI6cd5UNI641cUNI7d22UNI8017UNI65f6 2 图6不同查询关键字数量下的搜索时间 3.2准确率 本文重点关注的是向数据查询者返回top-k个 相关的结果,因此主要使用准确率Pr来衡量结果,根 据前述的规则对查询关键字进行模糊.其中,Pr = tp/tp + fp;tp为“真阳性”结果,fp为“假阳性”结果. 图7显示:在关键字准确的情况下,随着搜索关键字 数量的增加,由于“假阳性”的产生,搜索准确率Pr逐 步小幅下降;在引入模糊关键字的情况下,随着搜索 关键字数量的增加,准确率Pr同样开始有小幅下降, 但随着关键字数量的进一步增加,准确率又逐步回 升.这是因为受模糊关键字引起“假阳性”的影响, 随着关键字数量增加,准确率反而会逐步下降. 0 2 6 100.80 0.92 0.96 1.00 UNI5173UNI952eUNI5b57UNI6570UNI91cf UNI641cUNI7d22UNI51c6UNI786eUNI7387 8 0.84 UNI672cUNI6587UNI7b97UNI6cd5UNI6a21UNI7ccaUNI5173UNI952eUNI5b57 UNI73b0UNI6709UNI7b97UNI6cd5UNI6a21UNI7ccaUNI5173UNI952eUNI5b57 0.88 4 UNI672cUNI6587UNI7b97UNI6cd5UNI51c6UNI786eUNI5173UNI952eUNI5b57 图7准确及模糊关键字条件下的搜索准确率 同时,对于两种模糊关键字情况,图7显示:1)当 关键字中有两个字母顺序颠倒时,由于构建的映射向 量是相同的,转换的索引与准确关键字是一致的,因 此对准确率不产生影响;2)当关键字中增加或减少 一个字母时,总体上看,与准确关键字搜索相比,会一 定程度地降低准确率,且增加字母比减少字母降低的 作用更大,但与现有研究中的模糊关键字搜索准确率 相比,仍有一定程度提高,主要原因是本文所提关键 字转换机制使得模糊关键字与准确关键字之间的距 离更接近. 3.3相似度变化率 关于相似度计算结果的加密保护,采用“相似度 变化率”来评估,即在运用固定数目的哑元插入和根 据混淆参数动态调节数目的哑元插入两种算法返回 同样数量k个查询结果的前提下,实际属于top-k中 的文档相似度排序发生变化的比率.图8显示,根据 混淆参数动态调节数目的哑元插入算法能够使更大 比例的相似度排序发生变化,从而为查询提供更强的 隐私保护. 60 80 120 14020 60 70 80 UNI67e5UNI8be2UNI8fd4UNI56deUNI7ed3UNI679cUNI6587UNI6863UNI6570 UNI76f8UNI4f3cUNI5ea6UNI53d8UNI5316UNI7387 /% 30 UNI672cUNI6587UNI7b97UNI6cd5 40 100 UNI73b0UNI6709UNI7b97UNI6cd5 50 图8不同算法条件下的相似度变化率 4结论 本文研究了在云环境中数据加密保护条件下,针 对可支持模糊检索的多关键字搜索问题.基于现有 技术,提出了一种能够在有效处理各种拼写错误的 基础上,更为节约存储空间的关键字映射向量表达方 104控制与决策第34卷 法,并针对如何更准确检索数据和进一步降低安全隐 患,研究改进了相似度评估算法.实验结果表明,所提 机制和算法是可行和实用的.未来的工作将重点聚 焦在:1)如何更高效地进行索引添加更新;2)如何进 一步提升密文搜索效率;3)如何借鉴明文检索技术, 在密文域从语义的角度表达用户检索意图,从而进一 步