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

Bharath Kumar Samanthula, Fang Yu Rao, Elisa Bertino, Xun Yi

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

6 Citations (Scopus)

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

Fingerprint

Network protocols
Outsourcing
Geographic information systems
Internet
Privacy preserving
Shortest path
Graph
Social networks
Destination
Trade-offs
Road network
Privacy
World Wide Web
Guarantee

Keywords

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

Cite this

Samanthula, B. K., Rao, F. Y., Bertino, E., & Yi, X. (2015). Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. In Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015 (pp. 427-434). [7301008] (Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IRI.2015.72
Samanthula, Bharath Kumar ; Rao, Fang Yu ; Bertino, Elisa ; Yi, Xun. / Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 427-434 (Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015).
@inproceedings{7b6e0b581e444e8c802d3dd0475cd65d,
title = "Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data",
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.",
keywords = "Privacy, cloud computing, encryption, graph data, shortest path",
author = "Samanthula, {Bharath Kumar} and Rao, {Fang Yu} and Elisa Bertino and Xun Yi",
year = "2015",
month = "10",
day = "19",
doi = "10.1109/IRI.2015.72",
language = "English",
series = "Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "427--434",
booktitle = "Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015",

}

Samanthula, BK, Rao, FY, Bertino, E & Yi, X 2015, Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. in Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015., 7301008, Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015, Institute of Electrical and Electronics Engineers Inc., pp. 427-434, 16th IEEE International Conference on Information Reuse and Integration, IRI 2015, San Francisco, United States, 13/08/15. https://doi.org/10.1109/IRI.2015.72

Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. / Samanthula, Bharath Kumar; Rao, Fang Yu; Bertino, Elisa; Yi, Xun.

Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 427-434 7301008 (Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015).

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

TY - GEN

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

AU - Samanthula, Bharath Kumar

AU - Rao, Fang Yu

AU - Bertino, Elisa

AU - Yi, Xun

PY - 2015/10/19

Y1 - 2015/10/19

N2 - 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.

AB - 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.

KW - Privacy

KW - cloud computing

KW - encryption

KW - graph data

KW - shortest path

UR - http://www.scopus.com/inward/record.url?scp=84959163904&partnerID=8YFLogxK

U2 - 10.1109/IRI.2015.72

DO - 10.1109/IRI.2015.72

M3 - Conference contribution

AN - SCOPUS:84959163904

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

SP - 427

EP - 434

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Samanthula BK, Rao FY, Bertino E, Yi X. Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. In Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 427-434. 7301008. (Proceedings - 2015 IEEE 16th International Conference on Information Reuse and Integration, IRI 2015). https://doi.org/10.1109/IRI.2015.72