KMCS: Efficient and privacy-preserving k-core multi-attribute community search

Community search, capable of discovering highly cohesive communities from large-scale graphs, has been widely researched in many fields, e.g., recommender systems and community analysis. In recent years, numerous studies have focused on privacy-preserving community search. However, existing solutions cannot balance well the requirements of structure and multi-attribute cohesiveness effectively. To address this challenge, an efficient and privacy-preserving scheme named K-Core Multi-Attribute Community Search (KMCS) is proposed based on the attribute community graph. Specifically, to improve search efficiency, on the one hand, we utilize an improved core decomposition tree to index the attribute community graph. Furthermore, inspired by the Hamming distance and the K-Core inequality, we design a matrix-operation-based filtering algorithm under plaintext. On the other hand, a unified encoding mechanism is innovatively proposed, which reduces the computational cost by embedding multiple attribute vectors into the attribute matrix. In addition, based on this mechanism, we design an efficient plaintext verification algorithm. To preserve data security, firstly, using symmetric homomorphic encryption (SHE) and lightweight matrix encryption, we design a secure filtering scheme and a secure verification scheme to preserve the privacy of the structure and multi-attribute cohesiveness search. Secondly, the concrete KMCS scheme is presented, which protects outsourced data, query requests, and query results, while additionally ensuring the security of the core decomposition tree's access patterns through obfuscation techniques. The security analysis reveals that KMCS scheme can achieve all our expected security goals. Finally, through performance evaluation, extensive experiments are performed on real community network datasets, demonstrating that KMCS is efficient and practical.