Cryptology ePrint Archive: Report 2015/295

Security Analysis of Re-Encryption RPC Mix Nets

Ralf Kuesters and Tomasz Truderung

Abstract: 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{\"o}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.

Category / Keywords: cryptographic protocols / mix nets, e-voting

Original Publication (with minor differences): EuroS&P 2016

Date: received 29 Mar 2015, last revised 17 Dec 2015

Contact author: kuesters at uni-trier de

Available format(s): PDF | BibTeX Citation

Version: 20151217:111351 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]