Risk-limiting audit optimization with ElectionGuard : zero-knowledge arguments on Chaum-Pedersen multi-commitments

Details

Supervisors

Pereira, Olivier ; Peters, Thomas

Faculty

Ecole polytechnique de Louvain
Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique, à finalité spécialisée
Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

This master's thesis focuses on the development of cryptographic zero-knowledge protocols within the context of ElectionGuard, an open-source voting software created by Microsoft. The primary objective is to shorten the size of the proofs that are used in risk-limiting audits to make them more efficient and practical. Drawing inspiration from the "Bulletproofs" paper by Stanford University, we design cryptographic zero-knowledge protocols that facilitate the efficient generation of logarithmic-sized proofs. In the context of risk-limiting audits, we consider multi-Pedersen commitments that gather the l selections cast in a ballot, v1, ... ,vl, in one group element V = h^r g1^v1 ... gl^vl. We designed three protocols among which the two first protocols prove in a zero-knowledge fashion that the committed votes are valid by proving that they are bits (first protocol) and satisfy the K-selection limit (second protocol), i.e. at most K choices are selected on a ballot. The third protocol allows to do partial opening of votes commitment, that is revealing one of the selections, vj committed inside V. This paper begins with an introduction to zero-knowledge protocols. We then present the mathematical descriptions of our protocols, emphasizing the key design concepts employed. Furthermore, we provide rigorous security guarantees for these protocols, supported by mathematical proofs for their zero-knowledge and soundness properties. Additionally, we predict the theoretical complexities of our protocols. To validate our research, we implemented the three main zero-knowledge protocols, observing successful performance that is aligned with our theoretical predictions. By accomplishing these objectives, our research contributes to the advancement of secure and efficient auditing in the context of voting systems and specifically within the ElectionGuard framework by reaching logarithmic proof sizes.