A Multivariate Key-Establishment Scheme for Wireless Sensor Networks

In this paper, we propose a novel threshold key pre-distribution scheme for wireless sensor networks using symmetric multivariate polynomials. In the proposed scheme, called multivariate key pre-distribution scheme (MKPS), every node is assigned a unique d-tuple as its ID. The ID assignment mechanism is used to distribute shares of multivariate polynomials among nodes prior to the network deployment. After the deployment, some nodes can establish exactly (d - 1) common keys. The final secret key is a symmetric combination of all these keys. We show that this feature significantly improves the security of MKPS over previous schemes. We also propose a procedure to choose a dimension d that is optimal with respect to network resiliency and network connectivity. We provide complete security and performance evaluations of MKPS. Results reveal that the proposed scheme provides robustness in design and outperforms the previous schemes in term of the network resiliency against the node capture without increasing the memory requirement.