GRECS: Graph Encryption for Approximate Shortest Distance Queries
GRECS: Graph Encryption for Approximate Shortest Distance Queries
复制标题
DOI：
10.1145/2810103.2813672
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
Xianrui Meng;S. Kamara;Kobbi Nissim;G. Kollios
中科院分区：
文献类型：
--
作者：
Xianrui Meng;S. Kamara;Kobbi Nissim;G. Kollios
提出了一种有效支持大规模加密图的近似最短距离查询的图加密方案。最短距离查询是最基本的图操作之一，有着广泛的应用。使用这种图加密方案，客户端可以将大规模隐私敏感图外包给不受信任的服务器，而不会失去查询它的能力。其他应用包括加密图形数据库和受控披露系统。我们提出了GRECS(图加密近似最短距离查询)，它包括三个Oracle加密方案，它们在任何半诚实的服务器上都是可证明安全的。我们的第一个构造只使用对称密钥操作，从而产生了计算效率很高的构造。我们的第二个方案使用了某种同态加密，计算效率较低，但实现了最佳的通信复杂性(即使用最小的带宽)。最后，我们的第三种方案在计算上是有效的，并且以少量的额外泄漏为代价实现了最优的通信复杂度。我们通过实验实现并评估了我们的构建的效率。实验表明，我们的方案是有效的，可以应用于扩展到160万个节点和1100万条边的图。
We propose graph encryption schemes that efficiently support approximate shortest distance queries on large-scale encrypted graphs. Shortest distance queries are one of the most fundamental graph operations and have a wide range of applications. Using such graph encryption schemes, a client can outsource large-scale privacy-sensitive graphs to an untrusted server without losing the ability to query it. Other applications include encrypted graph databases and controlled disclosure systems. We propose GRECS (stands for GRaph EnCryption for approximate Shortest distance queries) which includes three oracle encryption schemes that are provably secure against any semi-honest server. Our first construction makes use of only symmetric-key operations, resulting in a computationally-efficient construction. Our second scheme makes use of somewhat-homomorphic encryption and is less computationally-efficient but achieves optimal communication complexity (i.e. uses a minimal amount of bandwidth). Finally, our third scheme is both computationally-efficient and achieves optimal communication complexity at the cost of a small amount of additional leakage. We implemented and evaluated the efficiency of our constructions experimentally. The experiments demonstrate that our schemes are efficient and can be applied to graphs that scale up to 1.6 million nodes and 11 million edges.