Abstract: The Internet and the Web have arguably surpassed the von Neumann Computer as the most complex computational artifacts of our times. Out of all the formidable characteristics of the Internet/Web, it seems that the most novel is its socio-economic complexity. The Internet and the Web are built, operated and used by a multitude of very diverse economic interests, which compete or collaborate in various degrees. In fact, this suggests that some very important insights about the Web may come from a fusion of ideas from Algorithms with concepts and techniques from Mathematical Economics and Game Theory. Since 2000, a new field has emerged (Algorithmic Game Theory and Computational Internet Economics), which examines exactly such ideas. We feel that this field belongs to Web Science. Some of the main topics of that field examined so far are Internet equilibria, the so called “Price of Anarchy” (a measure of loss of optimality due to selfishness [Koutsoupias,Papadimitriou (1999)], electronic markets and their equilibria, auctions, and algorithmicmechanisms design (inverse game theory or how to design a game in the net in such a clever way that individual players, motivated solely by their selfish interests, actually end up meeting the goals of the game designer!). Our paper here surveys the main concepts and results of this very promising subfield.
Abstract: In this book chapter we will consider key establishment protocols for wireless sensor networks.
Several protocols have been proposed in the literature for the establishment of a shared group key for wired networks.
The choice of a protocol depends whether the key is established by one of the participants (and then transported to the other(s)) or agreed among the participants, and on the underlying cryptographic mechanisms (symmetric or asymmetric). Clearly, the design of key establishment protocols for sensor networks must deal with different problems and challenges that do not exist in wired networks. To name a few, wireless links are particularly vulnerable to eavesdropping, and that sensor devices can be captured (and the secrets they contain can be compromised); in many upcoming wireless sensor networks, nodes cannot rely on the presence of an online trusted server (whereas most standardized authentication and key establishment protocols do rely on such a server).
In particular, we will consider five distributed group key establishment protocols. Each of these protocols applies a different algorithmic technique that makes it more suitable for (i) static sensor networks, (ii) sensor networks where nodes enter sleep mode (i.e. dynamic, with low rate of updates on the connectivity graph) and (iii) fully dynamic networks where nodes may even be mobile. On the other hand, the common factor for all five protocols is that they can be applied in dynamic groups (where members can be excluded or added) and provide forward and backward secrecy. All these protocols are based on the Diffie-Hellman key exchange algorithm and constitute natural extensions of it in the multiparty case.