Measuring Anonymity with Relative Entropy

                 Yuxin Deng, Jun Pang, and Peng Wu


Anonymity is the property of maintaining secret the identity of users performing 
a certain action. Anonymity protocols often use random mechanisms which can be 
described probabilistically. In this paper, we propose a probabilistic process 
calculus to describe protocols for ensuring anonymity, and we use the notion of
relative entropy from information theory to measure the degree of anonymity 
these protocols can guarantee. Furthermore, we prove that the operators in the
probabilistic process calculus are non-expansive, with respect to this measuring
method. We illustrate our approach by using the example of the Dining 
Cryptographers Problem.