Description

Advances in lattice-based cryptography are enabling the use of public key algorithms (PKAs) in power-constrained ad hoc and sensor network devices. Unfortunately, while many wire-less networks are dominated by group communications, PKAs are inherently unicast – i.e., public/private key pairs are generated by data destinations. To fully realize public key cryptography in these networks, lightweight PKAs should be augmented with energy-efficient mechanisms for group key agreement. We consider a setting where master keys are loaded on clients according to an arbitrary distribution. We present a protocol that uses session keys derived from those master keys to establish a group key that is information-theoretically secure. When master keys are distributed randomly, our protocol requires O(log bt) multicasts, where1 1=bis the probability that a given client possesses a given master key. The minimum number of public multicast transmissions re-quired to for a set of clients to agree on a secret key in our setting was recently characterized. The proposed protocol achieves the best possible approximation to that optimum that is computable in polynomial time. Moreover, the computational requirements of our protocol compare favorably to multi-party extensions of Diffie-Hellman key exchange.