cMix: Anonymization byHigh-Performance Scalable Mixing.
David Chaum, Farid Javani, Aniket Kate, Anna Krasnova, Joeri de Ruiter, Alan T. Sherman · IACR Cryptology ePrint Archive · 2016
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, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. CCS ’16 June 16–19, 2013, Seattle, WA, USA c © 2016 ACM. ISBN 123-4567-24-567/08/06. . . $15.00 DOI: 10.475/123_4 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.