Efficient Key Exchange for Wireless Multi-hop Networks

We present a protocol that enables to create pairwise keys between nodes in a wireless network, so that the keys are secure from an adversary, Eve, with unbounded computational and memory capabilities, but with limited network presence. Our proposed protocol works over arbitrary multi-hop networks, unlike previously proposed protocols that only work when nodes are restricted to be within the same broadcast domain. Multi-hop networks enable to support a wider range of applications; we are inspired in this paper by a traffic-anonymization application. Multi-hop networks are also more interesting technically, as they offer a much richer palette of opportunities for secrecy, that include the inherently noisy nature of wireless, the existence of multiple paths between the network nodes, and interference from concurrent transmissions. We propose a protocol that leverages these opportunities, and show that it can create keys at a rate of tens of Kbps.