Biblio

Tor is a famous routing overlay network based on the Onion multi-layered encryption to support communication anonymity in a threat model in which some network nodes are malicious. However, Tor does not provide any protection against the global passive adversary. In this threat model, an idea to obtain recipient anonymity, which is enough to have relationship anonymity, is to hide the recipient among a sufficiently large anonymity set. However, this would lead to high latency both in the set-up phase (which has a quadratic cost in the number of involved nodes) and in the successive communication. In this paper, we propose a way to arrange a Tor circuit with a tree-like topology, in which the anonymity set consists of all its nodes, whereas set-up and communication latency depends on the number of the sole branch nodes (which is a small fraction of all the nodes). Basically, the cost goes down from quadratic to linear. Anonymity is obtained by applying a broadcast-based technique for the forward message, and cover traffic (generated by the terminal-chain nodes) plus mixing over branch nodes, for the response.

Anonymous Communication Networks (ACNs) are networks in which, beyond data confidentiality, also traffic flow confidentiality is provided. The most popular routing approach for ACNs also used in practice is Onion. Onion is based on multiple encryption wrapping combined with the proxy mechanism (relay nodes). However, it offers neither sender anonymity nor recipient anonymity in a global passive adversary model, simply because the adversary can observe (at the first relay node) the traffic coming from the sender, and (at the last relay node) the traffic delivered to the recipient. This may also cause a loss of relationship anonymity if timing attacks are performed. This paper presents Onion-Ring, a routing protocol that improves anonymity of Onion in the global adversary model, by achieving sender anonymity and recipient anonymity, and thus relationship anonymity.

When location-based services (LBS) are delivered, location data should be protected against honest-but-curious LBS providers, them being quasi-identifiers. One of the existing approaches to achieving this goal is location k-anonymity, which leverages the presence of a trusted party, called location trusted service (LTS), playing the role of anonymizer. A drawback of this approach is that the location trusted service is a single point of failure and traces all the users. Moreover, the protection is completely nullified if a global passive adversary is allowed, able to monitor the flow of messages, as the source of the query can be identified despite location k-anonymity. In this paper, we propose a distributed and hierarchical LTS model, overcoming both the above drawbacks. Moreover, position notification is used as cover traffic to hide queries and multicast is minimally adopted to hide responses, to keep k-anonymity also against the global adversary, thus enabling the possibility that LBS are delivered within social networks.