As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any message unless it collaborates with every other mix participating in the cascade through which that message passes.

Most of the mix-net projects about which I have read (both those that have been implemented and those that remain theoretical) mitigate such a "collaboration attack" by introducing randomness into path selection: thus an adversary must collaborate with a significant proportion of all mixes throughout the network in order to achieve a high probability that those in any given cascade will all be collaborators. Various techniques have been suggested to further frustrate an adversary who attempts to so bias the network, such as viewing all mixes on a single subnet as potential collaborators.

If one is certain (at least, as much as one can ever be) that some particular mixes are honest (i.e. not collaborating with an adversary), it would at first glance appear desirable to ensure that at least one such honest mix is included in every cascade used for one's messages so as to significantly reduce (if not completely eliminate) the threat of such "collaboration attacks".

However, forcing all one's messages to pass through a subset of the network that is defined by one's trust relationships leaks information about those relationships. Over time, an adversary might be able to use such information to link together all one's messages or even identify oneself.

My question is: how can one measure this trade-off? Is there existing research that already has considered it (I have not been able to find any yet)?

Where senders are themselves also acting as mixes in the presence of sufficient inbound cover traffic, does the inclusion of known honest mixes in downstream cascades for their own messages actually provide any additional anonymity given that those messages could arguably have been forwarded for another party?

  • $\begingroup$ I don't see what this question has to do with cryptography. Sure mix nets use cryptography, but the question in and of itself has nothing to do with cryptography. Perhaps there is a better place on StackExchange for this question, where you will get good answers. $\endgroup$
    – mikeazo
    Jun 25, 2012 at 16:47
  • 2
    $\begingroup$ Seems reasonable to me (I'm a TCS mod) $\endgroup$ Jun 25, 2012 at 21:29

2 Answers 2


I haven't seen a paper that addresses your (first) question specifically. One extreme example of a mix node that you trust is yourself, if you are participating in the network as well as using it. One paper that talks about the trade-offs of using yourself as a node in a mix network is: On the Economics of Anonymity. It sort of addresses your second question.

While Tor is not exactly a mix network, I believe it carefully chooses entry nodes based on individuals the network maintainers trust. In this case, all users have the same "trust network" and so it avoids the problem you are proposing to study. The drawback is you personally must trust the same nodes.

As to your specific question, I haven't seen a paper that specifically addresses what you want but I also do not follow the area closely. Most papers on Mix Networks are catalogued here: http://freehaven.net/anonbib/ and so you could thumb through the titles for something that might be related.

Finally, I'm not sure you'll find the adversary has much power unless if they can observe large portions of the network, in which case there are more effective attacks (especially in Tor-like anonymity networks which don't actually mix or obfuscate packet timing).

  • $\begingroup$ Assume the adversary can observe large portions of the network, but assume a high-latency network as originally proposed by Chaum rather than the lower-latencies achieved by Tor. Your link to "On the Economics of Anonymity" is useful (thank you) -- I am still reading through it -- but I fear it doesn't really answer the question around the extent to which one can be compromised by one's trust relationships, which is really what I was after. $\endgroup$
    – eggyal
    Jun 28, 2012 at 10:36
  • $\begingroup$ In a proper mixnet, if you pass your messages through a node that turns out to be trustworthy, the message will always be anonymous within the set of messages mixed by that node (assuming the other senders don't voluntarily reveal which messages are their's -- or are from the adversary -- which is a different attack vector). So you can never fully link together messages (assuming the messages themselves are not linkable -- again a different attack vector). As the message propagates to mixes that mix in different messages, the adversary could stop the anonymity set from growing but that's it. $\endgroup$
    – PulpSpy
    Jun 28, 2012 at 14:07
  • $\begingroup$ But if an adversary is able to witness that all of Alice's messages are relayed through Bob's mix (perhaps because the adversary colludes with every mix between Alice and Bob), then he will be able to determine that Alice trusts Bob even though he can't determine what happened to the message thereafter. Surely that is a new attack vector which has not been discussed in any of the literature you've cited? $\endgroup$
    – eggyal
    Jun 28, 2012 at 14:56
  • $\begingroup$ I see. Agreed it is not in the papers I've cited or ever seen. $\endgroup$
    – PulpSpy
    Jun 28, 2012 at 20:25

It is hard to answer without knowing your exact adversary model. For example, does the adversary know all of the mixes you trust? What is the adversary able to see (only what is coming into your trusted mixes and what goes out)? How much of the network besides the trusted mixes does the adversary control?

Looking at the worst case (you have only one trusted mix, and you are the only person in the entire network who uses that mix, and the adversary controls all other nodes in the cascade), it would seem that anonymity would be completely broken.

In a slightly better case, say the trusted mix is highly used by others. It now seems that the system remains secure. The attacker could follow your packets up until the trusted mix is used, but after that, the attacker should have no idea which packets are yours.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.