In wireless sensor networks, the messages between pairs of communicating nodes are open to eavesdropping, tampering, and forgeries. These messages can easily be protected using cryptographic means but the nodes need to share a common secret pairwise key. This thesis proposes a new scheme, the Blom-Yang key agreement (BYka) scheme, that enables pairs of sensor nodes in large networks to compute their pairwise keys quickly and efficiently. Prior to deployment, the Trusted Authority (TA), assigns each node their public IDs, and using its master keys, computes and stores in the nodes their private key-sets. When a pair of nodes need to obtain their pairwise keys, they exchange their public key identifier IDs which are just 16-bit integers. Using the counterpart's ID with its own set of private keys, the nodes are able to compute a large common pairwise key, but only if they have obtained their keying material from the same TA. Hence, the scheme is also mutually authenticating. The computations use simple arithmetic operations which are fast and efficient, easily undertaken by sensor devices which have limited computational, memory, and energy resources. For example, it is able to compute keys of 128 bits in 279 milliseconds in the MICAz mote, requiring 1170 bytes of memory to store the private keying material. Similar key agreement schemes, already widely used in computer networks, use public key cryptographic algorithms which require computationally expensive mathematical operations, taking much longer time, and requiring much more resources.

The security of the BYka scheme is based on the difficulty of obtaining information about the private-public-master-key associations (PPMka). The private keys in each node are computed by the TA using all the permutations of its multiple master keys and the node's public keys operating over a small prime field, and then stored in a random order in the node. If these are captured, the private keys cannot be used directly as the adversary would first have to discover the PPMka. The analysis showed that, with suitable keying parameters, even if sufficient number of private keys are stolen, an adversary with powerful computing resources would need to expend an infeasibly large amount of time and resources to try all the possible PPMka to break the scheme. The adversary may try to discover the PPMka by using pairs of captured nodes to compute their pairwise keys, but this would require the capture of tens of thousands of nodes. Alternatively, even when using the most efficient method, the adversary needs to try a large number of possibilities equivalent to security strengths of 80 to 192 bits. Overall, the adversary has only a small probabilistic chance of breaking the scheme. These analytical results were verified using computer simulated attacks and are used to provide some guidelines and tables for the selection of the keying parameters to meet implementation and performance requirements including computation times, memory availability, network sizes, and pairwise key sizes.

The proposed key agreement scheme is in effect a non-interactive identity-based scheme which uses the node's identity (ID) as its public key. This allows a node to encrypt messages to a target node once its ID is known. It can be used by nodes in dynamic, mobile and ad hoc situations to opportunistically send authenticated messages to each other when they are in range. A single message authenticated protocol (SMAP) using the BYka scheme as the cryptographic primitive is proposed. The speed, efficiency, and resilience of the BYka scheme would make it useful as the cryptographic primitive in other applications such as email and voice communications.