无假阳性的可验证通配符可搜索加密  

Verifiable Wildcard Searchable Encryption Without False Positive

作　　者：赵博 刘晋璐 秦静[1,2] ZHAO Bo;LIU Jin-Lu;QIN Jing(School of Mathematics,Shandong University,Jinan 250100,China;State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China)

机构地区：[1]山东大学数学学院,济南250100 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100093

出　　处：《密码学报》2022年第5期899-909,共11页Journal of Cryptologic Research

基　　金：国家自然科学基金(62072276,61772311)。

摘　　要：通配符可搜索加密因能够灵活地支持关键词的部分匹配,在安全存储服务中有重要的应用价值,但大多数现有的通配符可搜索加密方案都未考虑服务器恶意的情况,且利用布隆过滤构造索引,搜索结果存在假阳性.为此,本文提出了一个无假阳性的可验证通配符可搜索加密方案.该方案通过对关键词编码将通配符搜索转化为范围搜索,并利用保序加密保证明文文本字典顺序和密文数值顺序的一致性,对于含任意单字符通配符的关键词包含的明文文本字典区间都对应着确定的密文数值范围,实现了搜索结果无假阳性.进一步,提出有序二叉位图树(ordered binary bitmap tree,OBBT)索引与逐层匹配算法提高了搜索效率.通过在OBBT的叶子节点存储索引关键词对应的验证标签,实现了搜索结果正确性和完整性的验证.安全性分析表明方案是非适应性语义安全的.性能分析表明,相对以往方案搜索效率也有明显提升.Wildcard searchable encryption has an important application in secure storage services because it can flexibly support partial matching of keywords. However, most of the existing wildcard searchable encryption schemes do not consider the case that the server is malicious, and use Bloom filter to construct the index, which leads to false positives in search results. This paper proposes a verifiable wildcard searchable encryption scheme without false positive. The proposed scheme converts the wildcard search into a range search by encoding keywords, and uses order-preserving encryption to ensure the consistency of the dictionary order of plaintext and the numerical order of ciphertext. For any keywords containing single-character wildcards, the plaintext dictionary interval corresponds to the determined numerical range of ciphertext, so that the search results have no false positive. Further,this paper proposes the Ordered Binary Bitmap Tree(OBBT) index and layer-by-layer matching algorithm to improve the search efficiency. In addition, by storing verification tags in OBBT leaf nodes, the correctness and integrity of search results can be verified. Finally, the security analysis shows that the proposed scheme is non-adaptive semantically secure. The performance analysis shows that, compared with some existing schemes, the search efficiency is improved significantly.

关 键 词：通配符可搜索加密 保序加密 有序二叉位图树形(OBBT)索引 可验证性 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]