LAUSR

It is increasingly common for enterprises/ organizations to outsource graph analytics services to the cloud. For example, enterprises may leverage the cloud to store and query large attributed graphs. Among others, subgraph matching over a large attributed graph is a common and fundamental query functionality for graph analytics. It aims to retrieve all isomorphic subgraphs for a small query graph and greatly benefits various application domains like cheminformatics, social network analysis, and anti-money laundering. Deploying subgraph matching service in the cloud, however, poses a threat to the privacy of the information-rich graph data as the cloud gains access to the attributed graph, query graph, and query result. Given this, several works have been proposed for supporting privacy-aware subgraph matching. However, prior works only consider a weak semi-honest threat model and cannot provide integrity guarantees for the subgraph matching results in case of malicious adversary. In light of this, we design, implement, and evaluate eGrass, a new system enabling maliciously secure attributed subgraph matching service outsourced to the cloud. In addition to offer protection for graph data confidentiality, eGrass is also designed to hide search access patterns as well as defend against malicious cloud server attempting to compromise the result integrity. We conduct extensive experiments on a real-world dataset. The results demonstrate that compared to the state-of-the-art previous protocol with semi-honest security, eGrass is only $3\times -4.7\times $ slower in query latency, uses $3\times -3.5\times $ more communication, and does not require extra cloud-side storage.