A Discriminatory Rewarding Mechanism for Sybil Detection with Applications to Tor
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.
[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.
[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.
@article{"International Journal of Business, Human and Social Sciences:62810", author = "Asim Kumar Pal and Debabrata Nath and Sumit Chakraborty", title = "A Discriminatory Rewarding Mechanism for Sybil Detection with Applications to Tor", 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", volume = "4", number = "3", pages = "293-8", }
