# Total anonymity against malicious agents

Suppose we have $$N$$ parties, two of whom are Alice and Bob, while some fraction of the remainder are malicious agents working together. We form a network where each party can pass an encrypted message to another indirectly by routing it through other parties. Alice and Bob know a key secretly, so they can communicate privately because the other parties who look at the message just see noise and pass it on.

But now suppose the malicious agents are really malicious; they can sneak into Bob's home and learn the key, and they also can spy on the entire network to track every movement. Now it becomes easy to unmask Alice. The malicious agents check every message they get with the key, and they'll eventually notice that they always see messages meant for Bob originating with Alice.

So my question is, assuming the agents can acquire as much info through Bob and the network at large as desired, is there a way to modify this protocol such that Alice can't be unmasked? I.e., that the agents will have no way (or a computationally-infeasible way) of guessing Alice is a more likely candidate than any of the other parties? The protocol can be somewhat unreliable if necessary. Obviously it will require some second layer of encryption, but I don't know what to look for.

Dining cryptographer networks are information theoretically secure to the anonymity set size. This is ultimately a traffic analysis question; however, it's very closely related to, and somewhat hard to delineate from, cryptography. In practice a DC-net is, in numerous ways, a lot like a one time pad. Primarily useful in theory and some niche cases. Anonymity is very much dependent on having a large anonymity set size, and DC-nets aren't very scalable.

Constant rate cover traffic is something else for you to read about.

Not just the semantics to be concerned about in this area. Malicious party will delay packets and create a watermark in interpacket arrival timings, then do end to end correlation analysis looking for that actively created pattern. This rapidly explodes into the massive complexity of mix theory. Pynchon gate is the state of the art in mix theory; it uses PIR for message retrieval from nymservers.

Traffic analysis still is largely successful even if all traffic is encrypted and impossible to decrypt. The goal is maintaining -- across all of myriad dimensions -- invariance from the anonymity set. Anonymity is at least typically severely degraded by any variation from the set, other than if there is variation in the form of randomization per hop (i.e. layers of encryption being removed at each hop still has variance of ciphertexts across the anonymity set, but the variance is made statistically independent from itself at each hop by the adding or removing of a layer of encryption).

Interpacket arrival timings are far from the only thing. Need the packets all padded to the same size, or else the packet sizing disparity across streams of packets creates a variance from the anonymity set that can be followed throughout the network.

Traffic analysis is extremely meta. It isn't about the communications, it's about the signals carrying them.

Check out freehaven.net bibliography.

Almost all experts say that Tor is the best bet for anonymity, and that this will not stop being the case any time soon. There is a big disconnection between theory and practice in this area. Plethora mix network designs, and things like DC-nets, are technically much stronger and -- arguably, perhaps anyway -- more sophisticated than Tor is. It's just they have such significant constraints on them, and oftentimes such poor scalability, that in the real world Tor blows them away even though it has major variance in terms of things like stream byte counts for example.

• Thanks. I figured I could beat typical traffic analysis by having every party transmit ~3 junk messages periodically. If a party wanted to transmit a real message, he just replaces one of the junk messages, which would still look like noise. The trade-off is a slower arrival of messages. Dining cryptography seems to be what I was looking for. I found this: dedis.cs.yale.edu/dissent which seems to answer my question – HiddenBabel Nov 16 '19 at 17:27
• "Dummy messages" are what they are called in mix theory, if you want to search for more about that technique. Long term intersection attacks are among the most damning. Say that a global passive adversary knows that messages sent will arrive at their destination within 24 hours. So, every time Bob receives a message, they take a snapshot of everyone who sent a message within the past 24 hours, and assume his interlocutor among them. Over time they look for the commonality between such snapshots, which are individually called crowds. This is done simply by intersecting them together. – Gratis Nov 16 '19 at 19:33
• If you are only concerned with receiver anonymity you can use various Private Information Retrieval algorithms. These are somewhat analogous to radio broadcasts, which can be anonymously received. The most naive example, which is also the only information theoretically secure one to use a single server, is to send all messages sent to the server to all of the clients and then have clients filter out what they don't want. Obviously scales very poorly, but it is quite analogous to a radio broadcast otherwise. It provides no anonymity to senders; anonymity to the anonymity set size for receivers. – Gratis Nov 16 '19 at 19:41