Paper 2015/295

Security Analysis of Re-Encryption RPC Mix Nets

Ralf Kuesters and Tomasz Truderung


Re-Encryption randomized partial checking (RPC) mix nets were introduced by Jakobsson, Juels, and Rivest in 2002 and since then have been employed in prominent modern e-voting systems and in politically binding elections in order to provide verifiable elections in a simple and efficient way. Being one of or even the most used mix nets in practice so far, these mix nets are an interesting and valuable target for rigorous security analysis. In this paper, we carry out the first formal cryptographic analysis of re-encryption RPC mix nets. We show that these mix nets, with fixes recently proposed by Khazaei and Wikström, provide a good level of verifiability, and more precisely, accountability: cheating mix servers, who try to manipulate the election outcome, are caught with high probability. Moreover, we show that all attacks that would break the privacy of voters' inputs are caught with a probability of at least $1/4$. In many cases, for example, when penalties are severe or reputation can be lost, adversaries might not be willing to take this risk, and hence, would behave in a way that avoids this risk. Now, for such a class of ``risk-avoiding'' adversaries, we show that re-encryption RPC mix nets provide a good level of privacy, even if only one mix server is honest.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. EuroS&P 2016
mix netse-voting
Contact author(s)
kuesters @ uni-trier de
2015-12-17: revised
2015-04-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ralf Kuesters and Tomasz Truderung},
      title = {Security Analysis of Re-Encryption {RPC} Mix Nets},
      howpublished = {Cryptology ePrint Archive, Paper 2015/295},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.