Cryptology ePrint Archive: Report 2009/413

Three Improved Algorithms for Multi-path Key Establishment in Sensor Networks Using Protocols for Secure Message Transmission

Jiang Wu and Douglas R. Stinson

Abstract: In this paper, we propose a security model to capture active attacks against multi-path key establishment (MPKE) in sensor networks. Our model strengthens previous models to capture more attacks and achieve essential security goals for multi-path key establishment. In this model, we can apply protocols for perfectly secure message transmission to solve the multi-path key establishment problem. We propose a simple new protocol for optimal one-round perfectly secure message transmission based on Reed-Solomon codes. Then we use this protocol to obtain two new multi-path key establishment schemes that can be applied provided that fewer than one third of the paths are controlled by the adversary. Finally, we describe another MPKE scheme that tolerates a higher fraction (less than 1/2) of paths controlled by the adversary. This scheme is based on a new protocol for a weakened version of message transmission, which is very simple and efficient.

Our multi-path key establishment schemes achieve improved security and lower communication complexity, as compared to previous schemes.

Category / Keywords: applications / key establishment

Date: received 25 Aug 2009

Contact author: dstinson at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20090901:065410 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]