X hits on this document

PDF document

Lecture 18: Mix net Voting Systems - page 4 / 5





4 / 5

  • 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 (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.

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







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


Document info
Document views3
Page views3
Page last viewedSun Jan 17 15:40:07 UTC 2016