Privacy-Preserving Approximate Minimum Community Search on Large Networks

The minimum community search is used to identify a minimum dense community that includes a specified vertex in a large network. It has gained significant attention because of its various applications in social-network analysis, e-commerce transactions, biological network modeling, and other areas. Nevertheless, how to realize privacy-preserving minimum community search remains unexplored up to now. In this paper, we initiate the first research on privacy-preserving approximate minimum community search. We propose an effective scheme that allows cloud servers to identify the smallest possible community while safeguarding the private information of the network. To ensure the privacy of sensitive information in the network, we employ obfuscation technology and graph encryption technology to construct two secure indexes instead of the original graph. To strike a balance between safeguarding private information and maintaining search efficiency, our scheme incorporates Bloom filters into the index and implements a two-step strategy on the secure indexes to achieve privacy-preserving approximate minimum community searches. Furthermore, to secure the privacy of the search result, we carefully design an array comparison protocol based on the BGN cryptosystem. This protocol enables cloud servers to perform privacy-preserving heuristic searches from the initial community without exposing any details about the approximate minimum community. The security analysis confirms that our scheme achieves CQA2-security for two non-colluding cloud servers. The experimental results based on real social networks show that the proposed scheme can efficiently handle approximate minimum community searches on large networks.