Securing Every Bit: Authenticated Broadcast in Radio Networks

This paper studies non-cryptographic authenticated broad- cast in radio networks subject to malicious failures. We in- troduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monitor their neighbors for malicious behav- ior. Second, we present a more robust variant, MultiPathRB, that tolerates the maximum possible density of malicious de- vices per region, using an elaborate voting strategy. We also introduce a new proof technique to show that both protocols ensure asymptotically optimal running time. We demonstrate the fault tolerance of our protocols through extensive simulation. Simulations show the practical supe- riority of the NeighborWatchRB protocol (an advantage hid- den in the constants of the asymptotic complexity). The NeighborWatchRB protocol even performs relatively well when compared to the simple, fast epidemic protocols commonly used in the radio setting, protocols that tolerate no malicious faults. We therefore believe that the overhead for ensuring authenticated broadcast is reasonable, especially in applica- tions that use authenticated broadcast only when necessary, such as distributing an authenticated digest.

Published in:
Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures
Presented at:
22nd ACM Symposium on Parallelism in Algorithms and Architectures, Santorini, Greece, 13-15 June, 2010
Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa

 Record created 2010-05-26, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)