Extending ElectionGuard with Eligibility Verifiability to Prove the Absence of Ballot Stuffing

ElectionGuard is a cryptographic toolkit that makes elections end-to-end verifiable but
leaves eligibility verifiability open. Without this property, ballot stuffing, i.e., the addition
of ballots beyond one per eligible voter, cannot be detected from the election record.
This thesis extends ElectionGuard with eligibility verifiability while preserving its applic­
ability to different voting systems and the simplicity of its verification. Every ballot is
signed under a credential whose key shares are generated independently by several regis­
trars using a multi-signature scheme, so that the registrars can only collectively produce a
usable credential. In addition, the electoral roll is fixed by a perfectly hiding commitment,
which allows designated auditors to inspect the same roll the credentials were issued for
without publishing it. It is proven that, as long as one registrar is honest, the extension is
verifiable under the unforgeability of the multi-signature scheme and the soundness of the
tally proofs. The correctness of the roll itself is established by a statistical audit whose error
probability is bounded by the number of sampled entries. ... mehrSince the published credentials
carry no reference to a voter, everlasting ballot privacy is preserved as long as the registrars
keep the link between voters and credentials secret.
A prototype of ElectionGuard instantiates the construction with MuSig and a Pedersen
commitment. Election records produced by it remain valid for unmodified verifiers, and the
benchmarks show a constant overhead of about one kilobyte and less than one millisecond
per ballot, which amounts to about 4% for the smallest ballot style evaluated and decreases
for larger ones.