Conditional anonymity with non-probabilistic adversary

• We propose a new notion of anonymity, called set-theoretic conditional anonymity.
• We compare the hierarchy of strong anonymity and the hierarchy of conditional anonymity.
• We define a metric for set-theoretic conditional anonymity.
• We improve an existing metric for probabilistic conditional anonymity.
• We study the loss of anonymity of systems with multiple observable outputs.

Conditional anonymity, in comparison to classical strong anonymity, provides a novel perspective on anonymity and has been applied to analyzing anonymizing protocols. While the existing research on conditional anonymity is limited to the probabilistic setting, in this paper we introduce the notion of set-theoretic conditional anonymity by considering the threat from non-probabilistic adversary. Then we refine the understanding of the relationship between strong anonymity and conditional anonymity. Moreover, in order to quantitatively evaluate system’s degree of anonymity, we propose a metric for set-theoretic conditional anonymity and a variant of an existing metric for probabilistic conditional anonymity. We formally show that a system will lose more (at best preserve equal) anonymity when adversary obtains more observable outputs from the system, which confirms the intuition that observations reveal sensitive information.