The fable of the bees: Incentivizing robust revocation decision making in ad hoc networks

Abstract

In this paper we present a new key-revocation scheme for ad hoc network environments with the following characteristics: • Distributed: Our scheme does not require a permanently available central authority. • Active: Our scheme incentivizes rational (selfish but honest) nodes to revoke malicious nodes. • Robust: Our scheme is resilient against large numbers of colluding malicious nodes (30% of the network for a detection error rate of 15%). • Detection error tolerant: Revocation decisions fundamentally rely on intrusion detection systems (IDS). Our scheme is active for any meaningful IDS (IDS error rate < 0.5) and robust for an IDS error rate of up to 29%. Several schemes in the literature have two of the above four characteristics (characteristic four is typically not explored). This work is the first to possess all four, making our revocation scheme well-suited for environments such as ad hoc networks, which are very dynamic, have significant bandwidth-constraints, and where many nodes must operate under the continual threat of compromise. Copyright 2009 ACM.