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.