Revocation Games in Ephemeral Networks

An ephemeral network is usually defined by the very short-lived and heterogeneous nature of interactions among self-organizing wireless devices. The wide penetration in everyday gadgets of radio technologies operating in unlicensed frequency spectrum, such as Bluetooth or 802.11 WLANs, accentuates the risk involved in communicating with unknown nodes, especially in hostile environments. Thus, misbehavior in ephemeral networks poses a serious threat to both well-behaving nodes and the network itself. The lack of centralized infrastructure and control makes such networks vulnerable to abuses, resulting in local service degradations and interruptions. Due to the short-lived and heterogeneous contacts among nodes, the reputation mechanisms based on repeated interactions are hard to establish and thus local revocation schemes seem to better cope with the highly volatile network model. In this report, we present a fully distributed scheme for local revocation of public-key certificates using a game-theoretic approach, in which each node selfishly decides on its actions and where, for each action, there is an associated cost and benefit. By providing incentives, dynamic costs and thanks to the history of previous behavior, our payoff model establishes the best course of actions for all the involved devices on-the-fly, such that the resulting revocation generates the least cost for the collectivity of players, i.e. a successful revocation that is also socially optimal. Based on the analytical results, we then formally define such algorithm and evaluate its performance through simulations. We show that our scheme is both accurate and effective in quickly removing malicious devices from the network.