Security Analysis of Re-Encryption RPC Mix Nets

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 attractive 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, under the assumption that at least one mix server is honest, 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.