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

作者：赵博; 刘晋璐; 秦静^*

来源：密码学报, 2022, 9(05): 899-909.

DOI：10.13868/j.cnki.jcr.000556

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

通配符可搜索加密因能够灵活地支持关键词的部分匹配,在安全存储服务中有重要的应用价值,但大多数现有的通配符可搜索加密方案都未考虑服务器恶意的情况,且利用布隆过滤构造索引,搜索结果存在假阳性.为此,本文提出了一个无假阳性的可验证通配符可搜索加密方案.该方案通过对关键词编码将通配符搜索转化为范围搜索,并利用保序加密保证明文文本字典顺序和密文数值顺序的一致性,对于含任意单字符通配符的关键词包含的明文文本字典区间都对应着确定的密文数值范围,实现了搜索结果无假阳性.进一步,提出有序二叉位图树(ordered binary bitmap tree, OBBT)索引与逐层匹配算法提高了搜索效率.通过在OBBT的叶子节点存储索引关键词对应的验证标签,实现了搜索结果正确性和完整性的验证.安全性分析表明方案是非适应性语义安全的.性能分析表明,相对以往方案搜索效率也有明显提升.

• 单位
  山东大学; 信息安全国家重点实验室; 中国科学院信息工程研究所; 数学学院