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
trade-off is that our mix only guarantees ``almost entirely correct"
mixing, i.e it guarantees that the mix network processed correctly all
inputs with high (but not overwhelming) probability. 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
may well be sufficient to announce instantly the result of a large
election. The correctness of the result can later be verified beyond
a doubt using any one of a number of much slower proofs of
perfect-correctness, without having to mix the ballots again.
Reference:
In proceedings of the 9'th ACM conference on Computer and Communications Security (CCS), 2002