Small Worlds and the Security of Ubiquitous Computing Harald Vogt ETH Zurich Department of Computer Science Abstract This paper considers the small-world phenomenon in two contexts: ubiquitous computing and security. We argue that small-world properties emerge in ubicomp systems due to their natural occurrence in human-centered networks and their meaning as a system design principle. The relationship of small worlds and security is examined from two viewpoints. First, results on the security of small-world networks are reviewed. Second, we look into how small-world properties are obstacles to, or can be helpful in maintaining security guarantees. We then give an example of how to improve the communication security in large-scale, self-organizing networks.