Practical Everlasting Privacy

Myrto Arapinis, Véronique Cortier, Steve Kremer, and Mark D. Ryan. Practical Everlasting Privacy. In Proceedings of the 2nd Conference on Principles of Security and Trust (POST'13), pp. 21–40, Lecture Notes in Computer Science 7796, Springer, Rome, Italy, March 2013.
doi:10.1007/978-3-642-36830-1_2

Download

[PDF] [HTML] 

Abstract

Will my vote remain secret in 20 years? This is a natural question in the context of electronic voting, where encrypted votes may be published on a bulletin board for verifiability purposes, but the strength of the encryption is eroded with the passage of time. The question has been addressed through a property referred to as everlasting privacy. Perfect everlasting privacy may be difficult or even impossible to achieve, in particular in remote electronic elections. In this paper, we propose a definition of practical everlasting privacy. The key idea is that in the future, an attacker will be more powerful in terms of computation (he may be able to break the cryptography) but less powerful in terms of the data he can operate on (transactions between a vote client and the vote server may not have been stored).
We formalize our definition of everlasting privacy in the applied-pi calculus. We provide the means to characterize what an attacker can break in the future in several cases. In particular, we model this for perfectly hiding and computationally binding primitives (or the converse), such as Pedersen commitments, and for symmetric and asymmetric encryption primitives. We adapt existing tools, in order to allow us to automatically prove everlasting privacy. As an illustration, we show that several variants of Helios (including Helios with Pedersen commitments) and a protocol by Moran and Naor achieve practical everlasting privacy, using the ProVerif and the AKiSs tools.

BibTeX

@inproceedings{ACKR-post13,
  abstract =      {Will my vote remain secret in 20 years? This is a
                  natural question in the context of electronic
                  voting, where encrypted votes may be published on a
                  bulletin board for verifiability purposes, but the
                  strength of the encryption is eroded with the
                  passage of time. The question has been addressed
                  through a property referred to as everlasting
                  privacy. Perfect everlasting privacy may be
                  difficult or even impossible to achieve, in
                  particular in remote electronic elections. In this
                  paper, we propose a definition of practical
                  everlasting privacy. The key idea is that in the
                  future, an attacker will be more powerful in terms
                  of computation (he may be able to break the
                  cryptography) but less powerful in terms of the data
                  he can operate on (transactions between a vote
                  client and the vote server may not have been
                  stored).\par  We formalize our definition of everlasting
                  privacy in the applied-pi calculus. We provide the
                  means to characterize what an attacker can break in
                  the future in several cases. In particular, we model
                  this for perfectly hiding and computationally
                  binding primitives (or the converse), such as
                  Pedersen commitments, and for symmetric and
                  asymmetric encryption primitives. We adapt existing
                  tools, in order to allow us to automatically prove
                  everlasting privacy. As an illustration, we show
                  that several variants of Helios (including Helios
                  with Pedersen commitments) and a protocol by Moran
                  and Naor achieve practical everlasting privacy,
                  using the ProVerif and the AKiSs tools.},
  address =       {Rome, Italy},
  author =	  {Arapinis, Myrto and Cortier, V{\'e}ronique and Kremer, Steve and Ryan, Mark D.},
  booktitle =     {{P}roceedings of the 2nd {C}onference on {P}rinciples of {S}ecurity and {T}rust (POST'13)},
  DOI =           {10.1007/978-3-642-36830-1_2},
  editor =        {Basin, David and Mitchell, John},
  month =         mar,
  pages =         {21-40},
  publisher =     {Springer},
  series =        {Lecture Notes in Computer Science},
  title =         {{P}ractical {E}verlasting {P}rivacy},
  volume =        {7796},
  year =          {2013},
  acronym =       {{POST}'13},
  nmonth =        {3},
  url =           {https://members.loria.fr/skremer/files/Papers/ACKR-post13.pdf},
}