kTCQ: Achieving Privacy-Preserving k-Truss Community Queries Over Outsourced Data

Community search over graphs, which is believed as a powerful tool for locating subgraphs of closely related vertices, has received considerable attention in recent years, and k-truss is such a popular community search metric to obtain subgraphs in which every edge forms (k-2) triangles. In this paper, we particularly consider k-truss community query services, which will return all k-truss communities containing a given query vertex. As is known, when the size of graph grows, for achieving better performance, it is natural for a service provider to outsource the services to a powerful cloud. However, this stresses the need for privacy-preserving k-truss community query services, as the cloud server is not fully trustable. Over the past years, many schemes focusing on privacy-preserving graph computation have been put forth, but none of them can well support privacy-preserving k-truss community queries. Aiming at this challenge, we first propose a privacy-preserving k-truss community query scheme (kTCQ) by constructing boolean circuits with homomorphic encryption technique and a table-based index. After that, we also design an efficiency-enhanced version (kTCQ+) based on a stream cipher scheme to reduce the encrypted index's size and improve the query efficiency. Detailed security analysis shows that both kTCQ and kTCQ+ can well preserve data privacy and access pattern privacy, and extensive experimental results also demonstrate that kTCQ+ can observably reduce the size of encrypted index and the query time by 12x and 5.9x , respectively.