Anonymity for Anonymous Storage

The word ``anonymous'' can mean many different things. Some systems claim ``anonymity'' without specifying a precise definition. While the anonymity requirements of communication channels have been considered previously in depth [5,18], we are not aware of a similar investigation into the requirements for publication and storage systems.

We do not give formal definitions here. Instead, we attempt to lay the groundwork for future definitions by enumerating different aspects of anonymity relevant to anonymous storage. This enumeration will allow us to compare Free Haven with related work.

In all of these notions of anonymity, there are at least three distinct subnotions based on what the adversary is assumed to already know. A document may be picked first, and then the adversary wishes to learn who authored, read, published, and so on. A user may be picked first, and the adversary wishes to know which documents the user authored, read, published, and so on. Finally, an adversary may know a document and a user, and then attempt to confirm its suspicion that the two are linked.

Author-Anonymity:

A system is author-anonymous if an adversary cannot link an author to a document.

Publisher-Anonymity:

A system is publisher-anonymous if it prevents an adversary from linking a publisher to a document.

Reader-Anonymity:

To say that a system has reader-anonymity means that a document cannot be linked with its readers. Reader-anonymity protects the privacy of a system's users.

Server-Anonymity:

Server-anonymity means no server can be linked to a document. Here, the adversary always picks the document first. That is, given a document's name or other identifier, an adversary is no closer to knowing which server or servers on the network currently possess this document.

Document Anonymity:

Document-anonymity means that a server does not know which documents it is storing. Server-anonymity and document-anonymity are crucial if mere possession of some file is cause for action against the server, because they provide protection to a server operator even after his or her machine has been seized by an adversary.

Isolated-server document-anonymity means that if the server is allowed to look only at the data that it is storing, it is unable to figure out the contents of the document. This is achieved via some sort of secret sharing mechanism, either sharing the document or sharing the key for recreating the document (or both) across servers.

Connected-server document-anonymity refers to the situation in which the server is allowed to communicate and compare data with all other servers. Since a connected server may act as a reader and do document requests itself, connected-server document-anonymity seems difficult to achieve without some trusted party which can distinguish server requests from ``ordinary'' reader requests.

Query-Anonymity:

Query-anonymity refers to the notion that over the course of a given document query or request, the ``identity'' of the document itself is not revealed to the server. In short, this means that although a server may have many different documents stored, which document was served for a given request is not knowable by the server. For an overview of private information retrieval (PIR), see [27].

A weaker form of query-anonymity may be realized through server deniability. The server knows the identity of the requested document, but no third party can be convinced of its identity. This concept is related to deniable encryption [13].

It seems that some of these notions of anonymity may imply each other. We leave this investigation as future work.