UC Berkeley

Currently, people have a limited range of choices in managing their identity online. They can use their real name or a long-term pseudonym, thereby lending context and credibility to information they publish but retaining no control over their privacy, or they can post anonymously, ensuring strong privacy but lending no additional credibility to their posts. In this work, we aim to develop a new type of online identity that allows users to publish information anonymously and unlinkably while simultaneously backing their posts with the credibility offered by a single, persistent identity. We show how these seemingly contradictory goals can be achieved through a series of new cryptographic techniques.

Our consideration of the utility of persistent identities focuses on their ability to develop reputation. In particular, many online forums include systems for recording feedback from a user's prior behavior and using it to filter spam and predict the quality of new content. However, the dependence of this reputation information on a user's history of activities seems to preclude any possibility of anonymity. We demonstrate that useful reputation can, in fact, coexist with strong privacy guarantees by developing a novel cryptographic primitive we call “signatures of reputation” which supports monotonic measures of reputation in a completely anonymous setting. In our system, users can express trust in others by voting for them, collect votes to build up their own reputation, and attach a proof of their reputation to any data they publish, all while maintaining the unlinkability of their actions.

Effective use of our scheme for signatures of reputation requires a means of selectively retrieving information while hiding one's search criteria. The sensitivity of search criteria is widely recognized and has previously been addressed through a series of cryptographic schemes for private information retrieval (PIR). Among the more recent of these is a scheme proposed by Ostrovsky and Skeith for a variant of PIR termed “private stream searching.” In this setting, a client encrypts a set of search keywords and sends the resulting query to an untrusted server. The server uses the query on a stream of documents and returns those that match to the client while learning nothing about the keywords in the query. To retrieve documents of total length n, the Ostrovsky-Skeith scheme requires the server to return data of length O(n log n). We present a new private stream searching scheme that improves on this result in several ways. First, we reduce the asymptotic communication to O(n + m log m), where m ≤ n is the number of distinct documents returned. More importantly, our scheme improves the multiplicative constants, resulting in an order of magnitude reduction in communication in typical scenarios. We also provide several extensions to our scheme which increase its flexibility and correspondingly broaden its applicability.

With the help of our private stream searching scheme, the proposed signatures of reputation allow users to accumulate positive feedback over time and attach a proof of their current reputation to any information they post online, all while maintaining the unlinkability of their actions. Because of the unlinkability provided, the user is free to use a single identity across all applications, thereby obtaining the most reputation. A detailed analysis of practical performance shows that our proposals, while costly, are within the capabilities of present computing and communications infrastructure.

We conclude our investigation into the potential for new forms of online identity with an evaluation of what might be considered the final frontier in attacks on anonymity: the possibility of linking posted information to its author solely through its content. Even if all explicit forms of identity are stripped from information a user posts online, it must remain intelligible to others to be useful. In the case of textual content, we note that the techniques of stylometry might allow an adversary to determine the likely author of an anonymous post by comparing it to material previously posted elsewhere. Through a series of large-scale experiments we show that, in some cases, this is indeed possible, and that individuals who have authored large amounts of content already online are the most vulnerable.