Related Concepts

Anonymity; Untraceability

Definition

Unlinkability of two events occurring during a process under observation of an attacker is the property that the two events appear to the attacker after the process exactly as much related – or unrelated – as they did before the process started (see [1]).

Theory

In order to apply the notion of unlinkability to a particular cryptographic scheme, the attacker model needs to be specified, for example, whether it is a passive attacker, such as an eavesdropper, or an active attacker (cryptanalysis for this terminology). If passive, which communication lines he can observe and when. If active, how he can interact with the honest system participants (e.g., oracle access) and thereby stimulate certain behavior of the honest participants, or how many honest participants he can control entirely (resilience in threshold signature), and whether the attacker is computationally restricted or computationally unrestricted (computational security). Based on a precise attacker model, certain events occurring in a given cryptographic scheme can then be defined as unconditionally or computationally unlinkable.

Applications

An individual who interacts with other individuals or authorities may keep its interactions unlinkable by using different pseudonyms in different transactions. As Rao and Rohatgi [3] showed, this may not be a sufficient measure to achieve unlinkability, but it is usually a necessary one. Anonymity, untraceability, and privacy are all closely related to the notion of unlinkability. In fact, many privacy-oriented payment schemes, credential schemes, electronic voting schemes, and secure auction schemes are built around the notion of unlinkability and employ transaction pseudonyms (see [ 2]).