Paper 2016/008

cMix: Anonymization by High-Performance Scalable Mixing

David Chaum and Debajyoti Das and Farid Javani and Aniket Kate and Anna Krasnova and Joeri de Ruiter and Alan T. Sherman

Abstract

cMix is the first practical system that can prevent traffic analysis of chat messages at scale. It creates a complete anonymity set every second for all messages sent during the previous second. cMix uniquely requires no public-key operations during the sending of a chat message---neither by the smart phone sending the message, the roughly ten nodes that process each message in sequence, nor the receiving smart phone. A typical number of public-key operations are, however, performed by each node, but only in a precomputataion. This means a savings in hardware of more than an order of magnitude, since computation need not be conducted while all other nodes are waiting. It also allows slower and less reliable cryptographic hardware to be used. cMix is a suite of cryptographic protocols that can replace today's dominant chat systems. It can provide payload secrecy, sender-recipient unlinkability, sender anonymity, and sender authentication for recipients---all secure unless all cMix nodes are compromised. For each batch, the adversary may know all senders and all recipients of traffic in the underlying packet-switched network, yet the adversary cannot link any sender to recipient. cMix provides fast delivery of messages, in both the forward and reverse directions, by having each node perform only a small number of symmetric-key and simple group operations (no modular exponentiations) in real time. Performance benefits include moderately low latency (despite large batch sizes) and efficient utilization of node machines. Senders (e.g., smartphones) perform their part of the cMix real-time protocols with similarly modest amounts of computation, resulting in negligible additional delay, battery, or bandwidth usage. The performance of cMix scales linearly in terms of the number of nodes, users, and messages, Our presentation includes a detailed specification of cMix, simulation-based security arguments, and anonymity analysis. We have implemented cMix on clients on the Android platform, and we give performance analysis, both modelled and measured, of two working prototypes currently running in the cloud.

Note: Revised version of previous manuscript.