Paper 2008/446

Secure Random Key Pre-Distribution Against Semi-Honest Adversaries

Mike Burmester, Reihaneh Safavi-Naini, and Gelareh Taban


Recently, Eschenauer and Gligor [EG02] proposed a model (the EG-model) for random key pre-distribution in distributed sensor networks (DSN) that allows sensors to establish private shared keys. In this model, each sensor is randomly assigned a set of keys, called a key-ring, from a secret key-pool. Two nodes can communicate securely by using a shared key (direct key) or via a chain of shared keys (key-path). The authors show how the key-ring size can be chosen so that nodes are guaranteed to be linked either by direct keys or by key-paths. Security of this system is proven for an eavesdropping (passive) adversary. In this paper we assume the same key pre-distribution set-up but consider a semi-honest adversary. Semi-honest adversaries are privacy adversaries that have access to a fraction of the keys in the key pool, the compromised keys, but are otherwise passive, in the sense that they do not cause nodes to deviate from protocol executions (to remain undetectable). Since they can decrypt messages secured by key-paths with compromised keys, the security guarantees of the EG model break down. We revisit the security of key establishment in the presence of such adversaries and make a number of contributions. First, we show that it is possible to choose the size of the key-rings so that any two nodes can exchange a private key securely in the presence of a semi-honest adversary. Second, we give a protocol that achieves this guarantee and prove its security. Third, we introduce a new efficiency parameter for the EG-model that allows the protocol designer to trade-off the communication required for key establishment with the key-ring size. Finally, we propose a concrete key establishment protocol (based on the DSR protocol) that guarantees security in the presence of a semi-honest adversary.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Under Submission
distributed cryptographykey managementsecret-key cryptography
Contact author(s)
gelareh @ umd edu
2008-10-20: received
Short URL
Creative Commons Attribution


      author = {Mike Burmester and Reihaneh Safavi-Naini and Gelareh Taban},
      title = {Secure Random Key Pre-Distribution Against Semi-Honest Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2008/446},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.