Efficient Verification of ElGamal Ciphertext Shuffles
Seminar Room 1, Newton Institute
A shuffle is a permutation and rerandomization of a set of ciphertexts. This means that the input ciphertexts and the output ciphertexts contain the same set of plaintexts but in permuted order. Furthermore, due to rerandomization of the ciphertexts the permutation is hidden. Mix-nets often use a sequence of random shuffles performed by different mix-servers to hide the link between senders and plaintexts. A common use is found in voting schemes, where a mix-net uses random shuffles to anonymize a set of encrypted votes.
To protect against malicious mix-servers it is necessary to verify that the shuffles are correct. Otherwise, a bad mix-server could for instance substitute encrypted votes cast by honest voters with encrypted votes for another candidate. Zero-knowledge proofs can be used to guarantee the correctness of a shuffle without revealing the underlying permutation or anything else. By providing such a zero-knowledge proof the mix-server can prove that it has not substituted any ciphertexts or in any other way deviated from the protocol; but at the same time the link between input ciphertexts and output ciphertexts remains secret.
Zero-knowledge proofs for correctness of a shuffle are complicated beasts but we will present a construction that is both efficient and where the required communication is much smaller than the size of the shuffle itself. We have implemented the zero-knowledge proof and will provide concrete performance measurements for verifying shuffles of ElGamal ciphertexts.