### Abstract

Most existing large-scale networked systems on the Internet such as peer-to-peer systems are vulnerable to Sybil attacks where a single adversary can introduce many bogus identities. One promising defense of Sybil attacks is to perform social-network based admission control to bound the number of Sybil identities admitted. SybilLimit [22], the best known Sybil admission control mechanism, can restrict the number of Sybil identities admitted per attack edge to O(log n) with high probability assuming O(n/log n) attack edges. In this paper, we propose Gatekeeper, a decentralized Sybil-resilient admission control protocol that significantly improves over SybilLimit. Gatekeeper is optimal for the case of O(1) attack edges and admits only O(1) Sybil identities (with high probability) in a random expander social networks (real-world social networks exhibit expander properties). In the face of O(k) attack edges (for any k ∈ O(n/ log n)), Gatekeeper admits O(log k) Sybils per attack edge. This result provides a graceful continuum across the spectrum of attack edges. We demonstrate the effectiveness of Gatekeeper experimentally on real-world social networks and synthetic topologies.

Original language | English (US) |
---|---|

Title of host publication | 2011 Proceedings IEEE INFOCOM |

Pages | 3218-3226 |

Number of pages | 9 |

DOIs | |

State | Published - 2011 |

Event | IEEE INFOCOM 2011 - Shanghai, China Duration: Apr 10 2011 → Apr 15 2011 |

### Publication series

Name | Proceedings - IEEE INFOCOM |
---|---|

ISSN (Print) | 0743-166X |

### Other

Other | IEEE INFOCOM 2011 |
---|---|

Country | China |

City | Shanghai |

Period | 4/10/11 → 4/15/11 |

### ASJC Scopus subject areas

- Computer Science(all)
- Electrical and Electronic Engineering

## Fingerprint Dive into the research topics of 'Optimal Sybil-resilient node admission control'. Together they form a unique fingerprint.

## Cite this

*2011 Proceedings IEEE INFOCOM*(pp. 3218-3226). [5935171] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2011.5935171