OblivGM: Oblivious Attributed Subgraph Matching as a Cloud Service

Songlei Wang, Yifeng Zheng*, Xiaohua Jia, Hejiao Huang, Cong Wang

*Corresponding author for this work

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

14 Citations (Scopus)

Abstract

In recent years there has been growing popularity of leveraging cloud computing for storing and querying attributed graphs, which have been widely used to model complex structured data in various applications. Such trend of outsourced graph analytics, however, is accompanied with critical privacy concerns regarding the information-rich and proprietary attributed graph data. In light of this, we design, implement, and evaluate OblivGM, a new system aimed at oblivious graph analytics services outsourced to the cloud. OblivGM focuses on the support for attributed subgraph matching, one popular and fundamental graph query functionality aiming to retrieve from a large attributed graph subgraphs isomorphic to a small query graph. Built from a delicate synergy of insights from attributed graph modelling and advanced lightweight cryptography, OblivGM protects the confidentiality of data content associated with attributed graphs and queries, conceals the connections among vertices in attributed graphs, and hides search access patterns. Meanwhile, OblivGM flexibly supports oblivious evaluation of varying subgraph queries, which may contain equality and/or range predicates. Extensive experiments over a real-world attributed graph dataset demonstrate that while providing strong security guarantees, OblivGM achieves practically affordable performance (with query latency on the order of a few seconds).
Original languageEnglish
Pages (from-to)3582-3596
JournalIEEE Transactions on Information Forensics and Security
Volume17
Online published28 Sept 2022
DOIs
Publication statusPublished - 2022

Funding

This work was supported in part by the Guangdong Basic and Applied Basic Research Foundation under Grant 2021A1515110027; in part by the Shenzhen Science and Technology Program under Grant RCBS20210609103056041, Grant JCYJ20210324132406016, and Grant GXWD20220817124827001; in part by the National Natural Science Foundation of China under Grant 61732022; in part by the Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies under Grant 2022B1212010005; in part by the Research Grants Council of Hong Kong under Grant CityU 11217819, Grant 11217620, Grant RFS2122-1S04, Grant N_CityU139/21, Grant C2004-21GF, Grant R1012-21, and Grant R6021-20F; and in part by the Shenzhen Municipality Science and Technology Innovation Commission under Grant SGDX20201103093004019.

Research Keywords

  • attributed subgraph matching
  • Cloud-based graph analytics
  • oblivious services
  • privacy preservation

RGC Funding Information

  • RGC-funded

Fingerprint

Dive into the research topics of 'OblivGM: Oblivious Attributed Subgraph Matching as a Cloud Service'. Together they form a unique fingerprint.

Cite this