Online micro-blogging services and social networks, as ex- emplified by Twitter and Facebook, have emerged as an im- portant means of disseminating information quickly and at large scale. A standard mechanism in micro-blogging that allows for interesting content to reach a wider audience is that of reposting (i.e., retweeting in Twitter, or sharing in Facebook) of content initially posted by another user. Moti- vated by recent events in which users were prosecuted merely for reposting anti-government information, we present Ri- poste, a randomized reposting scheme that provides pri- vacy guarantees against such charges. The idea is that if the user likes a post, Riposte will re- post it only with some (carefully chosen) probability; and if the user does not like it, Riposte may still repost it with a slightly smaller probability. These probabilities are com- puted for each user as a function of the number of connec- tions of the user in the network, and the extent to which the post has already reached those connections. The choice of these probabilities is based on results for branching pro- cesses, and ensures that interesting posts (liked by a large fraction of users) are likely to disseminate widely, whereas uninteresting posts (or spam) do not spread. Riposte is ex- ecuted locally at the user, thus the user's opinion on the post is not communicated to the micro-blogging server. We quantify Riposte's ability to protect users in terms of differential privacy and provide analytical bounds on the dissemination of posts. We also report on experimental re- sults based on topologies of real networks, including Twitter, Facebook, Renren, Google+ and LiveJournal.
