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.