Return Codes from Lattice Assumptions

Abstract

Vi presenterer en fremgangsmåte for å lage returkoder for et gitter-basert elektronisk valgsystem. For et valgsystem med fire kontrollkomponenter og kommunikasjon i to runder oppnår protokollen vår en total kommunikasjonsstørrelse på 2.3 MB per velger, og bruker under 1 s for utregningene.

Den elektroniske valgprotokollen til Swiss Post, som Sveits planlegger å bruke i valg og folkeavstemninger, antar en upålitelig valgserver og tilbyr individuell verifiserbarhet, universell verifiserbarhet og hemmelighold av stemmesedler. Protokollen bruker sikkerhets-antagelser basert på diskret logaritme, og disse antagelsene vil kunne trues av kvantedatamaskiner om et tiår eller to. Dette er ikke bare en fremtidig trussel mot integritet, men også en trussel mot langvarig hemmelighold av stemmesedler avgitt i dag.

Vi presenterer en gitter-basert valgprotokoll passende for valg med returkoder, og utvider med dette Aranha et al. sitt rammeverk fra 2021 og 2022. Protokollen fra 2021 inkluderer returkoder, men antar en pålitelig valgserver, mens protokollen fra 2022 antar en upålitelig valgserver, men inkluderer ikke returkoder. Våre returkoder kan sammen med miks- og dekrypterings-protokollene til Aranha et al. brukes til å lage et post-kvante-sikkert kryptografisk valgsystem som er kompatibelt med tillitsantagelsene til den elektroniske valgprotokollen til Swiss Post.

We present an approach for creating return codes for lattice-based electronic voting. For a voting system with four control components and two-round communications, our scheme results in a total of 2.3 MB of communication per voter, taking less than 1 s of computation.

The Swiss Post electronic voting protocol, planned for use in elections and referendums in Switzerland, assumes an untrustworthy voting server and offers individual verifiability, universal verifiability, and privacy. The protocol is based on discrete log-type assumptions, whose security could be broken by quantum computers in a decade or two. This is not only a future threat against integrity, but also a threat against privacy of votes cast today.

Together with the shuffle and the decryption protocols by Aranha et al., the return codes presented can be used to build a post-quantum secure cryptographic voting scheme compatible with the trust assumptions of the Swiss Post electronic voting protocol. While the protocol by Aranha et al. from 2021 includes return codes, but assumes a trustworthy voting server, the protocol by Aranha et al. from 2022 allows for an untrustworthy voting server but does not include return codes. We fill this gap.