skip to content

Efficient Verification of ElGamal Ciphertext Shuffles

Tuesday 31st January 2012 - 14:00 to 14:45
INI Seminar Room 1
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.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons