How to prove the validity of a complex ballot encryption to the voter and the public

One crucial aspect of any verifiable electronic voting system that uses encryption is the proof that the vote encryption is well-formed, i.e. the proof that the vote encryption encrypts a valid vote accordingly to the race specification. It makes no sense accepting an encrypted vote if, at the end of the election, the vote cannot be included in the tally because it is badly formed.

Proving the validity of a complex vote encryption, without revealing the vote, is a hard problem. This paper first contribution addresses exactly that problem and provides a set of new constructions to create a vote encryption and the corresponding public proof of validity for several types of complex ballots ([kmin,kmax]-out-of-n approval, weighted and ranked ballots). The second contribution is a technique that allows to create a single, constant size, verification code for a ballot containing one or several races of any mix of the race types considered. With this single verification code the voter can verify that her vote was cast-as-intended.

Moreover, our constructions can be tuned for either mix net or homomorphic tallying and support both types of tallying in the same multi-race ballot.