A segment method of querying shortest distance approximately on encrypted large-scale graph

19 July 2024 A segment method of querying shortest distance approximately on encrypted large-scale graph

Xiaotong Dong, Bo Li, Yong Li, Xiaojie Zhu, Weiping Wang

Author Affiliations +

Proceedings Volume 13181, Third International Conference on Electronic Information Engineering, Big Data, and Computer Technology (EIBDCT 2024); 131811J (2024) https://doi.org/10.1117/12.3031415
Event: Third International Conference on Electronic Information Engineering, Big Data, and Computer Technology (EIBDCT 2024), 2024, Beijing, China

Abstract

As one of the fundamental primitive operations, querying shortest distance between node pairs in a graph has gradually attracted great attention in both academia and industry. In recent years, with the rapid development of cloud computing, it allows clients to outsource their data to cloud servers. In this way, users can outsource large volumes of data which were difficult to store and compute on their own clients. However, it worth noting that for privacy and security reasons, user data needs to be encrypted before being transmission to the server. Meanwhile, it is crucial for the encrypted data transmitted to server to maintain availability in order to enable users' operations searching and querying. To preserve data privacy while enabling querying, clients must construct and transmit a secure index to the server for subsequent querying. When performing shortest distance queries on encrypted graph data outsourced in external storage, a significant challenge is computing the shortest distance in an efficient, accurate and secure manner. Furthermore, the challenge becomes more pronounced as the scale of the graph increases. In this paper, we propose a novel approach to address this issue by splitting the graph data into multiple segments and constructing 2HCL index LID within each subgraphs, as well as establishing an index LBD among these subgraphs. We also provide a comprehensive analysis of complexity and security of SSDAQ and present conclusion at the end of this paper. Compared to 2HCL, which is a classical and widely used algorithm, we reduce the time and space complexity from O(N2) time and O(kn|Lmax(sN)|) space to O(kn2) time and O(kn|Lmax(sn)|) space in setup phase.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Xiaotong Dong, Bo Li, Yong Li, Xiaojie Zhu, and Weiping Wang "A segment method of querying shortest distance approximately on encrypted large-scale graph", Proc. SPIE 13181, Third International Conference on Electronic Information Engineering, Big Data, and Computer Technology (EIBDCT 2024), 131811J (19 July 2024); https://doi.org/10.1117/12.3031415

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

;

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
7 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Computer security

Data privacy

Clouds

Symmetric key encryption

Data transmission

Data communications

Data storage

Show All Keywords

Keywords/Phrases

Search In:

Publication Years