Almost Entirely Correct Mixing With Applications to Voting

Abstract:
In order to design an exceptionally efficient mix network, both asymptotically and in real terms, we develop the notion of almost entirely correct mixing, and propose a new mix network that is almost entirely correct. In our new mix, the real cost of proving correctness is orders of magnitude faster than all other mix nets. The trade-off is that our mix only guarantees ``almost entirely correct" mixing. Almost entirely correct mixing means that with very high probability, the mix network processed correctly all but a very small number of inputs. We use a new technique for verifying correctness. This new technique consists of computing the product of a random subset of the inputs to a mix server, then require the mix server to produce a subset of the outputs of equal product. Our new mix net is of particular value for electronic voting, where a guarantee of almost entirely correct mixing will be sufficient to validate the result of all but the closest of elections. But if the result of the election is too close to call, we can fall back on any one of a number of slower proofs of perfect-correctness without having to mix the ballots again.