ReClaim: a Privacy-Preserving Decentralized Social Network

The privacy concerns associated with the popularity of online social networks have given rise to numerous research papers which focus on either storing the data in encrypted form, or decentralizing the network. However, without the incentive of being able to read private data, a centralized system cannot be sustained. A decentralized network does not rely on such incentives and can continue to operate based solely on user contributed resources. Unfortunately, current proposals either still rely on centralized components, a pre-existing friend-tofriend network, or incur substantial bandwidth overhead. This renders them useless for actual deployment.

ReClaim employs an existing technique to the PSI problem to build a semantic network wherein peers have connections to friends and friends-of-friends. This is achieved by a handshake which uses homomorphic encryption to privately determine which friends are shared amongst two peers. Afterwards, peers synchronize messages destined for friends, providing them with easy access to replicas. Moreover, storing those messages allows ReClaim to handle excessive churn (peers joining and leaving the network at a high rate), overcome NATfirewalls (by allowing for indirect communication), and allow friends to communicate without being online at the same time.

After describing the design of ReClaim, we implement a proof-of-concept application and show during extensive emulation that peers can connect to more than 60% of their friends within 10 minutes in a network consisting of 4000 peers. Moreover, within 10 minutes, peers using ReClaim can establish an indirect connection to 95% of their friends