Safe RPC: Auditing mixnets safely using Randomized Partial Checking

Secure voting systems like PunchScan and Scantegrity use mixnets which are verified using Randomized Partial Checking (RPC). This simple and efficient technique can lead to privacy loss and may, in an extreme case, result in linking all the clear text ballots to the voters who cast them, thus completely destroying the secrecy of all ballots and circumventing the functionality of the mixnet. We suggest a simple technique, Secure RPC (SRPC), that uses RPC in a way that guarantees maximal privacy in all possible cases. We prove that SRPC does not asymptotically reduce the integrity offered by RPC.