$k$kTCQ: Achieving Privacy-Preserving $k$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 (
$k$
TCQ) by constructing boolean circuits with homomorphic encryption technique and a table-based index. After that, we also design an efficiency-enhanced version (
$k$
TCQ+) based on a stream cipher scheme to reduce the encrypted index's size and improve the query efficiency. Detailed security analysis shows that both
$k$
TCQ and
$k$
TCQ+ can well preserve data privacy and access pattern privacy, and extensive experimental results also demonstrate that
$k$
TCQ+ can observably reduce the size of encrypted index and the query time by
$12\times$
and
$5.9\times$
, respectively.