How do mix networks work with server downtime?

I am looking for an analysis of practical mix networks with server downtime.

For example, if a message is supposed to go from A -> B -> C -> D, what happens if B wants to send the message but C is offline temporarily?

This could be a stop-and-go mix network so holding onto a message longer is OK, but I am wondering whether there's any paper analyzing this sort of thing? For instance, how does it affect anonymity, how does B know when to retry sending it, etc?

Or what if C goes offline permanently, is the message lost? Is there a mix network protocol for resilience in this case?

• If B wants to send to C and C is offline, then B cannot send. This has no impact on anonymity, because B not sending doesn't reduce anonymity. If C is permanently offline, then the mix cannot complete. But, I don't feel like I'm answering your question, perhaps you could clarify? – Alpha Bravo Aug 8 '18 at 15:06
• Maybe you're asking whether the mixnet can work if C doesn't participate (for whatever reason). That depends on the particular mixnet you're using. For onion routing, where the ciphertext is of the form $enc(pk_A, enc(pk_B, enc(pk_C, enc(pk_D, m))))$, the mixnet cannot work, because C doesn't participate, hence, the layer of the onion encrypted by $pk_C$ cannot be removed. By comparison, for a re-encryption mixnet, the mixnet works, since B can just send to D. The resulting reduction in anonymity corresponds to reducing the number of mix nodes from four to three. – Alpha Bravo Aug 8 '18 at 15:11
• I'm wondering two things, 1) what happens if C goes offline temporarily (say for a day), does that have implications on anonymity? I think the answer can be made to be "no" but am wondering if there are research papers on it. And also 2) if C were to go offline permanently, the message could be lost at B, so are there mix nets that take this into account and ensure better resiliency? – Some Guy Aug 10 '18 at 3:29

It depends on your choice of mixnet, as to whether a mixnet is resilient in the case that C doesn't participate (for whatever reason, including system failures and adversarial behavior by C).

For onion routing, where the ciphertext is of the form

• $enc(pk_A,enc(pk_B,enc(pk_C,enc(pk_D,m))))$,

the mixnet is not resilient, because $enc(pk_C,enc(pk_D,m))$ cannot be decrypted without participation of C.

By comparison, for a re-encryption mixnet, where the ciphertext is of the form

• $enc(pk,m)$,

the mixnet works, since B can skip C and send directly to D. The resulting reduction in anonymity corresponds to reducing the number of mix nodes from four to three.

• In response to crypto.stackexchange.com/questions/61228/… (I don't have enough reputation to comment above): 1) if B waits for C to come online, then there's no loss of anonymity (the proof would embrace the idea that waiting for a computation doesn't harm security), and 2) why would B loss a message? – Alpha Bravo Aug 10 '18 at 8:51
• For 2 I mean that if C goes offline permanently before the message gets to it, then it gets stuck at B. That's a problem if you want to ensure a high level of messages get through (say 99.9% or whatever). I think you could just send the message twice through different routes, but am wondering if there's a paper that has analyzed this problem, because does sending the same message twice have anonymity concerns, and are there other alternatives to get redundancy? – Some Guy Aug 10 '18 at 19:10
• As explained above, using a re-encryption mixnet, it doesn't matter if C goes offline, because it isn't needed. By comparison, it is needed for onion routing. – Alpha Bravo Aug 15 '18 at 10:10
• Regarding "sending the same message twice," this doesn't create any anonymity concerns. Sending a message once, twice, or arbitrarily many times makes no difference, the message is out there, whether it was put out there more than once makes no difference. – Alpha Bravo Aug 15 '18 at 10:11