# A Privacy-Preserving Routing Protocol Using Mix Networks in Opportunistic Networks
## 2 Motivation and Related Work  
In OppNets, we can have unstable nodes with unpredictable movements producing a regularly changing network topology. Hence, end-to-end routing paths between source and destination nodes may be difficult to establish. The reliability of data transmission and network-traffic control, which are provided by traditional transport protocols such as TCP, are very inefficient [2] in OppNets. This also means that, in order to provide privacy and anonymous communication services, traditional network mechanisms cannot be directly applied [3]. Several proposals addressed anonymous communications in OppNets, and most of them are based on some application of onion routing. For instance, ARDEN [4] proposes an attribute-based encryption method to provide strong anonymity guarantees. It is based on a traditional onion-routing architecture where nodes can act as onion routers. ARDEN divides nodes into several groups, and each group shares the same key. Thus, nodes from the same group can forward the message, which can improve delivery probability. [PERSON] et al. [5] designed an onion-based routing protocol and extended the existing protocol with group onions into multicopy forwarding. The main contributions of this paper were performance and security analyses of onion-based anonymous routing for DTNs. In [6], [PERSON] et al. proposed an onion-based scheme to ensure anonymous communications in predictable opportunistic networks (POppNets). A POppNet is a network where end-to-end connectivity is not guaranteed, and node communication happens in an opportunistic manner, but the behavior of the network can be predicted in advance. The predictability of such networks can be exploited to simplify some mechanisms of more generic OppNets where there is no prior knowledge on the network behavior. Alternatively, [7] provided a new structure for the history table of nodes in an OppNet in which the personal information of participants in the network is hidden from other nodes. To send a message from a sender node to the final receiver node, the optimized route, composed of different nodes, is identified by inspecting the history table that was created by each node on the basis of previous interactions. In this paper, a new privacy-preserving history-based (PPHB) routing mechanism was proposed on the basis of historical location tracking. [PERSON] et. al used a random walk process and encrypted exchanged message to ensure anonymous communications in OppNets [8]. Their work leveraged the simple opportunistic mechanism to store-carry-forward the message from end to end. In general, and particularly in solutions based on onion routing, some problems might arise if we consider traffic analysis attacks. In an OppNet, the transmission medium is usually the air,making it relatively easy to gather traffic data by anyone with physical proximity to the devices. If we consider an adversarial model where the attacker has access and can monitor all network interactions, traffic analysis techniques can be used to correlate source and destination in common onion routing based approaches. This adversarial model is relatively realistic for some scenarios. Consider, e.g., an OppNet built for a conference where nodes move around a relatively small physical space. OppNet routing protocols usually provide some sort of traffic analysis resistance, in the sense that a packet might be broadcast or sent to nodes which are neither the destination nor an intermediate node in the final delivery path. This does not prevent the identification of the message source, and in most cases does not prevent the attacker from gaining some knowledge about intermediate and destination nodes. In order to provide an anonymous communication method that is robust enough against this adversarial traffic analysis model, we considered the use of mixnets for OppNets. The idea of using mixes providing anonymous communication was first proposed by [PERSON] in 1981 [9].