Let's assume that the secret service can view all transmitted messages and how they are routed, but has no access to anyone's private computer, since otherwise privacy clearly cannot be guaranteed.

There's still no way to mathematically guarantee privacy in any realistic way. One big problem is traffic analysis: the secret service can try to correlate when you send messages with when other people receive messages. This doesn't even require extensive access to the internals of the network, but just the ability to monitor when users send or receive anything. Encryption will disguise the messages themselves, but not who is communicating.

Perhaps the most obvious way to try to foil traffic analysis is by introducing random delays into the system. If the delays are long enough, then it can make traffic analysis much harder, but delays cause severe problems of their own. (Real-time chat becomes impossible, and even e-mail becomes less useful as the delays grow.) And even with delays, making traffic analysis harder and less useful is not the same as making it impossible.

The only guaranteed way to defeat traffic analysis is to communicate all the time. If there's ever a period in which you do not send any messages, then the secret service will know that any messages received during that time either were sent before you stopped communicating or weren't from you. That's already a small information leak. Of course it might not matter in practice, but this is important if we want a mathematical guarantee. It is difficult to model what someone might guess in practice from small leaks, especially when combined with side information, so at a rigorous level all bets are off once information starts to leak.

So this means that if a group of people want to defeat traffic analysis rigorously, then they must all be communicating nonstop, using dummy messages if they don't have anything real to say. This is not generally considered realistic, and I don't know of any large-scale implementation.

Of course nonstop communication is not enough by itself: you also need a system for routing messages indirectly. If nonstop communication isn't an obstacle, then you can guarantee privacy using mix networks, in which a sequence of trusted servers anonymize and randomly permute messages. If all the servers are compromised, then the system becomes insecure, but otherwise it's OK.

In practice, people see constant communication as too costly for whatever benefit it offers. However, mix networks are a good idea nevertheless. The most widespread implementation is Tor. Tor does not provide mathematically guaranteed privacy, and it can be vulnerable to traffic analysis. However, it still provides far more anonymity than the internet does by default.

Of course then there are all sorts of meta-questions. For example, Tor is not very common among internet users. Does it actually attract attention and signal that Tor users are interesting targets for more careful investigation? I've got no idea.

Mathematics certainly plays an important role in addressing privacy concerns, and there's more it could contribute than it currently does. However, the practical constraints are significant, and privacy issues ultimately transcend any specific mathematical model. Sadly, there's no realistic scenario in which internet users could say "Do what you like, because mathematics guarantees our privacy."

Let's assume that the secret service can view all transmitted messages and how they are routed, but has no access to anyone's private computer, since otherwise privacy clearly cannot be guaranteed.

There's still no way to mathematically guarantee privacy in any realistic way. One big problem is traffic analysis: the secret service can try to correlate when you send messages with when other people receive messages (this correlation needs to take place over time; an individual message is certainly not enough by itself, and this can only detect patterns of frequent communication, but that is already a problem). This doesn't even require extensive access to the internals of the network, but just the ability to monitor when users send or receive anything. Encryption will disguise the messages themselves, but not who is communicating.

Perhaps the most obvious way to try to foil traffic analysis is by introducing random delays into the system. If the delays are long enough, then it can make traffic analysis much harder, but delays cause severe problems of their own. (Real-time chat becomes impossible, and even e-mail becomes less useful as the delays grow.) And even with delays, making traffic analysis harder and less useful is not the same as making it impossible.

The only guaranteed way to defeat traffic analysis is to communicate all the time. If there's ever a period in which you do not send any messages, then the secret service will know that any messages received during that time either were sent before you stopped communicating or weren't from you. That's already a small information leak. Of course it might not matter in practice, but this is important if we want a mathematical guarantee. It is difficult to model what someone might guess in practice from small leaks, especially when combined with side information, so at a rigorous level all bets are off once information starts to leak.

So this means that if a group of people want to defeat traffic analysis rigorously, then they must all be communicating nonstop, using dummy messages if they don't have anything real to say. This is not generally considered realistic, and I don't know of any large-scale implementation.

Of course nonstop communication is not enough by itself: you also need a system for routing messages indirectly. If nonstop communication isn't an obstacle, then you can guarantee privacy using mix networks, in which a sequence of trusted servers anonymize and randomly permute messages. If all the servers are compromised, then the system becomes insecure, but otherwise it's OK.

In practice, people see constant communication as too costly for whatever benefit it offers. However, mix networks are a good idea nevertheless. The most widespread implementation is Tor. Tor does not provide mathematically guaranteed privacy, and it can be vulnerable to traffic analysis. However, it still provides far more anonymity than the internet does by default.

Of course then there are all sorts of meta-questions. For example, Tor is not very common among internet users. Does it actually attract attention and signal that Tor users are interesting targets for more careful investigation? I've got no idea.

Mathematics certainly plays an important role in addressing privacy concerns, and there's more it could contribute than it currently does. However, the practical constraints are significant, and privacy issues ultimately transcend any specific mathematical model. Sadly, there's no realistic scenario in which internet users could say "Do what you like, because mathematics guarantees our privacy."