Resource Burning based Sybil Defense
Abstract:
A Sybil attack occurs when an adversary pretends to be multiple identities (IDs). Limiting the number of Sybil (bad) IDs to a minority permits the use of well-established tools for tolerating malicious behavior, such as protocols for Byzantine consensus and secure multiparty computation.
A popular technique for enforcing this minority is resource burning; that is, the verifiable consumption of a network resource, such as computational power, bandwidth, or memory. Unfortunately, typical defenses based on resource burning require non-Sybil (good) IDs to consume at least as many resources as the adversary.
In this talk, we will discuss a Sybil defense, ERGO, that guarantees (1) there is always a minority of Sybil IDs; and (2) when the system is under significant attack, the good IDs consume asymptotically less than the bad. In particular, for churn rate that can vary exponentially, the resource burning rate of ERGO is O(Square Root (T J) + J), where T is the resource burning rate of the adversary and J is the join rate of good IDs.
Biodata:
I am a Research Fellow at the National University of Singapore, under Prof. Seth Gilbert. I obtained my Ph.D. from the University of New Mexico, USA, under the advisement of Prof. Jared Saia. My current research is focused on designing provably secure, scalable, and efficient protocols for distributed systems.
In general, topics related to Randomized Algorithms, Distributed Graph Algorithms, Algorithmic Game Theory, and Biologically-inspired Algorithms spike my interest. In my free time, I like solving mathematical puzzles, reading sci-fiction, and traveling. I have served on the boards of various student and departmental organizations – UNM CS Advisory Board (Graduate Representative), Computer Science Graduate Student Association (CSGSA) (President), and UNM Women in Computing (Vice President).