Privacy Preserving Grapevines: Capturing Social Network Interactions Using Delegatable Anonymous Credentials

Abstract

A wide variety of services allow users to meet online and communicate with each other, building new social relationships and reinforcing older ones. Unfortunately, malicious entities can exploit such services for fraudulent activities such as spamming. It is critical that these services protect users from unwanted interactions, especially when new relationships are being established - the introduction problem. The problem of assessing that a social network connection is no longer beneficial is also important due to the dynamic nature of such networks. A large number of new connections are established through existing, weak social ties (for example, friend of a friend). On the other hand, the willingness of a user to continue interactions with an existing relationship is an indication of his or her endorsement of that relationship. The interaction history of a user provides valuable information about both new social network connections and the validity of established ones. However, capturing this interaction history is rife with privacy concerns. In this paper, we create a transferable token framework, based on delegatable anonymous credentials (DAC - Crypto 2009), that captures interaction history in a privacy preserving manner. By using the Groth Sahai proof system, we extend DACs to allow for single use tokens with the ability to identify token double spenders. We show that such tokens can, simultaneously, demonstrate the existence of a social network path and capture the continued validity of a social network connection. We present an implementation of this DAC based token framework and utilize it in a Voice over IP (VoIP) setting to enable legitimate user interactions in the presence of a spammer threat model. Our results indicate that we are able to achieve low false positive and false negative rates for realistic threat scenarios without disclosing a user’s social network connections.