基于云端的可验证模式串匹配研究
Research on Cloud-based Verifiable Pattern Matching
可验证模式串匹配,即用户能通过不可信云服务器上的外包文本数据获得可验证的模式串匹配结果.对应的验证问题是很多以安全性为主的大数据应用的基本问题,特别是外包到云服务器的以模式串匹配为基础服务的应用,如大数据库查询,人类基因数据搜索和文本检索等,验证问题尤为重要.但是,当前已有的可验证方案在性能方面仍有优化空间,同时也不支持高效的数据更新.为此,我们展开研究,设计方案以优化性能并解决数据更新的效率问题.以下两点是我们研究工作的主要贡献.首先,我们提出了一种基于哈希函数的可验证模式串匹配方案,相比当前最优方案,该方案的性能提高显著.我们基于有序集合累加器和后缀数组为模式串匹配设计了一种新的可验证数据结构,只涉及简单高效的哈希计算,使得性能提高显著.另外,该方案支持模式串多匹配验证,更加适应实际应用需求.同时该方案也支持公开验证,无须用户存储密钥数据.最后,仿真实验结果证实了该方案的实际性能优于当前最优方案.其次,我们提出了一种动态可验证模式串匹配方案,以支持高效的数据更新.我们通过随机数绑定字符机制切断文本字符间的位置联系,将连续型文本数据转换为离散型集合数据,以实现高效的数据更新,并将验证问题转换为集合成员关系验证问题,最后采用RSA累加器实现我们的动态可验证模式串匹配方案.该方案是第一个支持数据高效更新的可验证方案,方案的部分性能也较已有方案有所提升,降低了数据拥有者和用户的计算存储开销.最后的实验结果也体现了部分性能的优势以及数据更新的实用性.
- 作者：
- 王东宏
- 学位授予单位：
- 深圳大学
- 专业名称：
- 计算机科学与技术
- 授予学位：
- 硕士
- 学位年度：
- 2018年
- 导师姓名：
- 陈剑勇；陈飞
- 中图分类号：
- TP309
- 关键词：
- 模式串匹配；可验证性；可验证数据结构；数据更新
- pattern matching; verifiability; verifiable data structure; data updates;