Full Program »
Do I know You? - Efficient and Privacy-Preserving Common Friend-Finder Protocols and Applications
This paper presents the design and the implementation of the Common Friends service, a framework for finding common friends, which protects privacy of non-mutual friends and guarantees authenticity of friendships. We present a generic construction that reduces to secure computation of set intersection, while ensuring authenticity of announced friends via bearer capabilities. We also propose an efficient instantiation, based on Bloom filters, that only incurs a constant number of public-key operations and appreciably low communication overhead.
Our framework is designed so that developers can easily integrate the Common Friends service into their applications, e.g., to enforce access control based on users' social proximity in a privacy-preserving manner. Finally, we showcase our techniques in the context of an existing application for sharing (tethered) Internet connections, whereby users decide to share depending on the existence of common friends. A comprehensive experimental evaluation also attests to the practicality of proposed techniques.
Emiliano De Cristofaro
PARC (a Xerox Company)
University of Helsinki