International Association
for Cryptologic Research

Protecting metadata of communications has been an area of active research since the dining cryptographers problem was introduced by David Chaum in 1988. The Snowden revelations from 2013 resparked research in this direction. Consequently over the last decade we have witnessed a flurry of novel systems designed to protect metadata of users' communications online. However, these systems are often guided by the application they cater to, and leverage different assumptions and design choices to achieve their goal; resulting in a scattered view of the desirable properties, potential vulnerabilities, and limitations of existing metadata-protecting communication systems (MPCS).

In this work we survey 31 systems targeting metadata-protected communications, and present a unified view of the current state of affairs. We provide two different taxonomies for existing MPCS, first into three different categories by the precise type of metadata protections they offer, and next into six families based on the core techniques that underlie them. By contrasting these systems we identify potential vulnerabilities, as well as subtle privacy implications of design choices of existing MPCS. Furthermore, we identify promising avenues for future research for MPCS, and desirable properties that merit more attention.