Anonymity in the wild: mixes on unstructured networks

Shishir Nagaraja

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

16 Citations (Scopus)


As decentralized computing scenarios get ever more popular, unstructured topologies are natural candidates to consider running mix networks upon. We consider mix network topologies where mixes are placed on the nodes of an unstructured network, such as social networks and scale-free random networks. We explore the efficiency and traffic analysis resistance properties of mix networks based on unstructured topologies as opposed to theoretically optimal structured topologies, under high latency conditions. We consider a mix of directed and undirected network models, as well as one real world case study - the LiveJournal friendship network topology. Our analysis indicates that mix-networks based on scale-free and small-world topologies have, firstly, mix-route lengths that are roughly comparable to those in expander graphs; second, that compromise of the most central nodes has little effect on anonymization properties, and third, batch sizes required for warding off intersection attacks need to be an order of magnitude higher in unstructured networks in comparison with expander graph topologies.

Original languageEnglish
Title of host publicationPrivacy Enhancing Technologies - 7th International Symposium, PET 2007, Revised Selected Papers
EditorsN. Borisov , P. Golle
Place of PublicationBerlin
Number of pages18
ISBN (Print)9783540755500
Publication statusPublished - 1 Dec 2007
Event7th International Symposium on Privacy Enhancing Technologies, PET 2007 - Ottawa, Canada
Duration: 20 Jun 200722 Jun 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4776 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Symposium on Privacy Enhancing Technologies, PET 2007


  • route length
  • expander graph
  • anonymous communication
  • unstructured network
  • sender anonymity
  • graph theory
  • random processes
  • telecommunication traffic
  • computer networks


Dive into the research topics of 'Anonymity in the wild: mixes on unstructured networks'. Together they form a unique fingerprint.

Cite this