Alethea: A provably secure random sample voting protocol

David Basin*, Sasa Radomirovic, Lara Schmid

*Corresponding author for this work

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

20 Citations (Scopus)
40 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 publication2018 IEEE 31st Computer Security Foundations Symposium (CSF)
Number of pages15
ISBN (Electronic)9781538666807
Publication statusPublished - 9 Aug 2018
Event31st IEEE Computer Security Foundations Symposium 2018 - Oxford, United Kingdom
Duration: 9 Jul 201812 Jul 2018

Publication series

NameIEEE Computer Security Foundations Symposium
ISSN (Print)1940-1434


Conference31st IEEE Computer Security Foundations Symposium 2018
Abbreviated titleCSF 2018
Country/TerritoryUnited Kingdom


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

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Alethea: A provably secure random sample voting protocol'. Together they form a unique fingerprint.

Cite this