A Probabilistic Key Agreement Scheme for Sensor Networks without Key Predistribution

Vasiliki Liagkou, Effie Makri, Paul G. Spirakis, Yannis C. Stamatiou

TL;DR

This paper introduces a novel probabilistic key agreement scheme for sensor networks that eliminates the need for pre-distributing keys. The scheme allows two previously unknown entities to establish a shared secret key by iteratively increasing the similarity of their random bit strings, offering a scalable and resilient solution for secure communication in resource-constrained environments.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are characterized by limited resources (battery, processing power, memory) and dynamic topologies. Traditional public-key cryptography is often too resource-intensive for these networks. While symmetric-key cryptosystems are more suitable, distributing secret keys securely is a significant challenge. Existing key pre-distribution schemes often require prior knowledge of network structure or pre-loading keys, which can be impractical for large, dynamic, or ad-hoc networks. This paper addresses the critical need for a key agreement protocol that works between unknown entities without relying on pre-existing shared secrets, enabling secure communication in truly dynamic and self-organizing networks.

Methods

The core of the proposed scheme is a probabilistic protocol that allows two entities, each possessing an N-bit string, to cooperatively increase the number of positions where their strings match. This is achieved through an iterative process:

  1. Random Subset Selection: Both entities randomly select a subset of k positions from their strings.
  2. Secret Computation: They jointly compute, using a secure multi-party computation technique, whether the bits at these k positions disagree in more than half of the locations.
  3. Conditional Flipping: If a significant disagreement is detected, one entity (alternating between parties) randomly flips a subset of l bits within the chosen k positions. This flipping is designed to increase the overall similarity.
  4. Synchronization: The entities synchronize at each step to ensure they are progressing through the protocol together.

The paper then employs Wormald's theorem to analyze the probabilistic evolution of the string similarity. This involves deriving a deterministic differential equation that models the expected change in similarity over time, allowing for theoretical analysis of the protocol's convergence and efficiency.

Datasets

Not discussed in the paper. The paper focuses on a theoretical protocol and its analysis, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Key Agreement Without Predistribution: The most significant insight is the demonstration that a shared secret key can be established between unknown parties without any prior shared information, relying solely on a shared random seed for synchronized random number generation.
  • Probabilistic Similarity Increase: The protocol cleverly uses random bit flipping to probabilistically drive the strings towards higher similarity. The intuition is that if a significant portion of a random subset disagrees, flipping bits in that subset is more likely to increase agreement than decrease it.
  • Secure Multi-Party Computation for Agreement: The use of secure multi-party computation (specifically, the function $f_r$ and $f_x$) is crucial for enabling the entities to determine the number of matching positions without revealing their actual bit strings, thus preserving privacy during the agreement process.
  • Theoretical Framework for Dynamic Networks: Wormald's theorem provides a powerful tool to analyze the convergence of such probabilistic protocols, bridging the gap between discrete random steps and continuous deterministic behavior, which is essential for understanding performance in dynamic environments.
  • Scalability and Resilience: The protocol is designed to be scalable (new nodes can join without re-keying the entire network) and resilient to node captures, as the loss of a few nodes doesn't compromise the entire key agreement process.

Key Results

  • The paper presents a probabilistic protocol that theoretically guarantees an increase in the percentage of similar positions between two N-bit strings over time.
  • Through theoretical analysis using Wormald's theorem, the paper derives a differential equation that models the evolution of string similarity.
  • The analysis shows that the similarity function $x(t)$ is monotone increasing, indicating that the protocol consistently drives towards greater agreement.
  • The paper provides bounds on the time required to reach a certain level of similarity, demonstrating fast convergence, especially when the initial similarity is low.

Limitations and Future Work

  • Communication Overhead: The paper acknowledges that the protocol has "some increased communication overhead" due to the need for synchronization and potentially the secure multi-party computation steps.
  • Randomness Source: The protocol relies on a shared random seed to generate synchronized random numbers. The practical implementation of such a synchronized random number generator across distributed nodes might be a challenge.
  • Practical Implementation: While theoretically sound, the paper doesn't detail the practical implementation challenges or performance on actual sensor network hardware.
  • Future Work: The authors suggest that once a high degree of similarity is achieved, error correction techniques can be used to further enhance similarities and generate a large number of candidate keys for secure communication. Further research could explore optimizing the protocol parameters (k, l) for specific network conditions and evaluating its performance in real-world WSN deployments.

Summary updated

Abstract

The dynamic establishment of shared information (e.g. secret key) between two entities is particularly important in networks with no pre-determined structure such as wireless sensor networks (and in general wireless mobile ad-hoc networks). In such networks, nodes establish and terminate communication sessions dynamically with other nodes which may have never been encountered before, in order to somehow exchange information which will enable them to subsequently communicate in a secure manner. In this paper we give and theoretically analyze a series of protocols that enables two entities that have never encountered each other before to establish a shared piece of information for use as a key in setting up a secure communication session with the aid of a shared key encryption algorithm. These protocols do not require previous pre-distribution of candidate keys or some other piece of information of specialized form except a small seed value, from which the two entities can produce arbitrarily long strings with many similarities.
BibTeX
@inproceedings{liagkou2011probabilistic,
  author = {Vasiliki Liagkou and Effie Makri and Paul G. Spirakis and Yannis C. Stamatiou},
  title = {{A Probabilistic Key Agreement Scheme for Sensor Networks without Key Predistribution}},
  booktitle = {ICGS3/e-Democracy},
  year = {2011},
  doi = {10.1007/978-3-642-33448-1\_11},
}
Figure