Optimistic Mixing for Exit-Polls
P. Golle, S. Zhong, D. Boneh, M. Jakobsson and A. Juels.
We propose a new mix network that is optimized to produce a correct output
very fast when all mix servers execute the mixing protocol correctly (the
usual case). Our mix network only produces an output if no server cheats.
However, in the rare case when one or several mix servers cheat, we
convert the inputs to a format that allows "back-up" mixing. This back-up
mixing can be implemented using any one of a wide array of already
proposed (but slower) mix networks. When all goes well, our mix net is the
fastest, both in real terms and asymptotically, of all those that offer
standard guarantees of privacy and correctness. In practice, this benefit
far outweighs the drawback of a comparatively complex procedure to recover
from cheating. Our new mix is ideally suited to compute almost instantly
the output of electronic elections, whence the name "exit-poll" mixing.