Authenticated flooding in large-scale sensor networks

Two asymmetric mechanisms are often employed in large-scale systems to achieve scalable and efficient authenticated broadcast. However, cryptographic asymmetry based on public-key schemes is computationally expensive, while time asymmetry based on delayed-key release requires time synchronization cross the entire network and temporal buffering of messages at receivers. Neither approach is suitable for large-scale sensor networks composed of computation and storage constrained low-end sensor nodes. In this paper, we propose novel flooding authentication mechanism based on our "information asymmetry" model. Our design is built on top of symmetric cryptography for computation efficiency, and leverages the asymmetric key distribution between the sink and sensor nodes. Through intensive analysis we demonstrate optimized tradeoff between the resilience to compromised sensor nodes and the scalability to system size through space-efficient bloom filters as the authenticator. With a novel "false negative" tuning knob introduced in the construction of bloom filter, we show that the scalability of the authentication primitive can be greatly improved at the cost of small controlled degradation of security, therefore rendering a practical authenticated flooding for large-scale sensor networks