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