This paper introduces the Common Friends service, a framework for finding common friends which protects privacy of non-mutual friends and guarantees authenticity of friendships. First, we present a generic construction that reduces to secure computation of set intersection, while ensuring authenticity of announced friends via bearer capabilities. Then, we propose an efficient instantiation, based on Bloom filters, that only incurs a constant number of public-key operations and appreciably low communication overhead. Our software is designed so that developers can easily integrate Common Friends 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 access, whereby users decide to share access depending on the existence of common friends. A comprehensive experimental evaluation attests to the practicality of proposed techniques.
Category / Keywords: applications / Privacy enhancing technologies, social networks, access control Original Publication (with minor differences): ACSAC'13 Date: received 26 Sep 2013, last revised 26 Sep 2013 Contact author: me at emilianodc com Available format(s): PDF | BibTeX Citation Note: A preliminary version of this paper appears in ACSAC'13 -- this is the full version Version: 20130927:124640 (All versions of this report) Short URL: ia.cr/2013/620 Discussion forum: Show discussion | Start new discussion