TurboBlom: A light and resilient key predistribution scheme with application to Internet of Things

In the Internet of Things (IoT), there are often devices that are computationally too constrained to establish a security key using traditional key distribution mechanisms such as those based on the Diffie-Hellman key exchange. To address this, current solution commonly rely on key predistribution schemes (KPSs). Among KPSs, the Blom scheme provably provides the highest resilience against node capture attacks. This, however, comes at high computational overhead, because the Blom scheme requires many multiplications over a large finite field. To overcome this computational overhead, we present TurboBlom, a novel amendment of the Blom scheme. TurboBlom circumvents the need for field multiplications by utilizing specialized generator matrices, such as random zero-one matrices. We demonstrate that, through this approach, TurboBlom can significantly reduce the computational overhead of the Blom scheme by orders of magnitude. In our next key finding, we demonstrate that TurboBlom offers a level of resilience against node capture that is virtually on par with the Blom scheme. Notably, we prove that the gap between the resilience of the two schemes is exponentially small. These features of TurboBlom (i.e., low computational overhead and high resilience) make it suitable for computationally constrained devices. Such devices exist in abundance in IoT, for example, as part of Low Power and Lossy Networks (LLNs). To demonstrate a sample application of TurboBlom, we show how to use it to enable sender authentication in the Routing Protocol for LLNs (RPL), a standard routing protocol for IoT.