Quantifying unlinkability in multi-hop wireless networks

Consider a multi-hop wireless network in which devices act as anonymizing routers. Even if devices anonymize their link transmissions, an adversary may still be able to infer key information by observing the traffic patterns in the network. In this work, we quantify how well an adversary can infer unlinkability, that is, the probability that different pairs of devices are communicating, from anonymized link transmissions. We first propose a metric to compute unlinkability using a Kalman-filter based adversary. Using this metric, we then evaluate how different network characteristics impact unlinkability. We assume that devices do not reorder packets to mix traffic and thereby increase unlinkability. Instead, we show that traffic mixing is still possible due to the use of multi-hop routing and broadcast transmissions, with the amount of mixing dependent on the network characteristics. In simulation, we find that (i) for unicast links, as network connectivity increases unlinkability decreases, while for broadcast links, as connectivity increases unlinkability increases, (ii) link dynamics tend to increase unlinkability with unicast links but decrease unlinkability with broadcast links, (iii) well-connected topologies, particularly with broadcast links, achieve the same level of unlinkability with fewer transmissions per packet delivered, (iv) a lattice topology has consistently good unlinkability in different scenarios, and (v) heterogeneous network traffic gives higher unlinkability and better anonymization efficiency than uniform traffic, even when the average rate of traffic is the same.