Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data

Bharath K. Samanthula, Fang Yu Rao, Elisa Bertino, Xun Yi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Outsourcing data and computation to the cloud is increasingly common. However, the data to be outsourced is often privacy-sensitive (e.g., geospatial data, social network data, and Internet network traffic data) and thus it is typically outsourced after being properly encrypted. Graph is one of the most common ways to model and represent the data in many applications, including geospatial data in geographic information systems. In this paper, we consider the following problem: given a graph G, representing for example road or social networks, outsourced to a cloud in encrypted format, the user wants to privately retrieve from G the shortest path from a source s to a destination t. We refer to this problem as Privacy-preserving Shortest Path discovery over Encrypted Graph (PSPEG) data. We propose two novel PSPEG protocols under different security and efficiency guarantees. The first protocol enables one to retrieve the shortest path under a single-cloud setting whereas the second protocol is proposed under a federated cloud environment. Our theoretical and empirical analyses show that the proposed protocols provide a trade-off between efficiency and security.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages427-434
Number of pages8
ISBN (Electronic)9781467366564
DOIs
StatePublished - 19 Oct 2015
Event16th IEEE International Conference on Information Reuse and Integration, IRI 2015 - San Francisco, United States
Duration: 13 Aug 201515 Aug 2015

Publication series

NameProceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015

Other

Other16th IEEE International Conference on Information Reuse and Integration, IRI 2015
CountryUnited States
CitySan Francisco
Period13/08/1515/08/15

Keywords

  • Privacy
  • cloud computing
  • encryption
  • graph data
  • shortest path

Fingerprint Dive into the research topics of 'Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data'. Together they form a unique fingerprint.

Cite this