A Social Network for Clinically Paranoid Lesbians

Jacky Chang kyoki Christian J. Ternus

                       ternus

Geoffrey Thomas

                                         geofft

Ian Ynda-Hummel

                                                            ianyh

Abstract

We present a design for a social network meeting the following three requirements: (1) maliciously mining data from the network is difficult, if not impossible, (2) users delegate independent and indistguinshable sub-identities to compartmentalize different friends or sets of friends, and (3) interactions between friends do not reveal significant portions of the network graph to an untrusted party. We use a distributed system to prevent any central authority from being able to collect all of the data contained in the network, and broadcast all requests for information to a constantly changing “council” of nodes who monitor the traffic for large numbers of requests coming from a small number of clients. To mitigate vulnerability to so-called “Sybil attacks” and to allow for anonymous, unlinkable sub-identities, we propose a dark web of trust using “trust tokens” distributed by users of the system to quantify trustworthiness of other parties during all interactions.

1 Introduction

With the advent of ubiquitous social networking, the problem of controlling one’s personal information has become more important than ever. Many users of social networks would like to be confident of who has access to their personal information and data. The most popular social networks — Facebook, Twitter, MySpace, and so forth — rely on a single company running the network that users may not quite consider a trusted third party. Switching to a distributed model can fix the problem of a central party having access to a large amount of aggregate data, but it does not necessarily limit who can view a user’s data or unintentional information leakage.

Straightforward cryptographic techniques are not quite sufficient. Encrypting data would certainly keep malicious eavesdroppers from accessing information, but would do nothing to address one of the major sources of data leakage in social networks: the shape of the networks themselves. If an attacker knows which nodes are connected to each other, he can infer data about one node from what he knows about the others. In fact, it is possible to, even given a large of amount of anonymized data, reconstruct information about specific people [?].

In order to avoid this, users need to have some way of connecting to other users without revealing their own network connections to each other. This concern must be balanced with the fact that some amount of information needs to be exchanged to prove identity (“I am a friend of a friend”) in order to ensure that a malicious user is not disguising himself as a legitimate one in order to gain access to privileged information.

2 Specification

The essential problem with current, popular social networks is the centralization of authority. A single entity has purview over a user’s private and potentially sensitive information. Security policies can change in ways that leak your information in ways a user may not want and has no control over. To solve this problem we propose a distributed social networking protocol that meets the following three requirements.

• Although the system needs to be distributed to avoid a single third party, it should be sufficiently hard to data mine the social network; for instance, requests for an unusual amount of data should be obvious to the people providing this data.

• Users should be able to present multiple subidentities that cannot be identified as related unless the user specifically authorizes this.

• Since we lack a single central authority, we need a trust metric similar to PGP’s web of trust[?], but the entire goal of this network is to avoid publicizing friend relationships at the outset – we need a dark web of trust that requires revealing as little information about the friend graph as possible.

3 Preventing Data Mining

In order to prevent some central authority from having access to all of the aggregate data in the network, and therefore preventing there from being a single point of corruption or attack, we use a distributed system, with clients keeping track of their own data and the data of friends who are a hop away from them on the network. Without a centralized authority, however, we cannot rely on a single source that meters requests made by a user.

Requests for data are broadcast anonymously to a set of n nodes which we refer to as the “council.” If, for example, Geoff requests data on Ian from Jacky, Jacky would tell the council “I won’t say who I am, but Geoff was requesting data from me,” in order to have the least amount of data leaked in the message as possible. If the council sees a large number of requests from Geoff during a small time period, they would be able to tell all of the other nodes in the network, “Stop accepting and responding to requests from Geoff.”

After some set amount of time, the old council would be discarded and a new council selected using a majority of votes from the nodes in the network. If, during a council’s tenure, one of the nodes drops, the council would select a new member through a majority vote on their own.

When first entering a network, users begin their own councils, of which they are members. When they are told of another council, usually upon joining an active network that already has a council, they drop their own and begin to report to the existing council. If the council does not yet contain n members, likely because the network contains fewer than n members, the user would become a member of the council.

This council method of tracking information requests in a distributed system is very vulnerable to so-called “Sybil” attacks, in which a malicious user creates many anonymous psuedonyms, or nyms, which he then uses to request information from the different nodes. Since the nyms cannot be connected to each other or the attacker’s main identity, the council has no way of knowing that they are all the same person attempting to data mine. This gives rise to the need for a way to validate the trustworthiness of an account while still maintaining its anonymity.

4 Anonymous Sub-Identities

We require that the system allow a user to create multiple, anonymous sub-identities. For example, a user might want separate personal and work profiles, and a particularly cautious user, one who believes in keeping his work and home life separate, may want to ensure that these identities cannot be artbitrarily connected. We note that in the system we propose, this indistinguishability is computational in that it is a quality of proper use of the system. If a user decides to put his or her social security number on both of his sub-identities’ profiles, a human being would likely be able to connect the two.

Our solution to this problem is simple, but both motivates and provides an essential piece of the solution to the dark web of trust. A sub-identity is simply a public/private key-pair. When a user wishes to create a new one, he generates a new key-pair. Assuming that these key-pairs are, in fact, randomly generated, then determining a connection between two sub-identities is impossible without further information.

We must, of course, have a method for associating an identity with a given key-pair, which is complicated by the anonymity of these identities. In terms of a PGP-style web of trust, we need a way to show the existence of a path in the graph without revealing the path itself.

5 Dark Web of Trust

The standard model for calculating trust in a decentralized network is the “web of trust”, whose most well known implementation is for the PGP system. In the PGP web of trust, each user generates a public/private keypair using an encryption algorithm such as RSA or DSA and uploads their public key to a keyserver. Users then meet up in person and verify each others’ credentials (this is colloquially known as a “keysigning party”) and, with their own private keys, sign certifications that the key does in fact belong to the name associated with the key. These signatures are then uploaded to the public keyservers.

Given that the signatures are all on the public servers, and the list of signatures on any given key can be accessed easily, a client can generate the “trust path” between one person’s private key and another’s public: e.g., Alice has verified Bob’s identity, who has verified Celine’s, who has verified Dedric’s, and so forth. Given the existence of enough trust paths, Alice can be reasonably convinced, even in the event of a failure in judgment (or of malice) invalidating one of the trust paths, that the key she has for Dedric belongs to the real Dedric.

The problem with this design is that is inherently not anonymous. Finding a trust path requires being able to search the entire graph to find a specific path that one can be reasonably sure is a trusted one. This would violate our requirement that the shape of the network remain as obfuscated as possible. However, what we really want is