Cryptology ePrint Archive: Report 2014/341

Formal Analysis of Chaumian Mix Nets with Randomized Partial Checking

Ralf Kuesters and Tomasz Truderung and Andreas Vogt

Abstract: Mix nets with randomized partial checking (RPC mix nets) have been introduced by Jakobsson, Juels, and Rivest as particularly simple and efficient verifiable mix nets. These mix nets have been used in several implementations of prominent e-voting systems to provide vote privacy and verifiability. In RPC mix nets, higher efficiency is traded for a lower level of privacy and verifiability. However, these mix nets have never undergone a rigorous formal analysis. Recently, Kahazei and Wikstroem even pointed out several severe problems in the original proposal and in implementations of RPC mix nets in e-voting systems, both for so-called re-encryption and Chaumian RPC mix nets. While Kahazei and Wikstroem proposed several fixes, the security status of Chaumian RPC mix nets (with the fixes applied) has been left open; re-encryption RPC mix nets, as they suggest, should not be used at all.

In this paper, we provide the first formal security analysis of Chaumian RPC mix nets. We propose security definitions that allow one to measure the level of privacy and verifiability RPC mix nets offer, and then based on these definitions, carry out a rigorous analysis. Altogether, our results show that these mix nets provide a reasonable level of privacy and verifiability, and that they are still an interesting option for the use in e-voting systems.

Category / Keywords: cryptographic protocols / Chaumian Mix Nets, Privacy, Verifiability, Accountability, Formal Verification

Original Publication (with major differences): Security and Privacy 2014

Date: received 15 May 2014

Contact author: ttruderung at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140515:081901 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]