cMix: Anonymization by High-Performance Scalable Mixing

cMix is a cryptographic protocol for mix networks that uses precomputations of a group-homomorphic encryption function to avoid all real-time public-key operations by the senders, mix nodes, and receivers. Like other mix network protocols, cMix can enable an anonymity service that accepts inputs from senders and delivers them to an output buffer, in a way that the outputs are unlinkable to the inputs. cMix’s high performance scalable architecture, which results from its unique pre-computation approach, makes it suitable for smartphone-to-smartphone use while maintaining full anonymity sets independently per round. Each sender establishes a shared key separately with each of the mix nodes, which is used as a seed to a cryptographic pseudorandom number generator to generate a sequence of message keys. Each sender encrypts its input to cMix with modular multiplication by message keys. cMix works by replacing the message keys, which are not known in the pre-computation, in real time with a precomputed random value. Our presentation includes a detailed specification of cMix and simulation-based security arguments. We also give performance analysis, both modeled and measured, of our working prototype currently running in the cloud. cMix is the core technology underlying our larger PrivaTegrity system that allows smart devices to carry out a variety of applications anonymously (including sending and receiving chat messages), with little extra bandwidth or battery usage. This paper focuses on cMix.