Leakage Resilience of the Blom’s Key Distribution Scheme

We initiate the study of the leakage-resilience of the information-theoretic key distribution schemes. Such schemes, originally proposed in the 1980s, have recently attracted a lot of interest in the systems community. This is because, due to their extreme efficiency, they can be executed on low-cost devices such as sensors, where the use of the public-key cryptography is infeasible. We argue that the study of leakage resilience of such schemes is particularly well-motivated, since, unlike more expensive devices, the sensors (or other similar devices) are unlikely to be physically resilient to leakage. We concentrate on the classical scheme of Blom (CRYPTO 1982), since it is known to be optimal in a large class of such schemes. We model the leakage as an input-shrinking function. In this settings we show that Blom’s scheme is leakage-resilient in a very strong model, where the adversary can (1) compromise completely some nodes in a “standard” way, and (2) leak information jointly from the remaining nodes. The amount leakage that we can tolerate can be up to (0.5−ϵ) of the total amount of information on the leaking nodes. We also show that this bound is optimal, by providing an attack that breaks the scheme if more leakage is available to the adversary. This attack works even in a weaker model, where the nodes leak information independently. In the proof we make use of the theory of the randomness extractors. In particular we use the fact that inner product over a finite field is a good 2-source extractor. This is possible since the Blom’s scheme is based on the matrix multiplication.