Zero knowledge proofs of shuffle with ShuffleProofs.jl

Many remote electronic voting systems use the ElGamal re-encryption mixnet as the foundation of their design, motivated by a number of ways authorities can be held accountable. In particular, zero-knowledge proofs of shuffle as implemented in the Verifiactum library offer an elegant and well-established solution. In ShuffleProofs.jl, I implement a Verificatum compatible verifier and prover for non-interactive zero-knowledge proofs of shuffle, making it more accessible, as I shall demonstrate.

Zero-knowledge proofs (ZKP) are the key for making distributed applications privacy-preserving while keeping participants accountable. Widely used in remote electronic voting system designs and cryptocurrencies, they are still hard to understand, tinker with and thus are accessible only to a tiny minority of skilled cryptographers, dampening the creation of new innovative solutions.

An exciting ZKP application is making a re-encryption mix in the ElGamal cryptosystem accountable for not adding, removing, or modifying ciphertexts. While multiple protocols exist for the purpose, none is as contested as the WikstromTerelius variant implemented in the Verificatum library used to make election systems verifiable in Estonia, Norway, Switzerland and elsewhere. But is far from optimal to tinker with as is implemented in Java. In ShuffleProofs.jl, I implement Verificatum compatible noninteractive zero-knowledge verifier and prover for correct re-encryption, improving its accessibility for non-practitioners.

To demonstrate the usefulness and bring every listener on the same line, I shall discuss a most typical ElGamal voting system used widely as foundations for many designs representing it in only 30 lines of Julia code. After discussing the properties of the system, I will demonstrate how to add verifiability so that even if an adversary controlled the re-encryption mix server, it would not be able to add, remove or modify votes without being noticed.

I shall also demonstrate how we can use the ShuffleProofs.jl to verify Verificatum generated proofs of shuffle, which can help independent auditors to verify real elections on the field. In addition, I shall touch a bit on how one can implement their own verifier as a finite state machine making ShuffleProofs.jl futureproof with all sorts of implementations. Lastly, I will recap and articulate some practices on how zero-knowledge proofs can be implemented in Julia and how they could be made accessible for wider audiences to tinker with.