TY - GEN
T1 - Optimal Sybil-resilient node admission control
AU - Tran, Nguyen
AU - Li, Jinyang
AU - Subramanian, Lakshminarayanan
AU - Chow, Sherman S.M.
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79960849345&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960849345&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2011.5935171
DO - 10.1109/INFCOM.2011.5935171
M3 - Conference contribution
AN - SCOPUS:79960849345
SN - 9781424499212
T3 - Proceedings - IEEE INFOCOM
SP - 3218
EP - 3226
BT - 2011 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2011
Y2 - 10 April 2011 through 15 April 2011
ER -