| 摘要: |
| 随着云计算的快速发展, 数据用户将大量图数据外包给云以节约存储和管理成本。然而, 外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的, 为保护敏感信息的隐私安全, 数据拥有者希望在将图数据外包给云服务器之前对其加密, 同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径, 是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案, 以支持加密图上近似或精确最短距离查询、约束最短距离查询和 top-k 最近关键字查询, 但支持最短路径查询的方案较少, 且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中, 我们基于 2-Hop 标签技术构造支持有向图上最短路径查询的标签索引并加密, 然后将加密的标签外包给云服务器。 利用改进的保序编码算法编码距离值, 实现加法运算和值的比较, 提高最短路径查询的效率。在查询阶段, 通过递归式地计算两节点间最短路径上的第一条边和最后一条边, 最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的, 能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。 |
| 关键词: 云计算 图加密 结构化加密 最短路径查询 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2024.07.05 |
| Received:November 05, 2022Revised:February 13, 2023 |
| 基金项目:本课题得到国家自然科学基金(No. 62072105)和国家自然科学基金海峡联合基金重点项目(No. U1805263)资助。 |
|
| Shortest Path Queries on Structured Encrypted Graph |
| PAN Yingying,CHEN Lanxiang |
| College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350117, China;Fujian Provincial Key Laboratory of Network Security and Cryptology, Fuzhou 350117, China |
| Abstract: |
| With the rapid development of cloud computing, data users outsource large amounts of graph data to the cloud to save the cost of data storage and management. However, the security and privacy of outsourced data is a major challenge for cloud computing. As the cloud is semi-honest, in order to protect the privacy of sensitive information, data owners want to encrypt the graph data before outsourcing it to cloud servers, while retaining the ability to query and process the encrypted graph data. Shortest path query, one of the most fundamental query types in graph application, retrieves the shortest path between two given nodes in the graph. At present, many researchers have proposed a series of efficient schemes supporting approximate or accurate shortest distance query, constrained shortest distance query and top-k nearest keyword query on encrypted graph. However, there are fewer schemes supporting shortest path query, and the storage and time overhead of existing schemes are large. In this paper, a structured encrypted graph scheme is proposed to support shortest path query between two given nodes on the encrypted graph. In this scheme, we generate and encrypt a label index that supports the shortest path query on the directed graph based on 2-Hop labeling, and then outsource the encrypted index to the cloud server. A modified order preserving encoding algorithm is utilized to encode the distance value to achieve the addition operation and comparison of values, improving the efficiency of the shortest path query. The first edge and the last edge on the shortest path between two given nodes are calculated recursively during the query process, and finally the complete shortest path is returned. Security and performance analysis prove that the proposed scheme is secure and efficient to achieve the shortest path query between two nodes with less storage overhead and higher query efficiency, and protect the privacy of graph data. |
| Key words: cloud computing graph encryption structured encryption shortest path query |
