Karaoke: Distributed Private Messaging Immune to Passive Traffic Analysis

Karaoke is a system for low-latency metadata-private communication. Karaoke provides differential privacy guarantees, and scales better with the number of users than prior such systems (Vuvuzela and Stadium). Karaoke achieves high performance by addressing two challenges faced by prior systems. The first is that differential privacy requires continuously adding noise messages, which leads to high overheads. The second challenge lies in generating sufficient noise in a distributed system where some nodes may be malicious. This talk focuses on how Karaoke solves the first challenge using optimistic indistinguishability: in the common case, Karaoke reveals no information to the adversary, and clients can detect precisely when information may be revealed (thus requiring less noise). Our prototype of Karaoke achieves a latency of 6.8 seconds for 2M users which is 5x to 10x better than Vuvuzela and Stadium.

David Lazar <https://davidlazar.org> is a graduating PhD student at MIT CSAIL, advised by Nickolai Zeldovich. His research in systems security has focused on the problem of metadata privacy: how can two users communicate over the internet without anyone finding out about it? The systems he's built, including Vuvuzela, Alpenhorn, and Karaoke, take an approach based on differential privacy to provide strong metadata protection without sacrificing performance. David is in the process of deploying his work at <https://vuvuzela.io>. David is also an aspiring mountain climber and training for the Chicago Marathon in 2019.