% 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!"