We present a formalisation of a category of schemes that we refer to as broadcast-enhanced key predistribution
schemes (BEKPSs). These schemes are suitable for networks with access to a trusted base station
and an authenticated broadcast channel. We demonstrate that the access to these extra resources allows
for the creation of BEKPSs with advantages over key predistribution schemes such as flexibility and more
efficient revocation. There are many possible ways to implement BEKPSs, and we propose a framework for
describing and analysing them.
In their paper “From Key Predistribution to Key Redistribution,” Cichon et al. [2010] propose a scheme ´
for “redistributing” keys to a wireless sensor network using a broadcast channel after an initial key predistribution.
We classify this as a BEKPS and analyse it in that context. We provide simpler proofs of some
results from their paper, give a precise analysis of the resilience of their scheme, and discuss possible modi-
fications. We then study two scenarios where BEKPSs may be particularly desirable and propose a suitable
family of BEKPSs for each case. We demonstrate that they are practical and efficient to implement, and
our analysis shows their effectiveness in achieving suitable trade-offs between the conflicting priorities in
resource-constrained networks.