Cryptology ePrint Archive: Report 2021/520

Optimal Randomized Partial Checking for Decryption Mix Nets

Thomas Haines and Johannes Mueller

Abstract: One of the most important verifiability techniques for mix nets is randomized partial checking (RPC). This method is employed in a number of prominent secure e-voting systems, including Pret a Voter, Civitas, and Scantegrity II, some of which have also been used for real political elections including in Australia.

Unfortunately, it turned out that there exists a significant gap between the intended and the actual verifiability tolerance of the original RPC protocol. This mismatch affects exactly the "Achilles heel" of RPC, namely those application scenarios where manipulating a few messages can swap the final result (e.g., in close runoff elections).

In this work, we propose the first RPC protocol which closes the aforementioned gap for decryption mix nets. We prove that our new RPC protocol achieves an optimal verifiability level, without introducing any disadvantages. Current implementations of RPC for decryption mix nets, in particular for real-world secure e-voting, should adopt our changes to improve their security.

Category / Keywords: cryptographic protocols / Mixnets Verifiability E-voting RPC

Original Publication (in the same form): 26th Australasian Conference on Information Security and Privacy

Date: received 20 Apr 2021

Contact author: thomas haines at ntnu no

Available format(s): PDF | BibTeX Citation

Version: 20210423:122310 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]