## New cryptographic election protocol with best-known theoretical properties

### Warren D. Smith

We describe a correct, “verifiable,” and “coercion
resistant” election scheme which takes *O*(*N* + *V*)
(highly parallelizable) steps to process *V* votes by *N*
voters. It can handle essentially any underlying
vote-combining method, provided the number of possible distinct
votes is far smaller than the number of voters. In
these theoretical senses (aside from the proviso) the new
voting protocol is optimal.
Juels, Catalano, and Jakobsson had introduced the first
such scheme in 2002, except that it consumed quadratic
work and communication bandwidth and was vulnerable
to two attacks (described here). Our scheme is obtained
from JCJ’s by first modifying it to make it immune to
the two attacks, then adding two ideas to speed it up to
linear time, then finally adding a third idea to reduce the
constant factor in the *O* to the point where it apparently
becomes practically feasible.

The extra security guarantees encapsulated by “coercion
resistance” perhaps are not enough, in a practical sense,
to make our new protocol more desirable than simpler
schemes based on homomorphic encryption and bulletin
boards. That is because our new scheme makes heavy
use of mixnets and cooperative computation on “shared
secrets” carried out by mutually distrustful parties – both
of which cause our communication and/or verification requirements
to be comparatively large.

Finally, we remind the reader that still no secure voting
scheme is presently known that is anywhere close to feasibility,
for handling non-additive election methods that
involve enough bits per vote to allow typical voters to
generate unique votes. The author’s “reweighted range
voting” is an example of such an election method – it
arguably is the best one available for multiwinner elections
– and the cryptographic community so far has not even
considered how to handle such elections.