Common Friends Discovery with Privacy and Authenticity

In this paper, we propose a common friend discovery algorithm considering the privacy of users and the authenticity of friend relationships. The privacy means userspsila other friendspsila information does not be leaked except their common friends. The authenticity signifies anyone can not successfully claim he is a friend of someone unless he really is. It has many applications such as playing games by friends, finding talking-topics by strangers, finding introducer of job interview, finding matchmaker of someone you desire to know, etc. We consider its security and matching probability. We also implement the algorithm in two mobile phones to prove that it is workable.