Multi-Binomial mixes: A proposal for secure and efficient anonymous communication

Mix systems have long been used to provide communication privacy and among them the Binomial mix is one of the most sophisticated and reliable designs. We propose two new mix designs based on the Binomial mix which can host not one but multiple message selection algorithms. The MBSP mix runs a single and randomly chosen binomial-based algorithm at a time, which selects messages from the mix's single pool. The MBIP mix concurrently runs multiple algorithms and associates each with a separate pool. By comparing the proposed mix designs with the standard CDF-based Binomial mix and multiple other mixes, we show a significant improvement in security and performance: the strongest known (n−1)blending attack and the known passive attack on the Binomial mix are rendered impractical; mixing traffic with different latency/security requirements is made possible; and predicting the behaviour of a mix is made more difficult.