kTCQ: Achieving Privacy-Preserving k-Truss Community Queries Over Outsourced Data
Yunguo Guan, Rongxing Lu, Songnian Zhang, Yandong Zheng, Jun Shao, Guiyi Wei · IEEE Transactions on Dependable and Secure Computing · 2023
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.