Journal
IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING
Volume 18, Issue 1, Pages 192-204Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TDSC.2018.2880981
Keywords
Graph encryption; shortest distance; secure data outsourcing; 2-hop cover labeling
Ask authors/readers for more resources
GENOA is a novel graph encryption scheme for shortest distance queries that significantly enhances accuracy and efficiency compared to prior work. It utilizes efficient symmetric-key primitives and reveals order information among queried distance values in the 2HCL index.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available