% 6.857 project draft
% geofft, ianyh, kyoki, ternus

\documentclass[12pt,letterpaper]{article}
\usepackage{fullpage}
\usepackage{setspace}
\newcommand{\TODO}[1]{\typeout{TODO:#1}{\bf TODO: #1 :TODO}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{2mm}

\begin{document}

\title{6.857 Project Draft}

\author{Jacky Chang \\ Christian Ternus \and Geoffrey Thomas \\ Ian Ynda-Hummel}

\maketitle

\onehalfspacing

%% End goal: design a social network with good privacy guarantees without crippling functionality too much. There is some similarity beween social networks and DHTs, so looking at some results in that area. A scheme for distributed PKI certificates that would allow mutual authentication without leaking user interactions. Understanding what information is leaked accidentally from a social network, like everyone's sexual orientation and people's location from picture (PNG) geolocation information.


\section*{Abstract}

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 \textit{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. 

Another way to better control the flow of information is to allow users to display different sets of information to different people. If users have the option of giving different sets of people access to different sets of information, they can be more confident that details that they may want to share with one group will not be leaked to another. 

The final concern is with creating these friends lists. One of the major sources of data leakage in social networks is 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 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.

We plan to incorporate these ideas into a way of designing a social network that safeguards its users' private information.

%THINGS WE ARE DOING
%- design a decentralized social network that doesn't leak information
%- leaking information:
%    - a malicious user should not be able to masquerade as an honest one, that is there must be an incentive for honesty ("I must give up secret information to cheat")
%    - The "company" running the network should not be able to determine who is who (? -- from our talk that we gave in class)
%    - you should need to control more than some fraction of the nodes to be able to mount a useful side-channel attack against requests of data
%    - I should be able to publish something anonymously on the network (Tor hidden server)
%    - I should be able to request something anonymously on the network (Tor client)
%    - people should not able to mine large amounts of data from a connected network - this is one of the things you lose when you give up centralization (Except for Sybil attacks, but we don't care about those.)
%    - given information about one node, you can't reliably infer relationships to other nodes
%- when I send a friend request to someone on Facebook, they can see more information than they would be able to see otherwise
%- is the friend relationship a trust relationship? (cf. PGP) system that advises you of how much trust / web of trust induced by the social graph
%THINGS WE ARE NOT DOING
%- design a UI such that you don't make wall posts when you intend to send private messages
%- stopping human stupidity


%1. NO ONE CAN DATA MINE
%2. MULTIPLE DISJOINT IDENTITIES
%3. DARK WEB OF TRUST

\section*{Project Plan}

We propose to design a method of operation of a social network that satisfies three goals:

\begin{itemize}
\item Although the system needs to be distributed to avoid a single third party, it should be sufficiently \textbf{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.
\item Users should be able to present \textbf{multiple sub-identities} that cannot be identified as related unless the user specifically authorizes this.
\item Since we lack a single central authority, we need a trust metric like PGP's web of trust, but the entire goal of this network is to avoid publicizing friend relationships at the outset -- we need a \textbf{dark web of trust} that requires revealing as little information about the friend graph as possible.
\end{itemize}

We believe these properties are necessary for creating a social network that is
designed to guard its users' privacy, and we believe they are nearly sufficient
for designing a good system, although we expect part of the main work of this
project to be expanding on and clarifying these constraints.

The first goal, of making data mining hard, is difficult because we would like
to avoid any centralized authorities. Therefore, we cannot rely on a single
source that meters requests made by a user. One idea towards a solution that
our team has discussed involves having the requestee publishing an anonymous
but signed note identifying the requestor; future requestees can notice a high
number of these notes and deny requests for information. To make this idea
workable, we would need to figure out how to publish these notices without too
much performance impact and how to authenticate them: it is possible that the
answers to the second two goals will address authentication. We would also need
to ensure that publication of these notices does not compromise their senders'
privacy.

We plan for our system to let users explicity designate different modes of
identity. For example, a user might have a personal and work profile, both of
which have a distinct set of friends and thus channels of information
dispersion. One possible direction is to consider the possibility of a ``super
user'' which delegates to different profiles. The process by which a user
creates a friend relationship with another user --- discussed below --- is
largely based around the sharing of some piece of information. This information
acts as a gateway to initialize friendship. A user can have multiple such
gateways, and share different gateways to different people. Each gateway, then,
would map to a distinct node in the graph, connected to the ``super user''
node. Furthermore, we must create this network so that any other identities
connected to this ``super user'' node are not leaked through the friend
relationship with one of them. For example, we must take into consideration the
pitfalls of allowing global distribution of information to friends. Consider
the case where a personal friend and a business friend each get the same
provably real message. This message could leak information about the connection
of identities if these friends collude in some way.

We will also need to address the issue of estabilishing a "trust" metric in the
network that is visible to all users, but does not leak information about the
social graph. Since there is no way to authenticate users' claimed names, the
standard technique for checking that a friend requestor is who he says he is is
to check his profile, which includes a list of the people he currently has a
friend relationship with. In fact, Facebook automatically makes more
information about you visible to the recipient after you send a friend request
or a message. Our system will need to let users specify explicitly what
information they want to provide in a friend request and in other actions
requiring authentication.

The most useful such information is in fact the identities of \textit{all} of
your friends --- to be precise, all of your subidentities' friends --- but this
is obviously at odds with the entire premise of the network. Ideally, we would
find or develop some sort of cryptographic signing mechanism that avoids
identifying who did the signing, but only gives hints at who has signed and
vouched for the person doing the signing. This voucher itself would also be
anonymous, with the recursion terminating only at the verifier. As a concrete
example, if Alice and Bob are not friends and wish to verify each other's
identity, and they have five mutual friends whom they trust and who trust them,
Alice should be able to know that she has five trust paths to Bob without
implicitly learning which five friends Bob also knows.

We expect determining whether this is possible (potentially under a restricted
definition) and how best to do so to be a major part of our project. Should
this be doable in the general case, it provides a number of useful specific
cases: for one, it will extend to providing a way to convert trust for a single
subidentity into trust for all subidentities and the super user, because super
user nodes are usually not public or connected. It will also nicely turn into a
mechanism for providing anonymous but publicly-trustworthy notifications for
the data mining protection outlined above. 

Our belief is that a system that provides these three abilities will make a
large number of privacy desiderata possible. Certainly such a system would
satisfy our primary goal of not having a trusted party who has access to all
the data. By providing a trust system, it also prevents attackers without
access to secret resources --- either the user's private key, or the existing
friend relationships of that user --- from impersonating other uses, and the
use of a public key-style infrastructure that does not identify friend
relationships should prevent individual nodes from identifying who is who. By
allowing the creation of nonce subidentities that retain their trust value, it
becomes easy for legitimate users of the network to anonymously publish or
anonymously view information. And by requiring users to explicitly designate
what personal information they want to publish to socially identify themselves
to other users, we address privacy concerns like Facebook's where information
is unknowingly made more public than intended.

\section*{Background Information}

There is a significant problem of identity on existing social networks. In our
daily life, we make the distinction between different modes of interaction. The
fact that someone goes out drinking with friends on the weekend is often
irrelevant with regards to his work life, for example. It is hard, if not
impossible, on the current social network model to distinguish different sets
of access controlled data.

For instance, college students might prefer it if their parents did
not find pictures of last night's party -- or, on a more serious note,
if their information wasn't available to marketing corporations for
use in ads, as Facebook recently discovered might be a
problem.

Furthermore, information may be leaked in a social-networking scenario
which the users never intended to put online.  There was a
particularly notable case a while back where Netflix provided
supposedly-anonymized data about its userbase -- part of a contest to
see if programmers could improve the accuracy of Netflix's
recommendation algorithm.  Soon afterwards, users discovered that they
could be uniquely \emph{reidentified} by their information, and that
this had been used to ``out'' the sexual orientation of several
Netflix members against their will -- simply based on the movies they
had watched.

One way to avoid trusting the third-party network maintainer to keep your data
private is to use the social network only as a network connection, and have
end-to-end encryption of content and information between users. This ensures that protected content
cannot leak because of the general public can never see protected content
because of programming or design flaws. For increased scalability and to defend
against some easy attacks, we can make this a distributed system, e.g., place
each content item in a large distributed hash table (DHT).

There are a couple of issues with such an implementation. First, the system
should be able to pass metadata around, so that a user's client can see a home
screen with all of the information on current social networks. This would
require leaking some information on connections to the network, and we would
want to limit how much information about friend relationships can be recovered
from watching this traffic. The system also needs to have a way to defend
against offline attacks and the ``Sybil attack'', in which an attacker creates
and controls a large number of fake profiles and abusing their aggregate trust.

These thoughts and concerns have motivated our proposed design constraints for
our system. We are looking at a couple of existing work in data privacy for
solutions, for instance, Lysyanskaya et al.'s work on pseudonym systems so that
users can construct ``nyms'', such that two nyms cannot be correlated without
the help of the user ownning the nyms, and Sweeney's ``$k$-anonymity'' model,
which expands on the problem of reidenitification and possible solutions to
appropriately anonymizing data sets such that they cannot be reidentified.

\bibliographystyle{amsalpha}
\bibliography{paper_final}

\end{document}

@Misc{facebookprivacy,
    title = {{Facebook sued for privacy violations}},
    author = {{Legal Blog Watch}},
    howpublished = {\url{http://legalblogwatch.typepad.com/legal\_blog_watch/2009/08/facebook-sued-for-privacy-violation.html}},
    year = 2009,
    month = 08,
}

@Article{lysyanskaya2000pseudonym,
  title={{Pseudonym systems}},
  author={Lysyanskaya, A. and Rivest, R.L. and Sahai, A. and Wolf, S.},
  journal={Lecture notes in computer science},
  pages={184--199},
  year={2000},
  publisher={Springer}
}

@Article{foo,
    author = {Someone},
    title = {Something},
    journal = { },
    year = { },
    month = { },
}

@Misc{foo
    author = {},
    title = {},
    howpublished = {},
    year = {},
    month = {},
    day = {}
}

------
   Zephyr sent to kyoki  20:51  (Geoffrey Thomas)
       http://dspace.mit.edu/bitstream/handle/1721.1/46819/MIT-CSAIL-TR-2009-045.pdf
   Zephyr sent to kyoki  00:54  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       I think these guys are doing (some vague subsets of) what we're doing?

       Frikken et al. "Key allocation schemes for private social networks."
       Proceedings of the 8th ACM Workshop on Privacy in the Electronic
       Society.

       http://portal.acm.org/citation.cfm?id=1655191
-> Zephyr sent to kyoki  01:49  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       That paper cites
       http://portal.acm.org/citation.cfm?id=1456417
       which looks like it answers some of the questions about encryption keys
       and data leakage? Maybe?
   Zephyr sent to tabbott  02:00  (Geoffrey Thomas)
       I feel like I remember seeing some sort of Tor attack where you
       compromise a large fraction of the servers, entry through exit, that
       a particular client is using, and this is easy for some reason...
       remember what it is? I don't _think_ this is cited in your paper
   Zephyr sent to kyoki  02:17  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       It might also be worth skimming Yao's secure multiparty computation paper
       ("Protocols for Secure Computations", 1982) at some point.
   Zephyr sent to kyoki  02:31  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       http://doi.acm.org/10.1145/1102199.1102216
       Di Raimondo et al. "Secure off-the-record-messaging", WPES '05
       is kind of interesting in presenting some attacks against OTR and
       discussing mitigation.

       OTR lets you have an IM conversation and authenticate who you're talking
       to and later repudiate the fact that you had this conversation, so it
       can't be proven that you talked to a certain person or what you said,
       even though it could be verified by each party _during_ the conversation,
       which is possibly a useful primitive to us.
   Zephyr sent to kyoki  02:50  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       Ooh.
       http://epic.org/privacy/reidentification/Sweeney_Article.pdf
       Sweeney, "k-Anonymity: A model for protecting privacy". This starts
       addressing the reidentification problem.
   Zephyr sent to kyoki  03:08  (Geoffrey Thomas)
       CC: kyoki ternus ianyh
       There's of course Chaum's classic on mix networks and such:
       http://portal.acm.org/citation.cfm?id=358563
   Zephyr from tabbott  09:39  (Timothy G Abbott)
       I think basically all the good tor attacks of that form are discussed
       in our paper
   Zephyr sent to tabbott  10:22  (Geoffrey Thomas)
       I'll look harder. "You didn't make a pretty diagram of it!"
