Paper 2024/1513 Original: eprint.iacr.org/2024/1513 ↗

Depth Optimized Circuits for Lattice Based Voting with Large Candidate Sets

Abstract

Homomorphic encryption has long been used to build voting schemes. Additively homomorphic encryption only allows simple count- ing functions. Lattice-based fully (or somewhat) homomorphic encryp- tion allows more general counting functions, but the required parameters quickly become impractical if used naively. It is safe to leak information during the counting function evaluation, as long as the information could be derived from the public result. To exploit this observation, we de- sign a flexible framework for using somewhat homomorphic encryption for voting that incorporates random input and allows controlled leakage of information. We instantiate the framework using novel circuits with low but significant multiplicative depth exploiting the fact that, in the context of voting, leakage of certain information during homomorphic evaluation can be permitted. We also instantiate the framework with a circuit that uses random input to shuffle without the use of mixnets.