SoK: Verifiability Notions for E-Voting Protocols

SoK: Verifiability Notions for E-Voting Protocols. Véronique Cortier, David Galindo, Ralf Küsters, Johannes Müller, and Tomasz Truderung. In Proceedings of the 36th IEEE Symposium on Security and Privacy (S&P'16), IEEE Computer Society Press, San Jose, CA, USA, May 2016.

Download

[PDF] [long version] [HTML]

Abstract

There have been intensive research efforts in the last two decades or so to design and deploy electronic voting (e-voting) protocols and systems which allow voters and/or external auditors to check that the votes were counted correctly. This security property, which not least was motivated by numerous problems in even national elections, is called verifiability. It is meant to defend against voting devices and servers that have programming errors or are outright malicious. In order to properly evaluate and analyze e-voting protocols and systems w.r.t. verifiability, one fundamental challenge has been to formally capture the meaning of this security property. While the first formal definitions of verifiability were devised in the late 1980s already, new verifiability definitions are still being proposed. The definitions differ in various aspects, including the classes of protocols they capture and even their formulations of the very core of the meaning of verifiability. This is an unsatisfying state of affairs, leaving the research on the verifiability of e-voting protocols and systems in a fuzzy state.
In this paper, we review all formal definitions of verifiability proposed in the literature and cast them in a framework proposed by Küsters, Truderung, and Vogt (the KTV framework), yielding a uniform treatment of verifiability. This enables us to provide a detailed comparison of the various definitions of verifiability from the literature. We thoroughly discuss advantages and disadvantages, and point to limitations and problems. Finally, from these discussions and based on the KTV framework, we distill a general definition of verifiability, which can be instantiated in various ways, and provide precise guidelines for its instantiation. The concepts for verifiability we develop should be widely applicable also beyond the framework used here. Altogether, our work offers a well-founded reference point for future research on the verifiability of e-voting systems.

BibTeX

@inproceedings{SP16-verifiability,
    author = {V\'eronique Cortier and David Galindo and Ralf K\"usters and Johannes M\"uller and Tomasz Truderung},
    title = {SoK: Verifiability Notions for E-Voting Protocols},
abstract = {There have been intensive research efforts in the last two decades
  or so to design and deploy electronic voting (e-voting)
  protocols and systems which allow voters and/or
  external auditors to check that the votes were counted
  correctly. This security property, which not least was
    motivated by numerous problems in even national elections,
   is called \emph{verifiability}. It is meant to defend
  against voting devices and servers that have programming errors or
  are outright malicious. In order to properly evaluate and analyze
  e-voting protocols and systems
  w.r.t.~verifiability, one fundamental challenge has been to formally
  capture the meaning of this security property. While the first
  formal definitions of verifiability were devised in the late 1980s
  already, new verifiability definitions are still being proposed. The
  definitions differ in various aspects, including the classes of
  protocols they capture and even their formulations of the very core
  of the meaning of verifiability. This is an unsatisfying state of
  affairs, leaving the research on the verifiability of e-voting protocols and systems
  in a fuzzy state.
\par
  In this paper, we review all formal definitions of verifiability
  proposed in the literature and cast them in a framework proposed by K{\"u}sters,
  Truderung, and Vogt (the KTV framework), yielding a uniform
  treatment of verifiability. This enables us to provide a detailed
  comparison of the various definitions of verifiability from the
  literature. We thoroughly discuss advantages and disadvantages, and
  point to limitations and problems.  Finally, from these discussions
  and based on the KTV framework, we
  distill a general definition of verifiability, which can be
  instantiated in various ways, and provide precise guidelines for its
  instantiation. The concepts for verifiability we develop should be
  widely applicable also beyond the framework used here. Altogether,
  our work offers a well-founded reference point for future research
  on the verifiability of e-voting systems.},
    year = {2016},
      address =       {San Jose, CA, USA},
  booktitle =     {{P}roceedings of the 36th IEEE Symposium on Security and Privacy (S\&P'16)},
  month =         may,
  OPTpages     =     {},
  OPTnote = {},
  publisher =     {{IEEE} Computer Society Press},
  doi = {10.1109/SP.2016.52},
}