A pruned pendant vertex based index for shortest distance query under structured encrypted graph

Publication Type

Journal Article

Publication Date

11-2024

Abstract

The shortest distance query is used to determine the shortest distance between two vertices. Various graph encryption schemes have been proposed to achieve accurate, efficient and secure shortest distance queries for encrypted graphs. However, the majority of these schemes are inefficient or lack scalability due to the time-consuming index construction and large index storage. Moreover, none of them consider the trade-off between query efficiency and accuracy. To better trade off the query efficiency and accuracy, we propose a Pruned Pendant Vertex based Index for Shortest Distance Query ( PPVI - SDQ ) under structured encryption. The proposed scheme utilizes the structured encryption technique to encrypt a graph and build indexes. The main idea is to use the recursive method to repeatedly prune the pendant vertex, and thereby reducing the index size and construction time by minimizing the redundant data storage and graph traversal. The proposed scheme achieves accurate, efficient and secure shortest distance query with privacy-preserving for encrypted graph. The security analysis demonstrates that the proposed scheme satisfies CQA2-security. Experimental results with real datasets show that the scheme achieves the optimal accuracy and efficiency.

Keywords

Graph encrytion, shortest distance query, structured encryption, pruning pendant vertex

Discipline

Information Security

Research Areas

Cybersecurity

Publication

IEEE Transactions on Information Forensics and Security

Volume

19

First Page

6351

Last Page

6363

ISSN

1556-6013

Identifier

10.1109/TIFS.2024.3414156

Publisher

Institute of Electrical and Electronics Engineers

Additional URL

https://doi.org/10.1109/TIFS.2024.3414156

This document is currently not available here.

Share

COinS