Paper 2023/313

SoK: Metadata-Protecting Communication Systems

Abstract

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, such systems 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 four 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.

Note: Updates for August 2023 version: - Cosmetic touchups and minor corrections Updates for June 2023 version: - We now present functionality and privacy goals by themselves first before introducing the categories of Metadata-Protected Communications Systems (MPCS) that combine these two dimensions. - The MPCS category names were modified to be more precise. - We have divided the properties into three umbrella categories (Protections, Usability, Performance) for better readability, and similarly the Table was reformatted to align with the three property categories. - We provide more precise granularities of horizontal scalability and user disconnection impact. - We discuss metadata-protected messaging as an application of MPCS, and highlight the shortcoming of current MPCS designs in realizing this application.