[freehaven-dev] would you like to play a game?

[dmolnar@belegost.mit.edu]

A definition game, that is. 

Today in the meeting we started thinking about what kinds of anonymity
properties might be useful to have in an ideal anonymous publication
system, and how one might go about defining them in terms of adversary
games. We had a start on two notions, tentatively called "publishing
indistinguishability" and "publisher indistinguishability" (but which need
new names...)

These notions are sort of sub-notions of "publisher anonymity", because we
decided that we could not acheive the strongest intuitive notion of
"publisher anonymity" with Free Haven. We seemed to think we could get
these notions...beyond that, I don't know how "strong" they are or if they
are equivalent. 

That strongest notion would consist of the following : no person (not just
a free haven user) could be shown, ever, to have been any more likely to
have ever been a publisher of any document than any other person. Free
Haven can't meet this requirement because we have a requirement that
publishers send their document into the servnet, and an adversary may see
the sending even if it doesn't know what that sending is.

(note that we'd need to carefully define the adversary here, again)

publishing indistinguishability
-------------------------------

Informally :
		The adversary knows that the Free Haven user P is 
		a potential publisher, because it saw P send something
		to the servnet. We say that Free Haven acheives
		"publishing indistinguishability" if the adversary has
		only negligible advantage over guessing in determining
		*which* file in Free Haven P published. 

Slouching towards formality :

Let $\Phi_0$ and $\Phi_1$ be two documents. 
Then for all adversaries A, and sufficiently large number of 
publishers p > p_0, we have :

 [ b \in_R {0,1} : A(\Phi_b, transcript) = b ] <= 1/2 + neg(p)

where "transcript" is something we need to define based on the adversary's
capabilities and our model of an anonymous publishing system. Note that
here the number of possible publishers p is the security parameter. Is
that right?? and where does it go in the notation above?



publisher indistinguishability
------------------------------

Informally :
		The adversary knows that a document $\Phi$ was published
		by either party $P_0$ or party $P_1$. We say that
		Free Haven provides publisher indistinguishability if
		the adversary has negligible advantage over guessing
		whether $P_0$ or $P_1$ is the real publisher. 

Slouching towards formality :

[b \in_R {0,1} : A("\Phi published by P_b" , transcript) = b ] <= 1/2+neg 

Here I'm not quite sure what the security parameter should be. Is it the
number of publishers, or the number of documents? or something else?


To Do :
	* better, less overlapping names.
	* Define the "transcript" rigorously. Otherwise we are lost. 
	* What is the "right" security parameter for an anon publishing
	service? Is there more than one? 
	* Figuring out other "sub-notions" of publisher anonymity.
	* Are these two notions equivalent? Does one imply the other?
	* what else?
	
Thanks, 
-David