CWI Cryptology Group

Abstract: We describe a variation of the Pret-a-Voter voting protocol that keeps the same ballot layout but borrows and slightly modifies the underlying cryptographic primitives from Punchscan, which is based on bit commitments. By using unconditionally hiding bit commitments, our protocol obtains unconditional privacy. We suggest a way to make cheating on the computational binding bit commitments impossible under assumptions that seem plausible for large-scale elections. Also we show ways to have several races on the Pret-a-Voter ballot, showing that with respect to ballot layout the protocols are almost identical.

Abstract: Verifiable computation of the election result is commonly done by using either homomorphic techniques or mixing techniques. Homomorphic tallying is fast but the encrypted votes are accompanied by a noninteractive zeroknowledge proof, which may be costly. Mix-based tallying allows for simple, constant-size encrypted votes but sequential mixing and final tallying are relatively slow.
In this talk we give a trade-off in which the work for the voting client is minimized (same effort as in mix-based case) and homomorphic tallying it still possible. Thus, compared to Damgaard-Jurik’s result (PKC ’02), we reduce the work even further by eliminating the interval proof needed in their case. By using the protocol for binary conversion of Paillier encrypted values by Schoenmakers-Tuyls (Eurocrypt ’06), the servers can check the validity of any encrypted vote. The transformation (incl. binary conversion) of the encrypted votes into suitably homomorphically encrypted votes can be done during the election, possibly even before acknowledging receipt of the vote to the voter. Once the election is closed, the election result can be produced quickly using homomorphic tallying.