Alethea: A Provably Secure Random Sample Voting Protocol

David Basin, Saša Radomirović, Lara Schmid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Citations (Scopus)
329 Downloads (Pure)


In random sample voting, only a randomly chosen subset of all eligible voters are selected to vote. This poses new security challenges for the voting protocol used. In particular, one must ensure that the chosen voters were randomly selected while preserving their anonymity. Moreover, the small number of selected voters leaves little room for error and only a few manipulations of the votes may significantly change the outcome. We propose Alethea, the first random sample voting protocol that satisfies end-to-end verifiability and receipt-freeness. Our protocol makes explicit the distinction between human voters and their devices. This allows for more fine-grained statements about the required capabilities and trust assumptions of each agent than is possible in previous work. We define new security properties related to the randomness and anonymity of the sample group and the probability of undetected manipulations. We prove correctness of the protocol and its properties both using traditional paper and pen proofs and with tool support.
Original languageEnglish
Title of host publicationProceedings - IEEE 31st Computer Security Foundations Symposium, CSF 2018
Number of pages15
ISBN (Electronic)9781538666807
ISBN (Print)9781538666814
Publication statusPublished - 9 Aug 2018
Event31st IEEE Computer Security Foundations Symposium, CSF 2018 - Oxford, United Kingdom
Duration: 9 Jul 201812 Jul 2018


Conference31st IEEE Computer Security Foundations Symposium, CSF 2018
Country/TerritoryUnited Kingdom


  • automated-reasoning
  • e-voting
  • formal-verification
  • random-sample-voting

ASJC Scopus subject areas

  • General Engineering

Cite this