Abstract: Friend recommendations, whose goal is to expand the connections between users and increase their engagement on the network, is an essential problem for social networks. A particular challenge in friend recommendations is in making recommendations in a cold-start situation. This situation occurs when a new user has just registered and, as result, the model does not yet have sufficient information to directly provide recommendations. Friend recommendations also raise privacy concerns, as they may leak friendship relationships between people on the social network. Knowledge of such relationships may reveal sensitive information about a user, namely their political or sexual preferences [14], medical issues [8], or even de-anonymize their anonymous identities [6, 9]. The easiest and most common way to learn people’s relationships is through a brute-force attack that creates fake identities on the graph, connects them to the target user, and then observes friend recommendations that are based on the target user’s friends, and therefore, leak their social graph [2, 6]. As more users access social networks through their mobile phones, their phone contact books represent a valuable source of information for bootstrapping the recommendations in the coldstart situation. Our main contribution is to propose that the phone contact book can also be used to better protect the privacy of the users’ friend graphs when making friend recommendations, describe a straw-man approach for doing so, and measure its impact on recommendation quality through experiments.