PEAC: A probabilistic, efficient, and resilient authentication protocol for broadcast communications

One of the main challenges of securing broadcast communications is source authentication: to allow each receiver to verify the origin of the data. An ideal broadcast authentication protocol should be efficient for the sender and the receiver, have a small communication overhead, allow the receiver to authenticate each individual packet as soon as it is received (i.e. no buffering on the receivers), provide perfect robustness to packet loss, and scale to a large number of receivers. In this paper we introduce PEAC, a probabilistic, efficient and resilient authentication protocol for broadcast communications. This new construction achieves all the above properties, with the tradeoff that it requires just loose time synchronization between the sender and the receivers. Due to its low communication overhead and minimal synchronization requirements, the scheme is particularly suitable for low-end resource constrained devices as well as applications that require to process the received messages in real time or quasi-real time fashion. For instance, a packet can be authenticated computing 12 hash only on both the sender and the receivers, while the packet forging probability is kept below 2 -80. Finally, note that PEAC is completely customizable, allowing to trade-off security with a (small) overhead increase on the sender only, while not affecting the (small) overhead experienced by receivers. Copyright 2008 ACM.