Anonymity Trilemma : Strong Anonymity, Low Bandwidth Overhead, Low Latency – Choose Two.

Apr 11, 2018

Download: MP4 Video Size: 141.9MB  
Watch on YouTube

Abstract

Over the last three decades, several anonymous communication (AC) protocols have been proposed towards improving users' privacy over the internet. Among those, the Tor protocol has been particularly successful. Thanks to its low communication latency and low bandwidth overhead, Tor today is employed by millions of users worldwide. Nevertheless, its anonymity is known to be broken in the presence of global adversaries. AC protocols like the dining cryptographers network provide anonymity even in the presence of global adversaries at the expense of bandwidth overhead, while others such as the mixing network designs improve anonymity at the expense of higher latency.
In this work, we investigate the fundamental constraints of anonymous communication (AC) protocols. We analyze the relationship between bandwidth overhead, latency overhead, and sender anonymity or recipient anonymity against the global passive (network-level) adversary. We confirm the trilemma that an AC protocol can only achieve two out of the following three properties: strong anonymity (i.e., anonymity up to a negligible chance), low bandwidth overhead, and low latency overhead.
We further study anonymity against a stronger global passive adversary that can additionally passively compromise some of the AC protocol nodes. For a given number of compromised nodes, we derive necessary constraints between bandwidth and latency overhead whose violation make it impossible for an AC protocol to achieve strong anonymity. We analyze prominent AC protocols from the literature and depict to which extent those satisfy our necessary constraints. Our fundamental necessary constraints offer a guideline not only for improving existing AC systems but also for designing novel AC protocols with non-traditional bandwidth and latency overhead choices.