Paper 2014/341

Formal Analysis of Chaumian Mix Nets with Randomized Partial Checking

Ralf Kuesters, Tomasz Truderung, and Andreas Vogt


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Security and Privacy 2014
Chaumian Mix NetsPrivacyVerifiabilityAccountabilityFormal Verification
Contact author(s)
ttruderung @ gmail com
2014-05-15: received
Short URL
Creative Commons Attribution


      author = {Ralf Kuesters and Tomasz Truderung and Andreas Vogt},
      title = {Formal Analysis of Chaumian Mix Nets with Randomized Partial Checking},
      howpublished = {Cryptology ePrint Archive, Paper 2014/341},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.