Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium

We consider authenticating multicast messages in the case of extremely narrow communication channels, such as underwater acoustic communication, with devices such as mobile sensors creating a self-organizing autonomous network. Channel characteristics in this scenario prevent the application of digital signatures (and asymmetric cryptography in general), as it would consume too much of the available bandwidth. As communication is relatively sparse, standard symmetric methods such as TESLA have limited application in this scenario as well. Driven by real-world requirements, we focus on tiny networks of only a few nodes. This paper discusses two issues: (a) strategies of key predistribution enabling flexible creation of multicast groups; (b) authenticating multicast messages in a way that prevents an attacker impersonating the sender by subverting one or more receiver nodes and learning the symmetric keys stored by these nodes. For tiny networks, we show that scalable and asymptotically efficient solutions might be useless, and that specially tailored combinatorial approaches may confer some advantage.