Measuring unlinkability revisited

Unlinkability describes the inability of an observer to decide whether certain items of interest are related or not. Privacy aware protocol designers need a consistent and meaningful unlinkability measure to asses protocols in face of different attacks. In this paper we show that entropy measures are not sufficient for measuring unlinkability. We propose an alternative measure that estimates the error made by an attacker. We show by example that our expected distance provides a consistent measure that offers a better estimation of message-unlinkability.