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.