Fingerprinting wireless devices using physical properties has been recently suggested as an alternative for device identification and authentication. It has been found that the clock skew caused by the frequency discrepancy of the quartz crystals in different devices can be used as a reliable source for fingerprinting. Researchers have studied the application of the clock skew-based fingerprinting in sensor networks and claimed that it can detect fake identities, wormholes, and node replicas. However, the study in this paper draws a completely opposite conclusion, i.e., the clock skew of sensor nodes can be easily forged by adversaries to evade the detection. This paper then studies the feasibility of using the distribution of signal power in space to fingerprint sensor nodes. The result shows that a sensor node's signal power distribution in space is not only reliable for being used as a source for fingerprinting but also very hard to forge. Finally, the paper discusses the application of using signal power distribution for detecting various attacks as well as the limitations and open problems.

Recent studies have demonstrated that it is feasible to perform public key cryptographic operations on resource-constrained sensor platforms. However, the significant energy consumption introduced by public key operations makes any public key-based protocol an easy target of Denial-of-Service (DoS) attacks. For example, if digital signature schemes such as ECDSA are used directly for broadcast authentication without further protection, an attacker can simply broadcast fake messages and force the receiving nodes to perform a huge number of unnecessary signature verifications, eventually exhausting their battery power. This paper shows how to mitigate such DoS attacks when digital signatures are used for broadcast authentication in sensor networks. Specifically, this paper first presents two filtering techniques, the group-based filter and the key chain-based filter , to handle the DoS attacks against signature verification. Both methods can significantly reduce the number of unnecessary signature verifications when a sensor node is under DoS attacks. This paper then combines these two filters and proposes a hybrid solution to further improve the performance.

Wireless Sensor Networks (WSN) are vulnerable to jamming attacks where an adversary injects strong noises to interfere with the normal transmission. It is crucial to detect such jamming attacks as fast as possible. Existing studies have shown that an effective indicator of jamming is the packet delivery ratio (PDR). However, current PDR-based schemes use the end-to-end packet delivery ratio, which requires one to observe communication for a long time before a good decision is made. In this paper, we propose collaborative detection, which evaluates the packet delivery ratio in an given area instead of a pair of nodes. The intuition is that the attacker often jams an area of his interest, not just two specific nodes. The benefit is that we can detect jamming attacks in a much faster way. We have evaluated the performance of our idea on TelosB motes. The results show that we can effectively and quickly detect jamming attacks.

Wireless communication is vulnerable to jamming attacks, where an adversary injects strong noise to interfere with the legitimate transmissions. Jamming can easily disrupt a sensor application such as border monitoring. Since the area being jammed often tells the location of adversarial activities, e.g., illegal border crossing, it is critical to detect jamming efficiently and timely. It has been shown that the packet delivery ratio (PDR) is an effective indicator of jamming attacks. However, energy efficiency and detection timeliness are two conflicting requirements in existing PDR-based schemes. This paper proposes a novel jamming detection approach that is both efficient in terms of the additional overhead and timely in terms of the detection latency. The idea is to conduct two-phase detection. The first phase identifies the sign of jamming quickly and efficiently without adding any extra communication or requiring any special hardware or infrastructure. Any sign of jamming will trigger the second phase detection, which performs a short burst of channel probing to make an accurate decision. The benefits of the two-phase approach are analyzed in the paper. In addition, this paper also presents the detailed evaluation via experiments on a network of TelosB motes.

Many techniques have been developed recently for establishing pairwise keys in sensor networks. However, some of them are vulnerable to a few compromised sensor nodes, while others could involve expensive protocols for establishing keys. This article introduces a much better alternative that can achieve both high resilience to node compromises and high efficiency in key establishment. The main idea is to deploy a small number of additional sensor nodes, called assisting nodes , to help key establishment between sensor nodes. The proposed approach has many advantages over existing approaches. In particular, a sensor node only needs to make a few local communications and perform a few efficient hash operations to setup a key with any other sensor node in the network at a very high probability. The majority of sensor nodes only need to store a single key. Besides, it also provides high resilience to node compromises. The theoretical analysis, simulation studies, and experiments on TelosB sensor motes also demonstrate the advantages of this key establishment protocol in sensor networks.

While many protocols for sensor network security provide confidentiality for the content of messages, contextual information usually remains exposed. Such contextual information can be exploited by an adversary to derive sensitive information such as the locations of monitored objects and data sinks in the field. Attacks on these components can significantly undermine any network application. Existing techniques defend the leakage of location information from a limited adversary who can only observe network traffic in a small region. However, a stronger adversary, the global eavesdropper, is realistic and can defeat these existing techniques. This paper first formalizes the location privacy issues in sensor networks under this strong adversary model and computes a lower bound on the communication overhead needed for achieving a given level of location privacy. The paper then proposes two techniques to provide location privacy to monitored objects (source-location privacy)-periodic collection and source simulation-and two techniques to provide location privacy to data sinks (sink-location privacy)-sink simulation and backbone flooding. These techniques provide trade-offs between privacy, communication cost, and latency. Through analysis and simulation, we demonstrate that the proposed techniques are efficient and effective for source and sink-location privacy in sensor networks.

Buffer overflow vulnerabilities are program defects that can cause a buffer to overflow at runtime. Many security attacks exploit buffer overflow vulnerabilities to compromise critical data structures. In this paper, we present a black-box testing approach to detecting buffer overflow vulnerabilities. Our approach is motivated by a reflection on how buffer overflow vulnerabilities are exploited in practice. In most cases the attacker can influence the behavior of a target system only by controlling its external parameters. Therefore, launching a successful attack often amounts to a clever way of tweaking the values of external parameters. We simulate the process performed by the attacker, but in a more systematic manner. A novel aspect of our approach is that it adapts a general software testing technique called combinatorial testing to the domain of security testing. In particular, our approach exploits the fact that combinatorial testing often achieves a high level of code coverage. We have implemented our approach in a prototype tool called Tance. The results of applying Tance to five open-source programs show that our approach can be very effective in detecting buffer overflow vulnerabilities.

Attestation has become a promising approach for ensuring software integrity in wireless sensor networks. However, current attestation either focuses on static system properties, e.g., code integrity, or requires hardware support such as Trusted Platform Module (TPM). However, there are attacks exploiting vulnerabilities that do not violate static system properties, and sensor platforms may not have hardware-based security support. This paper presents a software attestation scheme for dynamic data integrity based on data boundary integrity. It automatically transforms the source code and inserts data guards to track run-time program data. A data guard is unrecoverable once it is corrupted by an attacker, even if the attacker fully controls the system later. The corruption of any data guard at runtime can be remotely detected. A corruption either indicates a software attack or a bug in the software that needs immediate attention. The benefits of the proposed attestation scheme are as follows. First, it does not rely on any additional hardware support, making it suitable for low-cost sensor nodes. Second, it introduces minimal communication cost and has adjustable runtime memory overhead. Third, it works even if sensor nodes use different hardware platforms, as long as they run the same software. The prototype implementation and the experiments on TelosB motes show that the proposed technique is both effective and efficient for sensor networks.

Security testing has gained significant attention recently due to frequent attacks against software systems. This paper presents a trace-based security testing approach. It reuses test cases generated from previous testing methods to produce execution traces. An execution trace is a sequence of program statements exercised by a test case. Each trace is symbolically executed to produce program constraints and security constraints. A program constraint is a constraint imposed by program logic on program variables. A security constraint is a condition on program variables that must be satisfied to ensure system security. A security flaw exists if there is an assignment of values to program variables that satisfies the program constraint but violates the security constraint. This approach detects security flaws even if existing test cases do not trigger them. The novelty of this method is a test model that unifies program constraints and security constraints such that formal reasoning can be applied to detect vulnerabilities. A tool named SecTAC is implemented and applied to 14 benchmark programs and 3 open-source programs. The experiment shows that SecTAC quickly detects all reported vulnerabilities and 13 new ones that have not been detected before.

Wireless communication is particularly vulnerable to signal jamming attacks. Spread spectrum mitigates such problem by spreading normal narrowband signals over a much wider band of frequencies and forcing jammers who do not know such spread pattern to invest much more effort to launch attacks. However, in broadcast systems, jammers can easily find out the spread pattern by compromising some receivers. Several group-based approaches have been proposed to deal with insider jammers who can compromise receivers in broadcast systems; they can tolerate t malicious receivers as long as the system can afford 2t additional copies for each broadcast message. This paper introduces a novel jamming-resistant broadcast system that organizes receivers into multiple channel-sharing broadcast groups and isolates malicious receivers using adaptive re-grouping. By letting receivers in different groups partially share their channels, this scheme reduces the extra communication cost from 2t to (2 - ρ)t copies, where ρ is the channel sharing factor (0<;ρ<;1); this is much closer to optimal given the previously proven lower bound of t additional copies. In addition, a sequential test based scheme is also proposed to further improve the performance so that p can be set larger to save more communication cost without reducing security. The analytic and simulation results show that the proposed approaches greatly push limit of jamming-resistant broadcast towards optimal.

The neighborhood information has been frequently used by protocols such as routing in sensor networks. Many methods have been proposed to protect such information in hostile environments. However, these methods can only protect neighbor relations between benign nodes. A compromised node can easily circumvent them and setup false neighbor relations with sensor nodes in many places, impacting the network at a large scale. This paper presents a theoretic model for neighbor discovery in sensor networks and describes a fundamental security limitation and a generic attack against this model. The paper then proposes an efficient and localized solution based on a security property achievable during sensor deployment. This technique provides a threshold security guarantee in dealing with compromised sensor nodes. The analytical and simulation studies show that the technique is practical and effective for sensor networks.

Embedded devices are widely used in military and civilian operations. They are often unattended, publicly accessible, and thus vulnerable to physical capture. Tamper-resistant modules are popular for protecting sensitive data such as cryptographic keys in these devices. However, recent studies have shown that adversaries can effectively extract the sensitive data from tamper-resistant modules by launching semi-invasive side-channel attacks such as power analysis and laser scanning. This paper proposes an effective key management scheme to harden embedded devices against side-channel attacks. This technique leverages the bandwidth limitation of side channels and employs an effective updating mechanism to prevent the keying materials from being exposed. This technique forces attackers to launch much more expensive and invasive attacks to tamper embedded devices and also has the potential of defeating unknown semi-invasive side-channel attacks.

Sensor nodes are often organized into clusters for efficiency and scalability purposes. Every sensor cluster is managed by a cluster leader during the network operation such as routing and data aggregation. Since managing a cluster consumes substantial energy, the cluster leader needs to be re-elected from time to time for load balancing. In hostile environments, it is critical to ensure the security of such leader election. This paper proposes an efficient, resilient, and fully distributed leader election protocol for sensor networks. It only uses efficient symmetric key operations and guarantees that (i) benign cluster members will elect the same leader as long as they are well- connected, and (ii) attackers cannot impact the leader election process to increase or decrease the chance of a benign member being elected as a cluster leader. In addition, the proposed method can quickly recover from message loss or malicious attacks. The evaluation results also demonstrate the efficiency and effectiveness of this approach.

Traditional test case generation methods usually consider coverage criteria like statement or path coverage and ignore security characteristics. The result is that a test case may fail to find vulnerabilities even if it covers the vulnerable statements. However, we argue that existing test cases are still of great value because significant human effort and time have been invested to achieve high coverage criteria. A high coverage indicates a high possibility that vulnerable statements occur in the execution traces of these test cases. Thus existing test cases could guide us to those vulnerable statements. Under this intuition, we present a method of security testing by re-examining existing test cases. The basic idea is to discover two types of constraints in a program: program constraints (PC) and security constraints (SC). The former are the constraints imposed by program statements. For example, an assignment statement i=0 constrains the value of i to be 0. The later are the constraints derived from security concerns. For example, a buffer should never be overflowed. Intuitively, a statement is vulnerable if it can make PCrarrSC be false, which means the program constraints are not strict enough to ensure the security constraints. We design and develop a tool named RETAST to demonstrate our idea and the initial result is promising.

Sensor networks may be used in many monitoring applications where the locations of the monitored objects are quite sensitive and need to be protected. Previous research mainly focuses on protecting source location against mote-class attackers who only have a local view of the network traffic. In this paper, we focus on how to protect the source location against laptop-class attackers who have a global view of the network traffic. This paper proposes four schemes---naive, global, greedy, and probabilistic---to deal with laptop-class attacks. The naive solution uses maintenance messages sent periodically to hide real event reports. The global and greedy solutions improve the naive solution by reducing the latency of event delivery without increasing communication overhead. The probabilistic solution further improves the performance by reducing communication overhead without sacrificing location privacy. Experiments show that the probabilistic solution is practical for providing source location privacy against a laptop-class attacker.

Recent studies have demonstrated that it is possible to perform public key cryptographic operations on the resource-constrained sensor platforms. However, the significant resource consumption imposed by public key cryptographic operations makes such mechanisms easy targets of Denial- of Service (DoS) attacks. For example, if digital signatures such as ECDSA are used directly for broadcast authentication without further protection, an attacker can simply broadcast forged packets and force the receiving nodes to perform a large number of unnecessary signature verifications, eventually exhausting their battery power. This paper studies how to deal with such DoS attacks when signatures are used for broadcast authentication in sensor networks. In particular, this paper presents two filtering techniques, a group-based filter and a key chain-based filter, to handle DoS attacks against signature verification. Both methods can significantly reduce the number of unnecessary signature verifications that a sensor node has to perform. The analytical results also show that these two techniques are efficient and effective for resource-constrained sensor networks.

Many sensor network applications require sensors' locations to function correctly. Despite the recent advances, location discovery for sensor networks in hostile environments has been mostly overlooked. Most of the existing localization protocols for sensor networks are vulnerable in hostile environments. The security of location discovery can certainly be enhanced by authentication. However, the possible node compromises and the fact that location determination uses certain physical features (e.g., received signal strength) of radio signals make authentication not as effective as in traditional security applications. This article presents two methods to tolerate malicious attacks against range-based location discovery in sensor networks. The first method filters out malicious beacon signals on the basis of the “consistency” among multiple beacon signals, while the second method tolerates malicious beacon signals by adopting an iteratively refined voting scheme. Both methods can survive malicious attacks even if the attacks bypass authentication, provided that the benign beacon signals constitute the majority of the beacon signals. This article also presents the implementation and experimental evaluation (through both field experiments and simulation) of all the secure and resilient location estimation schemes that can be used on the current generation of sensor platforms (e.g., MICA series of motes), including the techniques proposed in this article, in a network of MICAz motes. The experimental results demonstrate the effectiveness of the proposed methods, and also give the secure and resilient location estimation scheme most suitable for the current generation of sensor networks.

Many key predistribution techniques have been developed recently to establish pairwise keys between sensor nodes in wireless sensor networks. To further improve these schemes, researchers have also proposed to take advantage of the sensors' expected locations and discovered locations to help the predistribution of the keying materials. However, in many cases, it is very difficult to deploy sensor nodes at their expected locations or guarantee the correct location discovery at sensor nodes in hostile environments. In this article, a group-based deployment model is developed to improve key predistribution. In this model, sensor nodes are only required to be deployed in groups. The critical observation in the article is that the sensor nodes in the same group are usually close to each other after deployment . This deployment model is practical; it greatly simplifies the deployment of sensor nodes, while still providing an opportunity to improve key predistribution. Specifically, the article presents a novel framework for improving key predistribution using the group-based deployment knowledge. This framework does not require the knowledge of the sensors' expected or discovered locations and is thus suitable for applications where it is difficult to deploy the sensor nodes at their expected locations or correctly estimate the sensors' locations after deployment. To seek practical key predistribution schemes, the article presents two efficient instantiations of this framework, a hash key-based scheme and a polynomial-based scheme . The evaluation shows that these two schemes are efficient and effective for pairwise key establishment in sensor networks; they can achieve much better performance than the previous key predistribution schemes when the sensor nodes are deployed in groups.

Sensor nodes are often organized into clusters to facilitate many network operations such as data aggregation. Clustering has to be protected in hostile environments. Otherwise, an attacker can easily mislead a cluster-based application by attacking the clustering protocol. This paper proposes three techniques for resilient cluster formation. The simple neighbor validation provides a simple yet effective way to validate a sensor's neighbors; the priority-based selection organizes clusters basedon the sensor's priority of being a cluster head; and the centralized detection further enhances the security by detecting misbehaving nodes. Another appealing benefit of this protocol is that a sensor node can make a clustering decision immediately once the neighborhood information is available. This further increases the difficulty of attacking the clustering protocol. The analysis also shows that the proposed protocol is efficient and effective in dealing with attacks.

While many protocols for sensor network security provide confidentiality for the content of messages, contextual information usually remains exposed. Such information can be critical to the mission of the sensor network, such as the location of a target object in a monitoring application, and it is often important to protect this information as well as message content. There have been several recent studies on providing location privacy in sensor networks. However, these existing approaches assume a weak adversary model where the adversary sees only local network traffic. We first argue that a strong adversary model, the global eavesdropper, is often realistic in practice and can defeat existing techniques. We then formalize the location privacy issues under this strong adversary model and show how much communication overhead is needed for achieving a given level of privacy. We also propose two techniques that prevent the leakage of location information: periodic collection and source simulation. Periodic collection provides a high level of location privacy, while source simulation provides trade-offs between privacy, communication cost, and latency. Through analysis and simulation, we demonstrate that the proposed techniques are efficient and effective in protecting location information from the attacker.

Key management is the cornerstone for secure communication in sensor networks. Researchers have recently developed many techniques to setup pairwise keys between sensor nodes. However, these techniques allow an attacker to compromise a few sensor nodes and learn many pairwise keys used between non-compromised nodes. The attacker can then use these keys to impersonate non-compromised nodes and mislead the sensing application. To deal with this problem, this paper proposes to detect misused keys in sensor networks. The paper introduces a hidden layer of protection, which is designed for the security of pairwise keys rather than the messages in the network. It cannot be seen and will not be used by sensor nodes during normal communication. However, it can be checked by some special nodes to identify suspicious keys. With this idea, this paper develops a serial of techniques to detect misused keys. These techniques make it particularly difficult for an attacker to actively mislead the application using the compromised keys shared between non-compromised nodes. The paper also shows the effectiveness and efficiency of these techniques through analysis and experiments.

Sensors' locations play a critical role in many sensor network applications. A number of techniques have been proposed recently to discover the locations of regular sensors based on a few special nodes called beacon nodes, which are assumed to know their locations (e.g., through GPS receivers or manual configuration). However, none of these techniques can work properly when there are malicious attacks, especially when some of the beacon nodes are compromised. This paper introduces a suite of techniques to detect and remove compromised beacon nodes that supply misleading location information to the regular sensors, aiming at providing secure location discovery services in wireless sensor networks. These techniques start with a simple but effective method to detect malicious beacon signals. To identify malicious beacon nodes and avoid false detection, this paper also presents several techniques to detect replayed beacon signals. This paper then proposes a method to reason about the suspiciousness of each beacon node at the base station based on the detection results collected from beacon nodes, and then revoke malicious beacon nodes accordingly. Finally, this paper provides detailed analysis and simulation to evaluate the proposed techniques. The results show that our techniques are practical and effective in detecting malicious beacon nodes

Many sensor network applications require sensors' locations to function correctly. Despite the recent advances, location discovery for sensor networks in hostile environments has been mostly overlooked. Most of the existing localization protocols for sensor networks are vulnerable in hostile environments. The security of location discovery can certainly be enhanced by authentication. However, the possible node compromises and the fact that location determination uses certain physical features (e.g., received signal strength) of radio signals make authentication not as effective as in traditional security applications. This paper presents two methods to tolerate malicious attacks against beacon-based location discovery in sensor networks. The first method filters out malicious beacon signals on the basis of the "consistency" among multiple beacon signals, while the second method tolerates malicious beacon signals by adopting an it era lively refined voting scheme. Both methods can survive malicious attacks even if the attacks bypass authentication, provided that the benign beacon signals constitute the majority of the "consistent" beacon signals. This paper also presents the implementation of these techniques on MICA2 motes running TinyOS, and the evaluation through both simulation and field experiments. The experimental results demonstrate that the proposed methods are promising for the current generation of sensor networks.

Broadcast authentication is a critical security service in sensor networks; it allows a sender to broadcast messages to multiple nodes in an authenticated way. /spl mu/TESLA and multi-level /spl mu/TESLA have been proposed to provide such services for sensor networks. However, none of these techniques are scalable in terms of the number of senders. Though multi-level /spl mu/TESLA schemes can scale up to large sensor networks (in terms of receivers), they either use substantial bandwidth and storage at sensor nodes, or require significant resources at senders to deal with DOS attacks. This paper presents efficient techniques to support a potentially large number of broadcast senders using /spl mu/TESLA instances as building blocks. The proposed techniques are immune to the DOS attacks. This paper also provides two approaches, a revocation tree based scheme and a proactive distribution based scheme, to revoke the broadcast authentication capability from compromised senders. The proposed techniques are implemented, and evaluated through simulation on TinyOS. The analysis and experiment show that these techniques are efficient and practical, and can achieve better performance than the previous approaches.

Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. However, due to the resource constraints on sensor nodes, it is not feasible to use traditional key management techniques such as public key cryptography and key distribution center (KDC). A number of key predistribution techniques have been proposed for pairwise key establishment in sensor networks recently. To facilitate the study of novel pairwise key predistribution techniques, this paper develops a general framework for establishing pairwise keys between sensor nodes using bivariate polynomials. This paper then proposes two efficient instantiations of the general framework: a random subset assignment key predistribution scheme, and a hypercube-based key predistribution scheme. The analysis shows that both schemes have a number of nice properties, including high probability, or guarantee to establish pairwise keys, tolerance of node captures, and low storage, communication, and computation overhead. To further reduce the computation at sensor nodes, this paper presents an optimization technique for polynomial evaluation, which is used to compute pairwise keys. This paper also reports the implementation and the performance of the proposed schemes on MICA2 motes running TinyOS, an operating system for networked sensors. The results indicate that the proposed techniques can be applied efficiently in resource-constrained sensor networks.

Pairwise key establishment is a fundamental security service for sensor networks. However, establishing pairwise keys in sensor networks is a challenging problem, particularly due to the resource constraints on sensor nodes and the threat of node compromises. This article proposes to use both predeployment and postdeployment knowledge to improve pairwise key predistribution in static sensor networks. By exploiting the predeployment knowledge, this article first develops two key predistribution schemes, a closest pairwise keys scheme and a closest polynomials scheme . The analysis shows that these schemes can achieve better performance if the expected location information is available and that the smaller the deployment error is, the better performance they can achieve. The article then investigates how to use postdeployment knowledge to improve pairwise key predistribution in static sensor networks. The idea is to load an excessive amount of predistributed keys on sensor nodes, prioritize these keys based on sensors' actual locations discovered after deployment, and discard low-priority keys to thwart node compromise attacks. This approach is then used to improve the random subset assignment scheme proposed recently to demonstrate its practicality and effectiveness. The analysis indicates that the postdeployment knowledge can also greatly improve the performance and security of key predistribution.

Broadcast authentication is a fundamental security service in distributed sensor networks. This paper presents the development of a scalable broadcast authentication scheme named multilevel μTESLA based on μTESLA, a broadcast authentication protocol whose scalability is limited by its unicast-based initial parameter distribution. Multilevel μTESLA satisfies several nice properties, including low overhead, tolerance of message loss, scalability to large networks, and resistance to replay attacks as well as denial-of-service attacks. This paper also presents the experimental results obtained through simulation, which demonstrate the performance of the proposed scheme under severe denial-of-service attacks and poor channel quality.

Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. However, due to the resource constraints on sensors, it is infeasible to use traditional key management techniques such as public key cryptography and key distribution center (KDC). To facilitate the study of novel pairwise key predistribution techniques, this paper presents a general framework for establishing pairwise keys between sensors on the basis of a polynomial-based key predistribution protocol [2]. This paper then presents two efficient instantiations of the general framework: a random subset assignment key predistribution scheme and a grid-based key predistribution scheme. The analysis in this paper indicates that these two schemes have a number of nice properties, including high probability (or guarantee) to establish pairwise keys, tolerance of node captures, and low communication overhead. Finally, this paper presents a technique to reduce the computation at sensors required by these schemes.

This paper presents group key distribution techniques for large and dynamic groups over unreliable channels. The techniques proposed here are based on the self-healing key distribution methods (with revocation capability) recently developed by Staddon et al. [31]. By introducing a novel personal key distribution technique, this paper reduces (1) the communication overhead of personal key share distribution from O(t log q) to O(t log q), (2) the communication overhead of self-healing key distribution with t-revocation capability from O((mt + tm) log q) to O(mt log q), and (3) the storage overhead of the self-healing key distribution with t-revocation capability at each group member from O(m log q) to O(m log q), where t is the maximum number of colluding group members, m is the number of sessions, and q is a prime number that is large enough to accommodate a cryptographic key. All these results are achieved without sacrificing the unconditional security of key distribution. In addition, this paper presents two techniques that allow trade-off between the broadcast size and the recoverability of lost session keys. These two methods further reduce the broadcast message size in situations where there are frequent but short-term disruptions of communication and where there are long-term but infrequent disruptions of communication, respectively. Finally, this paper presents an API implementation of the proposed techniques.