1.

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 (a

^{c}, b^{c}), for a randomly chosen c ∈_{R }_{q}. Note that this operation does change the encrypted message from m to m^{c}. 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.2.

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.

3.3 1.

An overview Voters vote.

of

an

El-Gamal

based

Re-encryption

Mix-net

2.

An El-Gamal public key (p, g, y) is produced (in a distributed manner)

3.

The initial encryption phase is performed.

4.

All the mix phases are performed.

5.

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 mix_{i }fails, then the bad server mix_{i }is skipped and all the mix phases mix_{i+1}, . . . , mix_{k }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.

# References

[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.

18-4