When are three voters enough for privacy properties?

Myrto Arapinis, Véronique Cortier, and Steve Kremer. When are three voters enough for privacy properties?. In Proceedings of the 21st European Symposium on Research in Computer Security (ESORICS'16), pp. 241–260, Lecture Notes in Computer Science 9879, Springer, Heraklion, Crete, September 2016.
doi:10.1007/978-3-319-45741-3_13

Download

[PDF] [PDF (long version)] [HTML] 

Abstract

Protocols for secure electronic voting are of increasing societal importance. Proving rigorously their security is more challenging than many other protocols, which aim at authentication or key exchange. One of the reasons is that they need to be secure for an arbitrary number of malicious voters. In this paper we identify a class of voting protocols for which only a small number of agents needs to be considered: if there is an attack on vote privacy then there is also an attack that involves at most 3 voters (2 honest voters and 1 dishonest voter).
In the case where the protocol allows a voter to cast several votes and counts, e.g., only the last one, we also reduce the number of ballots required for an attack to 10, and under some additional hypotheses, 7 ballots. Our results are formalised and proven in a symbolic model based on the applied pi calculus. We illustrate the applicability of our results on several case studies, including different versions of Helios and Prêt-à-Voter, as well as the JCJ protocol. For some of these protocols we can use the ProVerif tool to provide the first formal proofs of privacy for an unbounded number of voters.

BibTeX

@inproceedings{ACK-esorics16,
  abstract =	 {Protocols for secure electronic voting are of
                  increasing societal importance. Proving rigorously
                  their security is more challenging than many other
                  protocols, which aim at authentication or key
                  exchange. One of the reasons is that they need to be
                  secure for an arbitrary number of malicious
                  voters. In this paper we identify a class of voting
                  protocols for which only a small number of agents
                  needs to be considered: if there is an attack on
                  vote privacy then there is also an attack that
                  involves at most 3 voters (2 honest voters and~1
                  dishonest voter).\par In the case where the protocol
                  allows a voter to cast several votes and counts,
                  e.g., only the last one, we also reduce the number
                  of ballots required for an attack to 10, and under
                  some additional hypotheses, 7 ballots. Our results
                  are formalised and proven in a symbolic model based
                  on the applied pi calculus. We illustrate the
                  applicability of our results on several case
                  studies, including different versions of Helios and
                  Pr\^et-\`a-Voter, as well as the JCJ protocol. For
                  some of these protocols we can use the ProVerif tool
                  to provide the first formal proofs of privacy for an
                  unbounded number of voters.},
  address =	 {Heraklion, Crete},
  author =	 {Arapinis, Myrto and Cortier, V\'eronique and Kremer,
                  Steve},
  booktitle =	 {{P}roceedings of the 21st {E}uropean {S}ymposium on
                  {R}esearch in {C}omputer {S}ecurity (ESORICS'16)},
  DOI =		 {10.1007/978-3-319-45741-3_13},
  editor =	 {Askoxylakis, Ioannis and Ioannidis, Sotiris and
                  Katsikas, Sokratis and Meadows, Catherine},
  month =	 sep,
  pages =	 {241--260},
  publisher =	 {Springer},
  series =	 {Lecture Notes in Computer Science},
  title =	 {When are three voters enough for privacy
                  properties?},
  volume =	 9879,
  year =	 2016,
  acronym =	 {{ESORICS}'16},
  nmonth =	 9,
  url =		 {https://hal.inria.fr/hal-01351398},
}