Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data

Chang Liu, Liehuang Zhu, Xiangjian He, Jinjun Chen

Research output: Journal PublicationArticlepeer-review

28 Citations (Scopus)


When coming to perform shortest distance queries on encrypted graph data outsourced in external storage infrastructure such as cloud, a significant challenge is how to compute the shortest distance in an accurate, efficient and secure way. This issue is addressed by a recent work, which makes use of somewhat homomorphic encryption (SWHE) to encrypt distance values output by a 2-hop cover labeling (2HCL) scheme. However, it may import large errors and even yield negative results. Besides, SWHE would be too inefficient for normal clients. In this paper, we propose GENOA, a novel Graph ENcryption scheme for shOrtest distAnce queries. GENOA employs only efficient symmetric-key primitives while significantly enhances the accuracy compared to the prior work. As a reasonable trade-off, it additionally reveals the order information among queried distance values in the 2HCL index. We theoretically prove the accuracy and security of GENOA under rigorous cryptographic model. Detailed experiments on eight real-world graphs demonstrate that GENOA is efficient and can produce almost exact results.

Original languageEnglish
Article number8532292
Pages (from-to)192-204
Number of pages13
JournalIEEE Transactions on Dependable and Secure Computing
Issue number1
Publication statusPublished - 1 Jan 2021
Externally publishedYes


  • 2-hop cover labeling
  • Graph encryption
  • secure data outsourcing
  • shortest distance

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data'. Together they form a unique fingerprint.

Cite this