Ne proposed a slightly di erent re-encryption mix-net, also based on El-Gamal. In Ne ’s protocol a re-encryption operation consists in part of taking a ciphertext (a, b) and generating another ciphertext (ac, bc), for a randomly chosen c ∈R q. Note that this operation does change the encrypted message from m to mc. The motivation behind Ne ’s scheme is that he manages to give efficient zero-knowledge proofs, which involve only a linear (in n) number of exponentiations.
There are faster protocols that are not zero-knowledge, such as the one proposed by Boneh and Golle [BG02] and the one proposed by Jacobsson, Juels and Rivest [JJR02]. Both use new techniques to verify correctness. In [BG02], for each mix server, the product of a random subset of its inputs is computed, and the mix server is required to produce a subset of outputs of equal products. In [JJR02], a new technique is used, called randomized partial checking, in which each server provides strong evidence of its correct operation by revealing a pseudo-randomly selected subset of its input/output relations.
An overview Voters vote.
An El-Gamal public key (p, g, y) is produced (in a distributed manner)
The initial encryption phase is performed.
All the mix phases are performed.
Each mix phase produces a proof. The proof includes a non-interactive version of the
Chaum-Pederson proof, obtained by applying the following Fiat-Shamir type step: the challenge is computed by applying some pseudo-random function to the first message and to the content of the bulletin board; the seed to the pseudo-random function is chosen in a distributed manner.
6. All the proofs are checked, and if they are correct, then the decryption phase is performed by applying a threshold decryption. If a proof of mixi fails, then the bad server mixi is skipped and all the mix phases mixi+1, . . . , mixk are redone.
Note that so far we only showed how to prove that one ciphertext is a re-encryption of another ciphertext. We didn’t show how to fully prove that a mix operated correctly.
[BG02] D. Boneh and P. Golle. Almost entirely correct mixing with applications to voting. ACM Conference on Computer and Communications Security 2002: 68-77.
[CP92] D. Chaum and T. P. Pedersen. Wallet Databases with Observers. CRYPTO 1992: 89-105.