Privacy-preserving reachability query services

Shuxiang Yin, Zhe Fan, Peipei Yi, Koon Kau Choi, Jianliang Xu, Shuigeng Zhou

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

9 Citations (Scopus)

Abstract

Due to the massive volume of graph data from a wide range of recent applications and resources required to process numerous queries at large scale, it is becoming economically appealing to outsource graph data to a third-party service provider (), to provide query services. However, cannot always be trusted. Hence, data owners and query clients may prefer not to expose their data graphs and queries. This paper studies privacy-preserving query services for a fundamental query for graphs namely the reachability query where both clients' queries and the structural information of the owner's data are protected. We propose privacy-preserving 2-hop labeling (pp-2-hop) where the queries are computed in an encrypted domain and the input and output sizes of any queries are indistinguishable. We analyze the security of pp-2-hop with respect to ciphertext only and size based attacks. We verify the performance of pp-2-hop with an experimental study on both synthetic and real-world datasets.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I
EditorsSourav S. Bhowmick, Curtis E. Dyreson, Christian S. Jensen, Mong Li Lee, Agus Muliantara, Bernhard Thalheim
PublisherSpringer Cham
Pages203-219
Number of pages17
Edition1st
ISBN (Electronic)9783319058108
ISBN (Print)9783319058092
DOIs
Publication statusPublished - 1 Apr 2014
Event19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 - Bali, Indonesia
Duration: 21 Apr 201424 Apr 2014

Publication series

NameLecture Notes in Computer Science
Volume8421
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameInformation Systems and Applications, incl. Internet/Web, and HCI (LNISA)
NameDASFAA: International Conference on Database Systems for Advanced Applications

Conference

Conference19th International Conference on Database Systems for Advanced Applications, DASFAA 2014
Country/TerritoryIndonesia
CityBali
Period21/04/1424/04/14

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Privacy-preserving reachability query services'. Together they form a unique fingerprint.

Cite this