PP-OCQ: A distributed privacy-preserving optimal closeness query scheme for social networks

摘要

Optimal closeness query in social networks requires obtaining the social datasets from each user so that he/she finds out a shortest social distance with any target user. For example, we can make friends in terms of the most similar social relationship of family background, education level and hobbies etc. Unfortunately, social data concerning user's attributes might reveal personal sensitive information and be exploited maliciously. Considering the above privacy-revealing issues, this paper proposes a Privacy-Preserving Optimal Closeness Query (PP-OCQ) scheme, which achieves the secure optimal closeness query in a distributed manner without revealing the users' sensitive information. We construct an equivalent cost graph where all users' information are encrypted by his/her public key and the data are authenticated by signature. It employs the ElGamal Cryptosystem to achieve the privacy protection in social networks, and gives an optimal closeness query protocol without leaking the users' sensitive information on homomorphic user ciphertexts. Then it follows the routing protocol, distributed Bellman-Ford shortest-paths protocol, to query the optimal closeness through the users' message propagation in multiple iterations. The direction of propagation is controlled by some indicators so that each user performs corresponding operations based on homomorphism property and fails to obtain other user's information due to the masking of random numbers. Our analysis and simulations show that the proposed scheme is efficient in terms of computation cost and communication overhead.