Online social networks (OSNs), which attract thousands of million people to use everyday, greatly extend OSN users’ social circles by friend recommendations. OSN users’ existing social relationship can be characterized as 1-hop trust relationship, and further establish a multi-hop trust chain during the recommendation process. As the same as what people usually experience in the daily life, the social relationship in cyberspaces are potentially formed by OSN users’ shared attributes, e.g., colleagues, family members, or classmates, which indicates the attribute-based recommendation process would lead to more fine-grained social relationships between strangers.

Unfortunately, privacy concerns raised in the recommendation process impede the expansion of OSN users’ friend circle. Some OSN users refuse to disclose their identities and their friends’ information to the public domain. In this paper, we propose a trust-based privacy-preserving friend recommendation scheme for OSNs, where OSN users apply their attributes to find matched friends, and establish social relationships with strangers via a multi-hop trust chain. Based on trace-driven experimental results and security analysis, we have shown the feasibility and privacy preservation of our proposed scheme.