University of Cambridge > > Isaac Newton Institute Seminar Series > Efficient Verification of ElGamal Ciphertext Shuffles

Efficient Verification of ElGamal Ciphertext Shuffles

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity