Observed terminology in anonymity research

This is part of the anonymity terminology project. The project goal is to come up with a proposed consensus about what the terms we use to describe implementations in anonymity networks actually mean.

Quite often in the literature, when a new system is incorporates several new ideas, and later designs resemble the original system only in certain respects, it's not easy to tell whether the term for the original system applies to the later designs.

For example, the original Onion Routing design (Goldschlag, Reed, Syverson, 1996) featured a multiply-layered public-key encrypted structure (an "Onion") that was used to establish long-term "virtual circuits" for data streams; once each circuit was established, data was relayed over the circuit in fixed-sized messages, each of which was decrypted with symmetric key operations at each step in the circuit. Now, how should the term "Onion Routing" be used? Does it apply to anything involving a structure encrypted with multiple public keys? (By this definition, a mixnet does onion routing.) To anything where an "onion" structure is used to establish virtual circuits? (By this definition, the Java Anon Proxy design does onion routing) To anything where some kind of public key operation, not necessarily involving an onion, is used to establish virtual circuits? (Unless the PK-onion requirement is relaxed, Tor isn't onion routing.)

This kind of messiness can make papers in the field hard to read: people hear that "onion routing" is vulnerable to "correlation attacks"; but not every system that folks are calling "onion routing" is actually vulnerable to everything that people are calling "correlation attacks".

Step one of this project is going to be descriptive: let's look through the research literature for statements defining these terms. Let's add more terms as we find them. We should put some effort into finding first uses, but not obsessively: terms can change their meaning over time.

Remember, anonbib is your friend.

Kinds of designs, design techniques

High-latency vs Low-latency

Mix, Mix-net

This term was introduced in Chaum's "Untraceable electronic mail, return addresses, and digital pseudonyms" (1981), where it referred to a computer that detects and removes duplicates from a batch of incoming messages, decrypts each message in the batch with its private key, sorts them into lexicographical order, and delivers them to their recipients.

Cascade

This term was introduced in Chaum's "Untraceable electronic mail, return addresses, and digital pseudonyms" (1981), where it referred to a series of mixes such that each mix would process a batch of messages before sending it to the next. Chaum1981 does not explicitly say that the cascade is assumed to be fixed; however, the message format it gives doesn't work in a non-fixed topology, since an address is only given for the final destination of each message.

Free-route

Onion routing

Onion

Padding

Batching

Pooling, Pool

Kinds of attacks

Predecessor attack

Correlation attack

Intersection attack

Tagging attack

N-1 attack

Related Work

Pfitzmann and Hansen have a must-read terminology proposal, "Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management – A Consolidated Proposal for Terminology," [at version 0.31]. This paper focuses on terminology for properties provided (or not provided) by anonymity, pseudonymity, privacy, and identity systems. This project, instead, aims to provide consistent terminology for techniques used to make these systems (and to attack them).

(In other words, don't go adding terms from the Pfitzmann and Hansen paper.)