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.

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.