Secure Communication Over Radio Channels

We study the problem of secure communication in a multi-channel, single-hop radio network with a malicious adversary that can cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and authenticated manner. It runs in O(|E|t^2 log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t < C the number of channels on which the adversary can participate in each round. We then show how to use f-AME to establish of a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. The resulting service requires O(nt^3 log n) rounds for the setup phase, and O(t log n) rounds for an arbitrary pair to communicate. By contrast, existing solutions in this setting rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious.