How Far Are You? Finding Path Length Between Two People On a Social Network

Imagine if there is a privacy-preserving mechanism for two mobile devices to determine if their owners have common friends. It can be useful for access control in applications like ride-sharing, sharing Internet access or even just a simple "people radar" app for showing nearby friends and friends-of-friends. Current mechanisms for doing this come at the cost of revealing these interactions and the users' locations to central servers.

In this talk, I will first describe our work, presented at ACSAC 2013, which allows efficient discovery of mutual friends while (a) protecting the privacy of non-mutual friends and (b) guaranteeing authenticity of claimed friendship relations. More importantly, unlike the current mechanisms, our approach does not force users to reveal their interactions or location to any servers. We have implemented "Common Friends" as a software framework that app developers can easily integrate into their applications, e.g., to enforce access control based on users' social proximity in a privacy-preserving manner. As an example, we have prototyped two applications that use the "Common Friends" framework. One, SpotShare is for sharing (tethered) Internet access, where users can choose to share access depending on the existence of common friends. The second, nearbyPeople, is a "people radar" application which shows people nearby and allows users to identify those with whom they share common friends.

I will then describe "Social PaL" which extends "Common Friends" in a number of ways. Social PaL allows two people to exactly determine the path length between them in a social graph. It retains the privacy guarantees of "Common Friends". "Social PaL" currently supports two social networks, Facebook and LinkedIn. For more information about this work, see https://se-sy.org/projects/pet/