# A Privacy-Preserving Routing Protocol Using Mix Networks in Opportunistic Networks
## 3 Anonymous Routing Using a Mix Network
### Opportunistic Mix Network  
We are dealing with networks where nodes can move, appear, and disappear, and all links are opportunistic. Following the notation from [6] we can see an OppNet as an undirected dynamic graph \(G(V,E)\), where \(V\) is the set of nodes and \(E\) the set of edges. Each edge denotes a connection between two nodes that can be used in both directions during a time range. Usually, an edge is denoted as \(e=(u,v,t,\lambda)\), showing that it starts at time \(t\) and has duration \(\lambda\). Nodes can also appear and disappear from the network; without loss of generality, we can assume that the disappearance of a node is captured by the fact that it has no edges (both having a node without connections or the fact that the node disappears is equivalent for our purposes). Graph \(G^{*}(V^{*},E^{*})\) is the static undirected graph obtained from \(G\) by considering all its edges without time constraints (all edges are in the graph independently of time); we have that \(E^{*}=E\). We used \(N^{*}(v)\) to denote all neighbors of node \(v\in V*\) in \(G^{*}\), that is, \(N^{*}(v)=\{u\mid(v,u,t_{i},\lambda_{i})\in E,\forall i\}\).  
In order to implement the mixnet, each network has a set of \(m\) mix nodes \(\mathcal{M}=M_{1},\ldots,\ M_{m}\), such that \(\mathcal{M}\subseteq V\). Our proposal exploits the fact that there could be several mix nodes, and the source node is free to choose which ones it uses to send a message. Moreover, the sender can choose the number of mix nodes to use in a cascade fashion (network) from set \(\mathcal{M}\). In this sense, our approach follows what could be denoted as a restricted free route mix network--it is a free route mixnet [11; 12]--but the selection of nodes is limited to a subset of the nodes of the network. We assumed that there was a key distribution mechanism, so each mix node had an asymmetric key pair, and the public key of each mix node was known to all nodes.  
We considered a typical decryption mixnet. For example, consider sender node \(V_{s}\) that chooses three mix nodes, \(M_{1},M_{2},M_{3}\), to send message \(x\) to destination \(V_{d}\). Each node has a corresponding public key \(PK_{s},PK_{1},PK_{2},PK_{3},PK_{d}\). To that end, \(V_{s}\) builds an onion-based encryption scheme, such as  
\[PK_{1}(r_{1},PK_{2}(r_{2},PK_{3}(r_{3},PK_{D}(r_{d},x))))\]where \(r_{i}\) are random nodes ensuring that messages cannot be correlated to their encrypted versions in any step. The message is received by \(M_{1}\), decrypted, and sent to \(M_{2}\) after performing the mix. Each node does the same until the message arrives at destination \(V_{d}\). Each node \(V_{i}\) waits until it has received \(k_{i}\) messages, and then forwards these \(k_{i}\) messages, making it hard for an attacker to correlate input messages with output messages.  
In the general case, mix nodes are a subset of the whole network nodes, \(\mathcal{M}\subseteq V\). The source node selects a path of mix nodes \(M_{i}\in\mathcal{M}\) of length \(p\), and encrypts message \(x\) as  
\[PK_{1}(r_{1},\ldots PK_{p}(r_{p},PK_{D}(r_{d},x))\ldots)\]  
We assumed that each mix node had enough capacity to perform the cryptographic operations, and memory to store the required \(k_{i}\) messages. Which nodes act as mix nodes depends on the specific scenario and the parameterization of our approach. If we assume that we can choose such nodes, this can have implications in several ways. Having more mix nodes could provide more privacy. The sender can choose randomly from the set of mix nodes, and thus make it harder for an attacker to follow the message through the network. On the other hand, having many mix nodes can enlarge the delay associated with each mix since each node needs to wait for \(k_{i}\) messages. We can also consider other approaches to select potential mix nodes; for instance, it seems reasonable that those nodes with more interactions are obviously more interesting to use. We discuss this in Section 3.3.