<p>Nowadays, more and more people are expanding their network through online social network services, such as friend recommendation. To improve user experience, the social network service provider wishes to outsource its services to a powerful cloud. Since the cloud is always untrusted, uploading query data and users’ information to it may cause serious privacy issues. Although some schemes have been proposed to address these privacy concerns, there are still some problems in privacy and efficiency. To deal with these problems, we propose a privacy-preserving friend recommendation scheme that is more secure and efficient than the state-of-the-art work. Specifically, based on three-party secret sharing (<i>TPSS</i>) scheme, we propose a secure threshold testing (<i>STT</i>) protocol to check whether an encrypted value is greater than the given threshold value. Second, we design a more secure and efficient friend recommendation scheme with the help of our proposed <i>STT</i> and the homomorphic properties of <i>TPSS</i>. Finally, the security of our scheme is proved in the semi-honest model, and the privacy of users is well preserved. Also, we evaluate the performance of the proposed scheme through extensive experiments. The results demonstrate that our proposed scheme outperforms the state-of-the-art.</p>