基于图数据库的可搜索加密

可搜索加密技术提供了对加密文件的

近年来，云计算得到了迅猛的发展，提出了“软件即服务”、“平台即服务”、“服务即服务”和“应用即服务”等众多的解决方案[1]。基于云的各种存储产品也走进了大众的生活，例如DropBox、百度云盘等。但是由于黑客入侵等原因，发生了多起云安全事故，例如2011 年黑客入侵Sony 公司造成数亿用户个人信息泄露，同年Google 公司旗下产品Gmail 用户信息也遭到恶意泄露[2]。

常用的隐私保护方案是，在数据文件离开用户控制前将其加密，并将密文存储在云端。这种解决方案可以实现端到端的安全，但是却不实用。因为数据被加密后，云端无法对它进行任何的有效计算，这不适用高吞吐和高容量的云存储场景。

为了同时实现数据加密和关键词搜索，可以采用完全同态加密[3]或者不经意随机存取(ORAM) [4]或者可搜索加密(SE)。前两者理论上拥有更多的优点，如更具有通用性和更强的安全性，但是由于计算复杂度高、系统设计难度大，距离实践尚远。可搜索加密实现了安全性和效率、可用性之间的平衡，更具有实践意义，得到了广泛的研究。

可搜索加密(SE)按加密方式可分为基于对称密钥的可搜索加密(SSE)和非对称密钥的可搜索加密(PSE)。目前主要有两种实现可搜索加密的方式，一种由Goh [5]提出并在文献[6]中使用，为每一个文档构造加密的数据结构，这种结构支持对关键词的检查能力，时间复杂度为O(n)，其中n 为文档的个数；第二种由Curtmola [7]提出，为整个文档集合构建倒排索引，通过搜索关键词找到对应的文档位置，这种方式的时间复杂度是O(k)其中k 为关键词的个数。由于第二种方案是时间复杂度上的最优解，所以有许多构建算法采用[8] [9] [10] [11]。

倒排索引的构建方式存在以下几个问题，索引的构建是静态的，无法应对动态的扩张；索引的搜索过程是串行化的，因为索引结构的唯一性导致无法很好的实现并行搜索；索引主要是构建在内存中，无法应对大量文件的索引同时不具备容灾性。Kemara 在文献[9]中首次提出了动态索引的概念和构造方法， 在文献[12]中通过使用关键词红黑树(KRB)索引的构造方法，较好的实现了索引的动态性和可并发性。

原有的可搜索加密方案无法进行分布式拓展，无法应对高并发等实际生产场景。通过改进基于关键词红黑树的可搜索加密方案，将其应用在图数据库上，获得更好的并发搜索特性和分布式部署能力。最后通过微基准测试，比较原方案和图数据库方案的各项性能，证明图数据库方案的可行性。

2. 相关工作 2.1. 动态可搜索加密模型 在构建可搜索加密模型中，使用了一些基础的密码学原语。其中私钥加密模型是一个多项式时间算法的三元组，SKE = (Gen, Enc, Dec)，Gen 是一个概率算法，输入安全参数k，输出密钥K；Enc 是一个概率算法，输入密钥K 和消息m，输出密文c；Dec 是一个确定性算法，输入密钥K 和密文c，输出m，