Systems Colloquium
Thursday, February 25, 2010
4:00 p.m., AKW 200

Sign up to meet with speaker.

Speaker: Chris Lesniewski-Laas, MIT

Title: A Sybil-proof Distributed Hash Table

Abstract: Decentralized systems, such as Distributed Hash Tables (DHTs), are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This attack is very difficult to defend against without requiring strong identities, such as certificates issued by a central authority. Many proposed highly-scalable decentralized systems are based on DHTs. Currently, absent a global PKI, these designs cannot provide strong availability guarantees.

In this talk, I'll describe a novel DHT overlay routing protocol which is efficient and strongly resistant to the Sybil attack. The protocol uses the social connections between users to build routing tables that enable Sybil-resistant one-hop lookups. The number of Sybils in the social network does not affect the protocol's performance, but links between honest users and Sybils do. With a social network of N well-connected honest nodes, the protocol can tolerate up to O(N/log N) such "attack edges". This means that an adversary has to fool a large fraction of the honest users before any lookups will fail.

Bio: Chris Lesniewski-Laas is a graduate student in MIT's Computer Science and Artificial Intelligence Laboratory, where he studies distributed computer systems. He received a B.S. degree in Mathematics and an M.Eng. degree in EECS from MIT. His advisor is M. Frans Kaashoek. His primary interests are scaling and security for decentralized Internet systems, routing protocols, social networks, and incentives. He is a member of the MIT SIPB and PBK.