Please use this identifier to cite or link to this item:
https://doi.org/10.1109/TNET.2009.2034047
Title: | SybilLimit: A near-optimal social network defense against sybil attacks | Authors: | Yu, H. Gibbons, P.B. Kaminsky, M. Xiao, F. |
Keywords: | Social networks Sybil attack Sybil identities SybilGuard SybilLimit |
Issue Date: | 2010 | Citation: | Yu, H., Gibbons, P.B., Kaminsky, M., Xiao, F. (2010). SybilLimit: A near-optimal social network defense against sybil attacks. IEEE/ACM Transactions on Networking 18 (3) : 885-898. ScholarBank@NUS Repository. https://doi.org/10.1109/TNET.2009.2034047 | 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 Θ(□n), or around 200 times in our experiments for a million-node system. We further prove that SybilLimit's guarantee is at most a log n factor away from optimal when considering approaches based on fast-mixing social networks. Finally, based on three large-scale real-world social networks, we provide the first evidence that real-world social networks are indeed fast-mixing. This validates the fundamental assumption behind SybilLimit's and SybilGuard's approach. © 2006 IEEE. | Source Title: | IEEE/ACM Transactions on Networking | URI: | http://scholarbank.nus.edu.sg/handle/10635/39830 | ISSN: | 10636692 | DOI: | 10.1109/TNET.2009.2034047 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.