21-05-2012, 12:56 PM
A Near-Optimal Social Network Defense Against Sybil Attacks
A Near-Optimal Social Network Defense.pdf (Size: 632.81 KB / Downloads: 21)
Abstract
Open-access distributed systems such as peer-to-peer
systems are particularly vulnerable to sybil attacks, where a malicious
user creates multiple fake identities (called sybil nodes).
Without a trusted central authority that can tie identities to real
human beings, defending against sybil attacks is quite challenging.
Among the small number of decentralized approaches, our recent
SybilGuard protocol leverages a key insight on social networks to
bound the number of sybil nodes accepted. Despite its promising
direction, SybilGuard can allow a large number of sybil nodes
to be accepted. Furthermore, SybilGuard assumes that social
networks are fast-mixing, which has never been confirmed in the
real world. This paper presents the novel SybilLimit protocol that
leverages the same insight as SybilGuard, but offers dramatically
improved and near-optimal guarantees. The number of sybil nodes
accepted is reduced by a factor of