Paper 2026/2500

Threshold Post-Quantum E-Voting from Lattice Commitments

Abstract

Lattice-based homomorphic e-voting protocols built on commitments, such as EVOLVE, keep ballots private against all but one authority and the tally verifiable even if all authorities collude, but need every authority to tally. We present T-EVOLVE, in which votes are Shamir-shared over the commitment message space: any t of n authorities that took part in the checking phase complete the tally, privacy holds against t-1 colluding authorities and verifiability against all. The voter proves that her committed shares form a Reed-Solomon codeword whose value at zero is a valid vote; the parity checks cost no communication, and tallying interpolates public column sums without norm growth. Complaints of authorities, including about ciphertexts that do not decrypt, are publicly verifiable given encryption with publicly verifiable opening, which we define and instantiate under LWE. We prove privacy, verifiability, individual verifiability and robustness in the classical random oracle model; the verifiability reduction is not tight and the parameters rest on classical hardness estimates. In our C implementation, a yes/no ballot for four authorities takes 109 KB without signatures, or 147 KB with the computed seed ciphertexts of our instantiation, and an authority aggregates 10^4 ballots in about three minutes per successful tally round on one core.