A comprehensive analysis of game-based ballot privacy definitions

A comprehensive analysis of game-based ballot privacy definitions. David Bernhard, Veronique Cortier, David Galindo, Olivier Pereira, and Bogdan Warinschi. In Proceedings of the 36th IEEE Symposium on Security and Privacy (S&P'15), pp. 499–516, IEEE Computer Society Press, San Jose, CA, USA, May 2015.

Download

[PDF] [HTML]

Abstract

We critically survey game-based security definitions for the privacy of voting schemes. In addition to known limitations, we unveil several previously unnoticed shortcomings. Surprisingly, the conclusion of our study is that none of the existing definitions is satisfactory: they either provide only weak guarantees, or can be applied only to a limited class of schemes, or both.
Based on our findings, we propose a new game-based definition of privacy which we call BPRIV. We also identify a new property which we call strong consistency, needed to express that tallying does not leak sensitive information. We validate our security notions by showing that BPRIV, strong consistency (and an additional simple property called strong correctness) for a voting scheme imply its security in a simulation-based sense. This result also yields a proof technique for proving entropy-based notions of privacy which offer the strongest security guarantees but are hard to prove directly: first prove your scheme BPRIV, strongly consistent (and correct), then study the entropy-based privacy of the result function of the election, which is a much easier task.

BibTeX

@inproceedings{SP15-privacy,
    author = {David Bernhard and Veronique Cortier and David Galindo and Olivier Pereira and Bogdan Warinschi},
    title = {A comprehensive analysis of game-based ballot privacy definitions},
abstract = {We critically survey game-based security definitions for the privacy of voting
schemes.  In addition to known limitations, we unveil several previously
unnoticed shortcomings.  Surprisingly, the conclusion of
our study is that none of the existing definitions is satisfactory: they either
provide only weak guarantees, or can be applied only to a limited class of
schemes, or both. 
\par
Based on our findings, we propose a new game-based definition of privacy
which we call BPRIV. We also identify a new property which we call {\em strong
consistency}, needed to express that tallying does not leak sensitive
information.  We validate our security notions by showing that BPRIV, strong
consistency (and an additional simple property called strong correctness) for a voting scheme imply its security in
a  simulation-based sense. 
This result also yields a proof technique for proving entropy-based
notions of privacy which offer the strongest security guarantees but are hard
to prove directly: first prove your scheme BPRIV, strongly consistent (and correct),
then study the entropy-based privacy of the result function of the election,
which is a much easier task.},
    year = {2015},
      address =       {San Jose, CA, USA},
  booktitle =     {{P}roceedings of the 36th IEEE Symposium on Security and Privacy (S\&P'15)},
  month =         may,
  doi = {10.1109/SP.2015.37},
  pages     =     {499--516},
  publisher =     {{IEEE} Computer Society Press},
}