A terminology for talking about privacy by data minimization: Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management

Global anonymity is maximized when the anonymity set is large and behavior is uniformly distributed: 'global anonymity is maximal iff all subjects within the anonymity set are equally likely.' Strong global anonymity does not protect individual 'likely suspects' — even in a strong-anonymity system, one user with distinctive behavior may have weak individual anonymity. Strong or even maximal global anonymity does not imply strong anonymity of each particular subject.

§3 defense traffic-shapeml-classifier

Adding dummy traffic to any anonymity mechanism yields the corresponding kind of unobservability: 'A mechanism to achieve some kind of anonymity appropriately combined with dummy traffic yields the corresponding kind of unobservability.' DC-nets achieve sender anonymity and MIX-nets achieve relationship anonymity; with dummy traffic both achieve the corresponding sender and relationship unobservability respectively.

§8 defense traffic-shapeflow-correlation

Pseudonymity uses persistent identifiers other than real names, enabling accountability while providing partial unlinkability; however, use of the same pseudonym across different contexts enables linkability: the attacker can link all data related to a pseudonym. Unlinkability of two messages requires that the attacker cannot sufficiently distinguish whether they share a sender or recipient; for a scenario with n senders, this holds iff the probability of common authorship is sufficiently close to 1/n.

§4, §9, §11 defense dpiflow-correlation

Undetectability of a message requires that it be indistinguishable from 'random noise' — an attacker cannot sufficiently distinguish whether the message exists or not. This is distinct from anonymity, which protects only the relationship between an IOI and a subject, not the IOI's existence itself. Undetectability is possible only for subjects not involved in the IOI; senders and recipients cannot achieve it against each other.

§6 defense random-payload-detectfully-encrypted-detect

The paper establishes a strict property hierarchy: unobservability ⇒ anonymity, and sender/recipient anonymity ⇒ relationship anonymity. Unobservability is strictly stronger than anonymity because it additionally requires undetectability against all uninvolved subjects — the IOI's very existence must be hidden — while anonymity only hides the subject's relationship to the IOI.

§7 defense flow-correlationtraffic-shape