加密数据上的动态相似性查询

摘要

信息时代的来临使得越来越密集的数据需要被存储和计算。传统的数据存储与管理方式已不能满足大规模数据的需求。将数据存储在云服务器上以减轻本地的维护和管理开销成为越来越多企业机构和个人用户的不二之选。但是对于私密数据,若直接将其存储在不完全可信的云服务器上,安全性和隐私性将会受到严重威胁。最简单直接的解决方式就是将数据加密之后再存储于云端,但是传统的加密算法会使密文上的操作变得更加复杂,例如最基本的查询操作。在这样需求的驱使下,允许用户直接在密文上查询的可搜索加密技术应运而生。传统的可搜索加密方案是针对静态数据设计的,索引建立完成后,不允许实时增删数据集。只有少部分动态可搜索加密方案提供数据的动态更新功能。最近提出的文件注入型攻击强调了动态可搜索加密中前向安全的重要性。为了阻止此类攻击,部分方案通过隐藏与先前查询匹配的新添加文件信息,达到前向安全的目的,然而方案的效率并不乐观。另一方面,对于相似性查询的需求,很少有方案将前向安全的动态可搜索加密方案和相似性查询结合。针对以上问题,本文提出并实现了一个适用于半可信服务器,基于加密数据的前向安全动态相似性查询方案。首先,针对现有的动态可搜索加密方案无法实现高效的相似性查询这一问题,本文使用了用于解决高维数据上最近邻查找的局部敏感哈希(Locality Sensitive Hashing,LSH)算法。通过局部敏感哈希,将数据集中的特征哈希量化,以很高的概率将距离较近的数据映射为相同的哈希值,再使用这些哈希值构建动态可搜索加密方案。另一方面,通过将正排索引和倒排索引相结合,构造出一个双字典索引结构,以便在保证高效检索能力的同时,允许明确且实时地删除数据。与之前的工作相比,双字典索引的更新效率和安全性都明显提升。每次查询之后,生成新密钥并重新加密安全索引中的数据,使原先的查询令牌失效,从而实现前向安全的要求。随后,通过限定更新密钥的条件,在保证前向安全的同时减少更新的次数,降低更新对查询操作带来的不良影响,有效提高查询效率。本方案设计的双字典数据结构有效解决了特征查询与数据更新之间的矛盾,同时避免了将密钥直接发送给半可信服务器带来的安全隐患;使用新密钥在适当的时候更新索引从而实现了高效的前向安全;最后将局部敏感哈希应用于动态可搜索加密实现了相似性查询。经过理论分析明确了本方案的复杂性,证明了方案的正确性以及自适应前向安全性。接着,将本方案应用在真实的邮件数据集上并评估了方案的性能。多组实验结果表明本方案在实践中非常有效,适用于真实密文数据场景下的高效相似性查询和数据动态更新。

关键词