Lecture 18: Mixnet Voting Systems
Yael Tauman Kalai · 2004
In the previous lecture, we defined the notion of an electronic voting system, and specified the requirements from such a system. In particular, we required an electronic voting system to be verifiable and robust. Loosely speaking, a voting system is said to be verifiable if any individual can verify that his vote was counted. A voting system is said to be robust if there does not exist any small set of servers that can disrupt the election. The voting systems that appear in the literature can be roughly categorized into three groups: one based on mixnets, one based on homomorphic encryptions, and one based on blind signatures. In this lecture we concentrate on mixnet protocols. We describe two types of mixnet protocols: decryption mixnets and reencryption mixnets. The general structure of mixnets was illustrated in the previous lecture. They begin with an initial encryption phase E, whose outputs are posted on a bulletin board, in order to achieve verifiability. The initial encryption phase is followed by several mix phases mix1, . . . , mixk . The reason we need several of them is to achieve robustness. In decryption mixnets, the mix phases mix and partially decrypt, whereas in reencryption mixnets, the mix phases mix and reencrypt. In reencryption mixnets a final decryption phase D is added.