Almost Entirely Correct Mixing With Applications to Voting
Authors:
D. Boneh and P. Golle.
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 tradeoff 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 perfectcorrectness without having to mix the ballots again.
