Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2020

Abstract

The constrained shortest distance (CSD) query is used to determine the shortest distance between two vertices of a graph while ensuring that the total cost remains lower than a given threshold. The virtually unlimited storage and processing capabilities of cloud computing have enabled the graph owners to outsource their graph data to cloud servers. However, it may introduce privacy challenges that are difficult to address. In recent years, some relevant schemes that support the shortest distance query on the encrypted graph have been proposed. Unfortunately, some of them have unacceptable query accuracy, and some of them leak sensitive information that jeopardizes the graph privacy. In this work, we propose Privacy-preserving Graph encryption for Accurate constrained Shortest distance queries, called PGAS. This solution is capable of providing accurate CSD queries and ensures the privacy of the graph data. Besides, we also propose a secure integer comparison protocol and a secure minimum value protocol that realize two kinds of operations on encrypted integers. We provide theoretical security analysis to prove that PGAS achieves CQA-2 Security with less privacy leakage. In addition, the performance analysis and experimental evaluation based on real-world dataset show that PGAS achieves 100% accuracy with acceptable efficiency.

Keywords

Cloud computing, Constrained shortest distance query, Graph encryption, Outsourced computing

Discipline

Information Security

Research Areas

Cybersecurity

Publication

Information Sciences

Volume

506

First Page

325

Last Page

345

ISSN

0020-0255

Identifier

10.1016/j.ins.2019.07.082

Publisher

Elsevier

Embargo Period

4-30-2021

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.ins.2019.07.082

Download

Share

COinS