Are You Really My Friend? Efficient and Secure Friend-matching in Mobile Social Networks

Social networks provide users with solutions to manage and acquire social connections in the modern society. Since users of a social network can make a new friendship even when they are not meeting physically, there should be a mechanism enabling them to securely verify identity of each other. One such mechanism is to check if there are enough number of common friends, relying on the friendships established already. Current protocols for mobile social networks require parties to act honestly during the protocol, and are limited to the two-party settings. We propose two solutions for friend matching based on authenticated data structures and polynomial operations that preserve privacy of non-common friends and provide authenticity of the result. Both constructions are efficient and general to be employed in multi-party settings.