When discussing privacy properties of a system, people often say their system offers both unlinkability and untraceability. To me that does not make much sense, because they essentially boil down to the same thing.

There is an execellent report (by the late Andreas Pfitzmann and Marit Hansen) discussing a terminology for talking about privacy. It defines unlinkability as the property that an adversary cannot determine whether two events occurring in the system are related or not. Events could be the sending and receiving of a message for instance, or the receipt of two separate messages.

Unfortunately, the report does not discuss the term untraceability. In the context of RFID systems, untraceability expresses the property that given two readings of RFID tags it cannot be determined whether they concern the same tag or not. This exactly corresponds to the definition for unlinkability given above. In the context of exchanging messages, untraceability expresses the property that the adversary cannot determine the sender (or recipient) of a message. However, even this definition is subsumed in the notion of unlinkability if we consider the sending and receipt of a message as two separate events.

In the Pfitzmann report, anonymity is defined as the inability to identify a subject within a set (the so-called anonymity set). Given set of possible senders of a message, the real sender is anonymous within this set if he or she is not identifiable within this set. This definition can be framed in terms of unlinkability by saying that a subject is anonymous (w.r.t. a certain event) if the subject cannot be linked to that event.