Wireless Sensor Networks (WSNs) is a kind of ubiquitous network. WSNs may consist of a lot of sensor nodes with computational capability and wireless communication capability. The sensors can measure environmental conditions such as temperature, pressure, humidity, and etc. The sensed data is forwarded to a base station through multi-hop paths that are established in collaboration between sensor nodes. As for WSNs, usage by a wide application (military, building maintenance, driving assistance, meteorological data collection, and etc.) is expected.

Many WSNs applications are deployed in unattended and often adversarial environments. Hence, security mechanisms that provide confidentiality and authentication are critical for the operation of many applications. Providing security is particularly challenging in WSNs due to the resource limitations of the sensor. Each sensor node is a small battery-powered device with limited memory and limited computational power.

Thus, most existing pairwise key establishment schemes in WSNs are not based on public key cryptography. One of the most popular schemes, referred to as RKP (Random Key Pre-distribution) in this thesis, was firstly proposed by Eschenauer and Gligor and was extended to many schemes ($q$-composite keys scheme, and so on). These basic probabilistic schemes are pairwise key pre-distribution scheme based on symmetric key cryptography. However, these schemes do not have self-healing feature for a link, and thus the ratio of the compromised links reaches 100\% after some time against the node-capture attacks.

Castelluccia and Spognardi have proposed the RKP scheme with self-healing property, named RoK (Robust Key pre-distribution) scheme, for multiphase WSNs, in which a link self-heals against node-capture attacks by redeploying a sensor node (base station's help) when its battery is depleted. The RoK scheme improves the security of the RKP scheme by limiting the lifetime of the keys and by refreshing the keys. Some recent schemes improve the resiliency of the RoK scheme.

The scheme for storage is proposed besides the link self-heal scheme (RoK scheme). The POSH (Proactive co-Operative Self-Healing) scheme and the DISH (Distributed Self-Healing) scheme have been proposed by Pietro et al. and Ma et al., respectively. These schemes use key evolution and sensor cooperation to self-heal the secret key which encrypts the sensed data on a sensor node for the purpose of data survival. These schemes involves each sensor sharing an initial key with the base station. At any time, sensors are either occupied (red), sick (yellow) or healthy (green). The self-healing of a sensor means that a sick sensor becomes the healthy sensor. The POSH and the DISH schemes update a secret key using the random data transmitted from other sensor nodes. That is, if at least one of the sensor nodes which send the random data is not corrupted, the compromised secret key is updated and then is self-healed.

The WSNs are usually deployed to operate for a long period of time. Availability is important to long-term use of WSNs assuming the presence of the adversary. And also, the three requirements (Forward Secrecy, Backward Secrecy and Self-Healing) are very important to recover from attacks on WSNs. However, It is difficult to satisfy all requirements. Actually, we find the above several schemes, maintain the availability of secure link composed of a pairwise symmetric key in the WSNs. But, many schemes (without RoK scheme) cannot satisfy the three properties. The security of the whole network in such schemes degrades with time in presence of assuming the adversary. An adversary who corrupts several sensors can obtain a set of the pairwise symmetric keys. If the adversary is continuously corrupting sensors, it will eventually learn all the pairwise symmetric keys and all newly deployed sensors will establish links that will immediately be compromised. This is an undesirable property.

The RoK scheme and other multiphase schemes are called resilient multiphase WSNs, in which a link self-heals against node-capture attacks. Also, the multiphase schemes satisfied the three properties above. However, as far as we know, there is no efficient scheme which maintains availability of the secure link between sensor nodes, without the help of a base station. So, the sensor corrupted once cannot recover without being exchanged. It is thus desirable that the link self-heals against node-capture attacks to maintain availability without the help of a base station.

In this thesis, we propose the first proactive co-operative link self-healing scheme, in which the secure link compromised in WSNs automatically self-heals with time, without the help of a server. And, our scheme satisfies the three requirements by regularly updating a key using contributions from the neighbor sensors. Our scheme updates a secure link using the random data transmitted from the neighboring sensor nodes, based on the idea of the POSH scheme. The POSH scheme self-heals the secret key for encrypting the sensed data on a sensor node for the purpose of data survival. In our scheme, a link self-heals in two steps: firstly two neighboring sensors are self-healed and then the link between these sensors is self-healed. Furthermore, our scheme has an advantage that the probability of establishing a secure link is 100\%. In addition, we conduct analytical evaluation and simulation experiment of our scheme, and results obtained from both analysis and simulations indicate that the proposed scheme is very effective in self-healing. Our scheme is both effective and efficient, as supported by analytical and simulation results.