A Discriminatory Rewarding Mechanism for Sybil Detection with Applications to Tor

Authors: Asim Kumar Pal, Debabrata Nath, Sumit Chakraborty

Abstract:

This paper presents an economic game for sybil detection in a distributed computing environment. Cost parameters reflecting impacts of different sybil attacks are introduced in the sybil detection game. The optimal strategies for this game in which both sybil and non-sybil identities are expected to participate are devised. A cost sharing economic mechanism called Discriminatory Rewarding Mechanism for Sybil Detection is proposed based on this game. A detective accepts a security deposit from each active agent, negotiates with the agents and offers rewards to the sybils if the latter disclose their identity. The basic objective of the detective is to determine the optimum reward amount for each sybil which will encourage the maximum possible number of sybils to reveal themselves. Maintaining privacy is an important issue for the mechanism since the participants involved in the negotiation are generally reluctant to share their private information. The mechanism has been applied to Tor by introducing a reputation scoring function.

Keywords: Game theory, Incentive mechanism, Reputation, Sybil Attack

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081798

References:

[1] A. Cheng and E. Friedman, "Sybil-proof reputation mechanisms", Proceedings of ACM SIGCOMM Workshop on Economics of Peer-to- Peer Systems, 2005, pp. 128-132.
[2] B. Lee, C. Boyd, E. Dawson, K. Kim, J. Yang and S. Yahoo, "Providing receipt freeness in mix-net based voting protocols", Proc.- Sixth International Conference on Information Security and Cryptology, Seoul, 2003.
[3] B.N. Levine, C. Shields and N.B. Margolin, "A Survey of Solutions to the Sybil Attack", Tech. Report, University of Massachusetts, Amherst, MA, 2006.
[4] C. Karlof and D. Wagner, "Secure routing in wireless sensor networks: Attacks and counter measurements", Ad hoc networks Journal (Elsevier) 1 (2-3), 2003, pp. 293-315.
[5] C. Piro, C. Shields and B. N. Levine, "Detecting the Sybil attack in adhoc networks", Proceedings of IEEE / ACM SecureComm, 2006.
[6] J. Douceur, "The Sybil attack", Proceedings of Workshop on P2P systems (IPTPS), 2002.
[7] J. Newsome, E. Shi, D. Song, and A. Perrig, "The Sybil attack in sensor networks: analyses & defenses", Proceedings of IPSN Intl Symposium, 2004, pp. 259-268.
[8] M. Yokoo, Y. Sakurai and S. Matsubara, "The effect of false-name bids in combinatorial auctions: new fraud in internet auctions", Games and Economic Behavior, vol. 46, No. 1, 2004, pp. 174-188.
[9] N.B. Margolin and B.N. Levine, "Quantifying and discouraging sybil attacks", Tech. Rep 2005-67, University of Massachusetts Amherst, 2005.
[10] N.B. Margolin and B.N. Levine, "Informant: Detecting Sybils Using Incentives", Proceedings of Financial Cryptography, 2007.
[11] N.B. Margolin, M. Wright and B.N. Levine, "Analysis of an incentive based protection system", Proceedings of ACM Digital Rights Management Workshop, 2004.
[12] N. Nissan and A. Ronen, "Algorithmic mechanism design", Games Economic Behavior, 35:166-196, 2001.
[13] S. Chakraborty, "A study of several privacy-preserving multi-party negotiation problems with applications to supply chain management" Doctoral dissertation, Indian Institute of Management Calcutta, 2007 (unpublished).
[14] S. Rubin, M. Christodorescu, V. Ganapathy, J.T. Giffin, L. Kruger, H. Wang and N. Kidd, "An auctioning reputation system based on anomaly", Proceedings of ACM conference on Computer and Communications Security, 2005, pp. 270-279.
[15] W. Muller, H. Plotz, J.P. Redich and T. Shiraki, "Sybil proof anonymous reputation management", SecureComm, 2008.
[16] Y. Haifeng, M. Kaminsky, P.B. Gibbons and A. Flaxman, "Sybilguard: Defending against Sybil attacks via social networks", ACM Sigcomm-06, September 11-15, 2006, Pisa, Italy.
[17] Y. Zhou, Y. Zhang and Y. Fang, "Access control in wireless sensor networks", Adhoc networks, Volume 5, 2007, pp. 3-13.
[18] R. Dingledine, N. Mathewson and P. Syverson, "Tor: The secondgeneration onion router", In Proceedings of the 13th USENIX Security Symposium, August 2004.
[19] I. Goldberg, "On the security of the tor authentication protocol", In Proceedings of the Sixth Workshop on Privacy Enhancing Technologies (PET 2006) (Cambridge, UK, June 2006), Springer.
[20] J. Feigenbaum, A. Johnson, and P. Syverson, "A model of onion routing with provable anonymity", In Proceedings of the 11th Financial Cryptography and Data Security Conference (FC 2007), 2007.