Paper 2015/1152

Privacy-preserving Friendship-based Recommender Systems

Qiang Tang and Jun Wang


Privacy-preserving recommender systems have been an active research topic for many years. However, until today, it is still a challenge to design an efficient solution without involving a fully trusted third party or multiple semi-trusted third parties. The key obstacle is the large underlying user populations (i.e. huge input size) in the systems. In this paper, we revisit the concept of friendship-based recommender systems, proposed by Jeckmans et al. and Tang and Wang. These solutions are very promising because recommendations are computed based on inputs from a very small subset of the overall user population (precisely, a user's friends and some randomly chosen strangers). We first clarify the single prediction protocol and Top-n protocol by Tang and Wang, by correcting some flaws and improving the efficiency of the single prediction protocol. We then design a decentralized single protocol by getting rid of the semi-honest service provider. In order to validate the designed protocols, we crawl Twitter and construct two datasets (FMT and 10-FMT) which are equipped with auxiliary friendship information. Based on 10-FMT and MovieLens 100k dataset with simulated friendships, we show that even if our protocols use a very small subset of the datasets, their accuracy can still be equal to or better than some baseline algorithm. Based on these datasets, we further demonstrate that the outputs of our protocols leak very small amount of information of the inputs, and the leakage decreases when the input size increases. We finally show that he single prediction protocol is quite efficient but the Top-n is not. However, we observe that the efficiency of the Top-n protocol can be dramatically improved if we slightly relax the desired security guarantee.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IEEE Transactions on Dependable and Secure Computing
recommender systemprivacyhomomorphic encryption
Contact author(s)
tonyrhul @ gmail com
2016-11-18: revised
2015-11-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Qiang Tang and Jun Wang},
      title = {Privacy-preserving Friendship-based Recommender Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1152},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.