Cloud-Based Approximate Constrained Shortest Distance Queries Over Encrypted Graphs With Privacy Protection
Cloud-Based Approximate Constrained Shortest Distance Queries Over Encrypted Graphs With Privacy Protection
复制标题
基于云的隐私保护加密图近似约束最短距离查询
DOI：
10.1109/tifs.2017.2774451
复制
发表时间：
2018-04
影响因子：
6.8
通讯作者：
Jiankun Hu
中科院分区：
文献类型：
--
作者：
Meng Shen;Baoli Ma;Liehuang Zhu;Rashid Mijumbi;Xiaojiang Du;Jiankun Hu
约束最短距离（CSD）查询是基本的图查询原语之一，其在总成本不超过给定阈值的约束下找到图中从原点到目的地的最短距离。CSD查询具有广泛的应用，例如电信和运输中的路由。随着云计算模式的日益普及，图所有者希望将其图外包给云服务器。为了保护敏感信息，这些图表在外包到云端之前通常会进行加密。然而，这对加密图上的CSD查询提出了很大的挑战。由于执行约束过滤是一个棘手的任务，现有的工作主要集中在无约束的最短距离查询。加密图上的CSD查询是一个开放的研究问题。在本文中，我们提出了康纳，一种新的图形加密方案，使近似CSD查询。康纳是建立在一个有效的，基于树的密文比较协议，并利用了原始密钥和有点同态加密，使其计算效率。使用康纳，图所有者可以首先加密隐私敏感图，然后将其外包给云服务器，从而在不失去查询能力的情况下实现必要的隐私。大量的实验与现实世界的数据集证明了所提出的图加密方案的有效性和效率。
Constrained shortest distance (CSD) querying is one of the fundamental graph query primitives, which finds the shortest distance from an origin to a destination in a graph with a constraint that the total cost does not exceed a given threshold. CSD querying has a wide range of applications, such as routing in telecommunications and transportation. With an increasing prevalence of cloud computing paradigm, graph owners desire to outsource their graphs to cloud servers. In order to protect sensitive information, these graphs are usually encrypted before being outsourced to the cloud. This, however, imposes a great challenge to CSD querying over encrypted graphs. Since performing constraint filtering is an intractable task, existing work mainly focuses on unconstrained shortest distance queries. CSD querying over encrypted graphs remains an open research problem. In this paper, we propose Connor, a novel graph encryption scheme that enables approximate CSD querying. Connor is built based on an efficient, tree-based ciphertext comparison protocol, and makes use of symmetric-key primitives and the somewhat homomorphic encryption, making it computationally efficient. Using Connor, a graph owner can first encrypt privacy-sensitive graphs and then outsource them to the cloud server, achieving the necessary privacy without losing the ability of querying. Extensive experiments with real-world data sets demonstrate the effectiveness and efficiency of the proposed graph encryption scheme.
登录
查看更多内容
DOI：
10.1109/iwqos.2014.6914301
发表时间：
2014-05
期刊：
2014 IEEE 22nd International Symposium of Quality of Service (IWQoS)
影响因子：
--
作者：
Meng Shen;Ke Xu;Kun Yang;Hsiao-Hwa Chen
通讯作者：
Meng Shen;Ke Xu;Kun Yang;Hsiao-Hwa Chen
DOI：
10.1145/2810103.2813672
发表时间：
2015-10
期刊：
Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
影响因子：
--
作者：
Xianrui Meng;S. Kamara;Kobbi Nissim;G. Kollios
通讯作者：
Xianrui Meng;S. Kamara;Kobbi Nissim;G. Kollios
影响因子：
1.6
作者：
Cohen, E;Halperin, E;Zwick, U
通讯作者：
Zwick, U
DOI：
10.1145/1455770.1455804
发表时间：
2008-10
期刊：
Proceedings of the 15th ACM conference on Computer and communications security
影响因子：
--
作者：
Assaf Ben-David;N. Nisan;Benny Pinkas
通讯作者：
Assaf Ben-David;N. Nisan;Benny Pinkas
DOI：
10.1007/978-3-662-45608-8_27
发表时间：
2014-12
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Marcel Keller;Peter Scholl
通讯作者：
Marcel Keller;Peter Scholl