An increasing volume of internet traffic is now encrypted, providing confidentiality of the data sent that protects it from being read by untrusted parties. However, the metadata, such as when a message is sent, to whom the message is addressed, and how often messages are sent can still be observed even when a message is encrypted. At glance it may seem inconspicuous, but metadata can leak detailed information about someone’s behavior such as when they wake up in the morning, if they check social media instead of focus on work, and who their friends are. While metadata privacy in networks has been studied since the 1980s, existing solutions are still far from perfect: they are either resource exhaustive which makes them infeasible to deploy in practice, or they guarantee only weaker notions of privacy which makes them vulnerable to attacks. In this talk, I will give an overview of the field, and present a recent solution that introduces a novel performance-privacy trade-off. I will also outline how this recent solution can be formalized, and how it allows us to reason about what privacy protection the solution provides.