SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates
SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates
复制标题
DOI：
10.1007/978-3-319-70972-7_5
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Qian Wang;K. Ren;Minxin Du;Qi Li;Aziz Mohaisen
中科院分区：
文献类型：
--
作者：
Qian Wang;K. Ren;Minxin Du;Qi Li;Aziz Mohaisen
在大数据时代，图数据库对于NoSQL技术变得越来越重要，许多系统都可以建模为图来进行语义查询。与此同时，随着云计算的出现，数据所有者非常有动力将其大量潜在敏感的图数据以加密的形式外包并存储在远程不可信服务器上，希望保留对加密图进行查询的能力。为了允许对加密数据进行有效和私密的查询，最深入研究的一类结构化加密方案是可搜索对称加密（SSE）设计，它对用于检索数据文件的搜索结构（例如倒排索引）进行加密。在本文中，我们解决了设计安全图数据库加密方案（SecGDB）来加密图结构并在加密图数据库上执行私有图查询的挑战。具体来说，我们的构建战略性地利用高效的加法同态加密和乱码电路来支持具有最佳时间和存储复杂性的最短距离查询。为了在多个查询上实现更好的摊销时间复杂度，我们进一步提出了一种称为查询历史记录的辅助数据结构，并将其存储在远程服务器上作为“缓存”资源。我们证明我们的构造在随机预言模型中是自适应语义安全的，并最终在各种代表性的现实世界数据集上实现和评估它，表明我们的方法在存储和计算方面实际上是有效的。
In the era of big data, graph databases have become increasingly important for NoSQL technologies, and many systems can be modeled as graphs for semantic queries. Meanwhile, with the advent of cloud computing, data owners are highly motivated to outsource and store their massive potentially-sensitive graph data on remote untrusted servers in an encrypted form, expecting to retain the ability to query over the encrypted graphs.To allow effective and private queries over encrypted data, the most well-studied class ofstructured encryptionschemes are searchable symmetric encryption (SSE) designs, which encrypt search structures (e.g., inverted indexes) for retrieving data files. In this paper, we tackle the challenge of designing a Secure Graph DataBase encryption scheme (SecGDB) to encrypt graph structures and enforce private graph queries over the encrypted graph database. Specifically, our construction strategically makes use of efficient additively homomorphic encryption and garbled circuits to support the shortest distance queries with optimal time and storage complexities. To achieve better amortized time complexity over multiple queries, we further propose an auxiliary data structure calledquery historyand store it on the remote server to act as a “caching” resource. We prove that our construction is adaptively semantically-secure in the random oracle model and finally implement and evaluate it on various representative real-world datasets, showing that our approach is practically efficient in terms of both storage and computation.