ABSTRACT
Based on the idea of mix-nets, Reed et al. [185] and Syverson et al. [186] introduced the onion routing approach to achieve anonymous communication as follows. An onion routing protocol involves a service provider, a set of users, and a set of nodes (called onion routers). To establish an anonymous channel with the service provider over the public network, the user first selects a random set of nodes (called a circuit), then wraps the message with several layers of encryption, one for each node, and sends it to the service provider through these intermediate nodes. The layered composition where transmitted messages are wrapped is called the onion, and thus the nodes in the circuit are called onion routers. On receiving a message from another node, the onion router decrypts it and immediately sends the resulting value to the next node. This way, anonymity can be achieved since each onion router obtains only the identities of the two nodes adjacent to him/her in the circuit. Neither the first node nor the last node can recognize if the message is receiving from/sending to a user or another onion router. Different from the mix-net in [184], an onion router does not batch and permute a number of received messages before forwarding, but rather immediately forwards what it receives. Since its introduction, onion routing has received a lot of attention and led to several constructions and implementations (e.g., [187-191]). Notably, the famous onion routing project, known as Tor [192], now offers privacy and anonymity service to huge number of users over the Internet.
