Privacy preserving strong simulation queries on large graphs

Lyu Xu, Jiaxin Jiang, Byron Choi, Jianliang Xu, Sourav S. Bhowmick

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

6 Citations (Scopus)


This paper studies privacy preserving query services for strong simulation queries in the database outsourcing paradigm. In such a paradigm, clients send their queries to a third-party service provider (SP), who has the outsourced large graph data, and the SP computes the query answers. However, as SP may not always be trusted, the sensitive information of the clients' queries, importantly, the query structures, should be protected. Moreover, graph pattern queries often have high complexities, whereas data graphs can be large. This paper adopts strong simulation as a practical query semantic for this paradigm. Under this semantic, queries are matched with a notion of balls, which are subgraphs related to the query diameter. We transform the core of the existing strong simulation algorithm using data-oblivious operations (ObSSA) and propose its secure version. We show that the algorithm may encounter an overflow problem even partially homomorphic encryption (PHE) has been used. We then propose an efficient inexact algorithm EncSSA, which is secure under chosen plaintext attack (CPA). The results of privacy analysis are presented. We have conducted experiments on Twitter and Citeseer datasets, and the results show that EncSSA is both efficient and effective.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021
Number of pages12
ISBN (Electronic)9781728191843
ISBN (Print)9781728191850
Publication statusPublished - Apr 2021
Event37th IEEE International Conference on Data Engineering, ICDE 2021 - Virtual, Chania, Greece
Duration: 19 Apr 202122 Apr 2021

Publication series

NameProceedings of IEEE International Conference on Data Engineering (ICDE)
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X


Conference37th IEEE International Conference on Data Engineering, ICDE 2021
CityVirtual, Chania
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems

User-Defined Keywords

  • Data outsourcing
  • Graph queries
  • Large graphs
  • Privacy preservation
  • Strong simulation


Dive into the research topics of 'Privacy preserving strong simulation queries on large graphs'. Together they form a unique fingerprint.

Cite this