Weak Probabilistic Anonymity

    Yuxin Deng, Catuscia Palamidessi, and Jun Pang  


Anonymity means that the identity of the user performing a certain
action is maintained secret.  The protocols for ensuring anonymity
often use random mechanisms which can be described probabilistically.
In this paper we propose a notion of {\it weak} probabilistic
anonymity, where {\it weak} refers to the fact that some amount of
probabilistic information may be revealed by the protocol. This
information can be used by an observer to infer the likeliness that
the action has been performed by a certain user. The aim of this work
is to study the degree of anonymity that the protocol can still
ensure, despite the leakage of information.

We illustrate our ideas by using the example of the dining
cryptographers with biased coins. We consider
both the cases of nondeterministic and probabilistic users.
Correspondingly, we propose two notions of weak
anonymity and we investigate their respective dependencies on the
biased factor of the coins.