Special Issue: Surveys

• Computer Network and Internet • Previous Articles     Next Articles

Survey on Anonymity in Unstructured Peer-to-Peer Systems

Ren-Yi Xiao   

  1. National Natural Science Foundation of China, Beijing 100085, China
  • Received:2007-12-22 Revised:2008-04-10 Online:2008-07-10 Published:2008-07-10

Although anonymizing Peer-to-Peer (P2P) networks often means extra cost in terms of transfer efficiency, many systems try to mask the identities of their users for privacy consideration. By comparison and analysis of existing approaches, we investigate the properties of unstructured P2P anonymity, and summarize current attack models on these designs. Most of these approaches are path-based, which require peers to pre-construct anonymous paths before transmission, thus suffering significant overhead and poor reliability. We also discuss the open problems in this field and propose several future research directions.

Key words: monotone graph property; decision tree; complexity; elusive;

[1] Anonymity. http://freehaven.net/anonbib/topic.html.
[2]} ISO IS 15408. 1999, http://www.commoncriteria.org.
[3]} Pfitzmann A, Hansen M. Anonymity, unlinkability, unobservability, pseudonymity, and identity management --- A consolidated proposal for terminology. Technical Report, 2005.
[4]} ISO/IEC 15408-2. http://standards.iso.org/ittf/PubliclyAva\-ilableStandards/, 2005.
[5]} Stoica I, Morris R, Karger D, Kaashoek F, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for Internet applications. In {\it Proc. ACM SIGCOMM}, San Diego, California, USA, 2001, pp.149--160.
[6]} Rowstron A, Druschel P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In {\it Proc. Middleware}, Heidelberg, Germany, Nov. 2001, pp.329--350.
[7]} Zhao B Y, Huang L, Stribling J, Rhea S C, Joseph A D, Kubiatowicz J D. Tapestry: A resilient global-scale overlay for service deployment. {\it IEEE Journal on Selected Areas in Communications} ({\it JSAC}), 2004, 22(1): 41--53.
[8]} Ratnasamy S, Francis P, Handley M, Karp R, Shenker S. A scalable content-addressable network. In {\it Proc. ACM SIGCOMM}, San Diego, California, USA, 2001, pp.161--172.
[9]} Napster. http://www.napster.com.
[10]} KaZaA. http://www.kazaa.com.
[11]} BitTorrent. http://www.bittorrent.com/.
[12]} Gnutella. http://gnutella.wego.com/.
[13]} Liu Y, Xiao L, Liu X, Ni L M, Zhang X. Location awareness in unstructured peer-to-peer systems. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2005, 16(2): 163--174.
[14]} Liu X, Liu Y, Xiao L. Improving query response delivery quality in peer-to-peer systems. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2006, 17(11): 1335--1347.
[15]} Xiao L, Liu Y, Ni L M. Improving unstructured peer-to-peer systems by adaptive connection establishment. {\it IEEE Transactions on Computers}, 2005, 54(9): 1091--1103.
[16]} Liao X, Jin H, Liu Y, Ni L M. Scalable live streaming service based on inter-overlay optimization. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2007, 18: 1663--1674.
[17]} Liu Y, Zhuang Z, Xiao L, Ni L M. A distributed approach to solving overlay mismatch problem. In {\it Proc. the 24th International Conference on Distributed Computing Systems $($ICDCS$)$}, Hachioji, Tokyo, Japan, 2004, pp.132--139.
[18]} Liu Y, Xiao L, Ni L M. Building a scalable bipartite P2P overlay network. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2007, 18(9): 1296--1306.
[19]} Wang C, Xiao L, Liu Y, Zheng P. DiCAS: An efficient distributed caching mechanism for P2P systems. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2006, 17(10): 1097--1109.
[20]} Xiao L, Zhuang Z, Liu Y. Dynamic layer management in super-peer architectures. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2005, 16(11): 1078--1091.
[21]} Chothia T, Chatzikokolakis K. A survey of anonymous peer-to-peer file-sharing. In \it Proc. IFIP International Symposium on Network-Centric Ubiquitous Systems $($NCUS$)$, \rm Nagasaki, Japan, 2005, pp.744--755.
[22]} Rogers M, Bhatti S. How to disappear completely: A survey of private peer-to-peer networks. In \it Proc. International Workshop on Sustaining Privacy in Autonomous Collaborative Environments $($SPACE$)$, \rm Moncton, New Brunswick, Canada, 2007.
[23]} Nambiar A, Wright M. Salsa: A structured approach to large-scale anonymity. In \it Proc. ACM CCS, \rm Alexandria, VA, USA, 2006, pp.17--26.
[24]} Scarlata V, Levine B N, Shields C. Responder anonymity and anonymous peer-to-peer file sharing. In \it Proc. the 9th International Conference of Network Protocol $($ICNP$)$, \rm Riverside, CA, USA, 2001, pp.272--280.
[25]} Dingledine R, Mathewson N, Syverson P. Tor: The second-generation onion router. In \it Proc. the 13th USENIX Security Symposium, \rm San Diego, CA, USA, 2004, pp.303--320.
[26]} Rennhard, Plattner B. Introducing MorphMix: Peer-to-peer based anonymous Internet usage with collusion detection. In \it Proc. ACM Workshop on Privacy in the Electronic Society, \rm Washington DC, USA, 2002, pp.91--102.
[27]} Bennett K, Grothoff C. GAP --- Practical anonymous networking. In \it Proc. Privacy Enhancing Technologies Workshop, \rm Germany, 2003, pp.141--160.
[28]} Reiter M K, Rubin A D. Crowds: Anonymity for web transactions. {\it ACM Transactions on Information and System Security}, 1998, 1(1): 66--92.
[29]} Xiao L, Xu Z, Zhang X. Low-cost and reliable mutual anonymity protocols in peer-to-peer networks. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2003, 14(9): 829--840.
[30]} Mislove A, Oberoi G, Post A, Reis C, Druschel P, Wallach D S. AP3: Cooperative, decentralized anonymous communication. In \it Proc. the 11th ACM SIGOPS European Workshop, \rm Leuven, Belgium, 2004, Article No.30.
[31]} Freedman M, Morris R. Tarzan: A peer-to-peer anonymizing network layer. In \it Proc. the 9th ACM Conference on Computer and Communications Security $($CCS$)$, \rm Washington DC, USA, 2002, pp.193--206.
[32]} Liu D, Chi C-H, Li M. Normalizing traffic pattern with anonymity for mission critical applications. In \it Proc. the 37th Annual Simulation Symposium, \rm Arlington, USA, 2004, pp.293--299.
[33]} Berthold O, Langos H. Dummy traffic against long term intersection attacks. In \it Proc. Privacy Enhancing Technologies Workshop $($PET$)$, \rm San Francisco, CA, USA, 2002, pp.199--203.
[34]} Dingledine R, Freedman M J, Molnar D. The free haven project: Distributed anonymous storage service. In \it Proc. Workshop on Design Issues in Anonymity and Unobservability, \rm Berkeley, California, USA, 2000, pp.67--95.
[35]} Han J, Liu Y, Xiao L, Xiao R, Ni L M. A mutual anonymous peer-to-peer protocol design. In \it Proc. the 19th International Parallel $\&$ Distributed Processing Symposium $($IEEE IPDPS$)$, \rm Denver, CA, USA, 2005, p.68.1.
[36]} Han J, Liu Y. Mutual anonymity for mobile peer-to-peer systems. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}). (To appear)
[37]} Han J, Liu Y. Rumor riding: Anonymizing unstructured peer-to-peer systems. In \it Proc. IEEE International Conference on Network Protocols $($ICNP$)$, \rm Santa Barbara, California, 2006, pp.22--31.
[38]} Serjantov A. Anonymizing censorship resistant systems. In \it Proc. the 1st International Workshop on Peer-to-Peer Systems, \rm Cambridge, MA, USA, 2002, pp.111--120.
[39]} Waldman M, Rubin A D, Cranor L F. Publius: A robust, tamper-evident, censorship-resistant web publishing system. In \it Proc. the 9th USENIX Security Symposium, \rm Denver, Colorado, USA, 2000, pp.59--72.
[40]} Roger Dingledine. The free haven project: Design and deployment of an anonymous secure data haven [Thesis]. MIT, June 2000.
[41]} Sherwood R, Bhattacharjee B, Srinivasan A. P$^{5}$: A protocol for scalable anonymous communication. In \it Proc. IEEE Symposium on Security and Privacy, \rm Oakland, California, USA, 2002, pp.58--70.
[42]} Levine B N, Shields C. Hordes: A multicast based protocol for anonymity. {\it Journal of Computer Security}, 2002, 10(3): 213--240.
[43]} Wang Y, Dasgupta P. Anonymous communications on the Internet. In \it Proc. the IASTED International Conference on Communication, Network and Information Security, \rm Phoenix, Arizona, USA, 2005, p.499.
[44]} Waters B R, Felten E W, Sahai A. Receiver anonymity via incomparable public keys. In \it Proc. the 10th ACM Conference on Computer and Communications Security $($ACM CCS$)$, \rm Washington DC, USA, 2003, pp.112--121.
[45]} Luo X, Qin Z, Han J, Chen H. DHT-assisted probabilistic exhaustive search in unstructured P2P networks. In \it Proc. the 22nd IEEE International Parallel and Distributed Processing Symposium $($IEEE IPDPS$)$, \rm Miami, Florida, USA, 2008. (To appear)
[46]} Nandan A, Pau G, Salomoni P. GhostShare --- Reliable and anonymous P2P video distribution. In \it Proc. the 1st IEEE Global Telecommunications Conference $($GlobeCom$)$ Workshops, \rm Dallas, Texas, USA, 2004, pp.200--210.
[47]} Clarke I, Sandberg O, Wiley B, Hong T W. Freenet: A distributed anonymous information storage and retrieval system. In \it Proc. Workshop on Design Issues in Anonymity and Unobservability, \rm Berkeley, CA, USA, 2000, pp.44--66.
[48]} Wright M K, Adler M, Levine B N, Shields C. The predecessor attack: An analysis of a threat to anonymous communications systems. {\it ACM Transactions on Information and System Security} $(${\it TISSEC}$)$, 2004, 7(4): 489--522.
[49]} Shmatikov V. Probabilistic analysis of anonymity. In \it Proc. the 15th IEEE Computer Security Foundations Workshop $($CSFW$)$, \rm Cape Breton, Nova Scotia, Canada, 2002, pp.119--128.
[50]} Zhu Y, Bettati R. Anonymity vs. information leakage in anonymity systems. In \it Proc. the 25th IEEE International Conference on Distributed Computing Systems $($ICDCS$)$, \rm Columbus, Ohio, USA, 2005, pp.514--524.
[51]} Guan Y, Fu X, Bettati R, Zhao W. A quantitative analysis of anonymous communications. {\it IEEE Transaction on Reliability}, 2004, 53(1): 103--115.
[52]} Levine B N, Reiter M K, Wang C, Wright M. Timing attacks in low-latency mix systems. In \it Proc. the 8th International Conference on Financial Cryptography, \rm Key West, Florida, USA, 2004, pp.251--265.
[53]} Serjantov A, Sewell P. Passive attack analysis for connection-based anonymity systems. In \it Proc. European Symposium on Research in Computer Security $($ESORICS$)$, \rm Norway, 2003, pp.116--131.
[54]} Fu X, Graham B, Xuan D, Bettati R, Zhao W. Analytical and empirical analysis of countermeasures to traffic analysis attacks. In \it Proc. IEEE International Conference on Parallel Processing $($ICPP$)$, \rm Kaohsiung, 2003, pp.483--492.
[55]} Fu X, Zhu Y, Graham B, Bettati R, Zhao W. On flow marking attacks in wireless anonymous communication networks. In \it Proc. the 25th International Conference on Distributed Computing Systems $($IEEE ICDCS$)$, \rm Columbus, Ohio, USA, 2005, pp.493--503.
[56]} Guan Y, Li C, Xuan D, Bettati R, Zhao W. Preventing traffic analysis for real-time communication networks. In \it Proc. IEEE Military Communications $($MILCOM$)$, \rm Atlantic City, NJ, USA, 1999, vol.1, pp.744--750.
[57]} Murdoch S J. Danezis G. Low-cost traffic analysis of Tor. In \it Proc. IEEE Symposium on Security and Privacy, \rm Oakland, California, USA, 2005, pp.183--195.
[58]}Breslau L, Cao P, Fan L, Phillips G, Shenker S. Web caching and Zipf-like distributions: Evidence and implications. In \it Proc. IEEE INFOCOM, \rm New York, USA, Vol.1, 1999, pp.126--134.
[59]} Lu L, Han J, Liu Y, Hu L, Huai J, Ni L M, Ma J. Pseudo trust: Zero-knowledge authentication in anonymous P2Ps. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}). (To appear)
[60]} Han J, Liu Y. Dubious feedback: Fair or not? In \it Proc. International Workshop on Peer-to-Peer Information Management $($P2PIM$)$, \rm Hong Kong, 2006, Article No.49.
[61]} Tan G, Jarvis S. A payment-based incentive and service differentiation scheme for peer-to-peer streaming broadcast. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}), 2007, 19(7): 940--953.
[62]} Xiao L, Zhu Y, Xu Z, Ni L. Incentive-based decentralized scheduling for computational grids. {\it IEEE Transactions on Parallel and Distributed Systems} ({\it TPDS}). (To appear)
[1] Gilad Katz, Asaf Shabtai, Lior Rokach, and Nir Ofek. ConfDTree:Statistical Methods for Improving Decision Trees [J]. , 2014, 29(3): 392-407.
[2] David P. Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field [J]. , 2012, 27(4): 678-686.
[3] You-Ming Qiao (乔友明), Jayalal Sarma M.N., and Bang-Sheng Tang (唐邦晟). On Isomorphism Testing of Groups with Normal Hall Subgroups [J]. , 2012, 27(4): 687-701.
[4] Yi Wu (吴奕). Pricing Loss Leaders Can be Hard [J]. , 2012, 27(4): 718-726.
[5] Yu-Ping Shen (沈榆平) and Xi-Shun Zhao (赵希顺). NP-Logic Systems and Model-Equivalence Reductions [J]. , 2010, 25(6): 1321-1326.
[6] Yu-Tao Ma (马于涛), Member, CCF, ACM, Ke-Qing He (何克清), Senior Member, CCF, IEEE, Bing Li (李兵), Senior Member, CCF, Jing Liu (刘婧) and Xiao-Yan Zhou (周晓燕). A Hybrid Set of Complexity Metrics for Large-Scale Object-Oriented Software Systems [J]. , 2010, 25(6): 1184-1201.
[7] Chong Long(龙 翀), Min-Lie Huang(黄民烈), Xiao-Yan Zhu(朱小燕), Member, CCF and Ming Li(李 明), Fellow, ACM, IEEE. A New Approach for Multi-Document Update Summarization [J]. , 2010, 25(4): 739-749.
[8] Mohamed Farouk Abdel Hady and Friedhelm Schwenker. Combining Committee-Based Semi-Supervised Learning and Active Learning [J]. , 2010, 25(4): 681-698.
[9] Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack [J]. , 2008, 23(5 ): 749-762 .
[10] Jian-Xin Wang, Xiao-Shuang Xu, and Jian-Er Chen. Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs [J]. , 2008, 23(5 ): 763-768 .
[11] Ji-Gang Wu, Thambipillai Srikanthan, and Guang-Wei Zou. New Model and Algorithm for Hardware/Software Partitioning [J]. , 2008, 23(4 ): 644-651 .
[12] Xue-Gang Hu, Pei-Pei Li, Xin-Dong Wu, and Gong-Qing Wu. A semi-random multiple decision-tree algorithm for mining data streams [J]. , 2007, 22(5): 711-724 .
[13] Wen-Ling Wu, Wen-Tao Zhang, and Deng-Guo Feng. Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia [J]. , 2007, 22(3): 449-456 .
[14] En-Jian Bai and Xiao-Juan Liu. Some Notes on Prime-Square Sequences [J]. , 2007, 22(3): 481-486 .
[15] Swapan Bhattacharya and Ananya Kanjilal. Code Based Analysis for Object-Oriented Systems [J]. , 2006, 21(6): 965-972 .
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved