Rapid mixing and security of Chaum's visual electronic voting
Marcin Gomulkiewicz, Marek Klonowski, Miroslaw Kutylowski
Recently, Chaum proposed an electronic voting scheme
that combines visual cryptography and digital processing. It was
designed so that it can be trusted by voters that distrust electronic
devices.
In this scheme mix-servers are used to guarantee anonymity of the votes
in the counting process. Randomized partial checking of Jakobsson et al.
is used to exclude possibility of forgery by the mix-servers. This leaks
\textit{some} information about the ballots, even if intuitively this
information cannot be used for any efficient attack.
We provide a rigorous stochastic analysis of how much information is
revealed by randomized partial checking in the Chaum's protocol. We
estimate how many mix-servers are necessary for a given security level.
We show that the variation distance between probability distribution of
votes and the uniform distribution is O(1/n) already for a constant
number of mix-servers. This means that a constant number of trustees in
the Chaum's protocol is enough to obtain provable security!
The analysis shows also that certain details of the Chaum's protocol can
be simplified without lowering security level.