Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data

Liu, C; Zhu, L; He, X; Chen, J

Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data

Liu, C Zhu, L He, X

Chen, J

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Dependable and Secure Computing, 2018
Issue Date:: 2018-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted ManuscriptAdobe PDF (3.18 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Liu, C	en_US
dc.contributor.author	Zhu, L	en_US
dc.contributor.author	He, X https://orcid.org/0000-0001-8962-540X	en_US
dc.contributor.author	Chen, J	en_US
dc.date.available	2020-05-25T19:08:41Z
dc.date.issued	2018-01-01	en_US
dc.identifier.citation	IEEE Transactions on Dependable and Secure Computing, 2018	en_US
dc.identifier.issn	1545-5971	en_US
dc.identifier.uri	http://hdl.handle.net/10453/129016
dc.description.abstract	IEEE 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 time-consuming 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.	en_US
dc.relation.ispartof	IEEE Transactions on Dependable and Secure Computing	en_US
dc.relation.isbasedon	10.1109/TDSC.2018.2880981	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.subject.classification	Strategic, Defence & Security Studies	en_US
dc.title	Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data	en_US
dc.type	Journal Article
utslib.for	0803 Computer Software	en_US
utslib.for	0804 Data Format	en_US
utslib.for	0805 Distributed Computing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - CRIN - Realtime Information Networks
pubs.organisational-group	/University of Technology Sydney/Strength - GBDTC - Global Big Data Technologies
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US

Abstract:

IEEE 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 time-consuming 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/129016