How to Break a Practical MIX and Design a New One

A MIX net takes a list of ciphertexts (c₁, ..., c_N) and outputs a permuted list of the plaintexts (m₁, ..., m_N) without revealing the relationship between (c₁,..., c_N) and (m₁, ...,m_N). This paper first shows that the Jakobsson’s MIX net of Eurocrypt’98, which was believed to be resilient and very efficient, is broken. We next propose an efficient t-resilient MIX net with O(t2) servers in which the cost of each MIX server is O(N). Two new concepts are introduced, existential-honesty and limited-open-verification. They will be useful for distributed computation in general.