Document Type

Working Paper



Embargo Period



wireless sensor networks, public key, merkle tree, deployment knowledge, algorithms, security




Computer Sciences


With the advance of technology, Public Key Cryptography (PKC) will sooner or later be widely used in wireless sensor networks. Recently, it has been shown that the performance of some public key algorithms, such as Elliptic Curve Cryptography (ECC), is already close to being practical on sensor nodes. However, the energy consumption of PKC is still expensive, especially compared to symmetric-key algorithms. To maximize the lifetime of batteries, we should minimize the use of PKC whenever possible in sensor networks. This paper investigates how to replace one of the important PKC operations–the public key authentication–with symmetric key operations that are much more efficient. Public key authentication is to verify the authenticity of another party’s public key to make sure that the public key is really owned by the person it is claimed to belong to. In PKC, this operation involves expensive signature verification on a certificate. We propose an efficient alternative that uses one-way hash function only. Our scheme uses all sensor’s public keys to construct a forest of Merkle trees of different heights. By optimally selecting the height of each tree, we can minimize the computation and communication costs. The performance of our scheme is evaluated in the paper.