Note that secure encryption schemes do not hide the length of the plain texts. Since the outputs of E appear publicly on a bulletin board, in order to preserve secrecy, we must require all the cipher-texts to be of the same length.
Note that that mixk (the last mix) generates the final output of the vote. Thus, if he doesn’t like the output he may abort. One way of preventing mixk from aborting, is by making his secret shared. This arouses further issues, such as key management.
It seems like semantic security is enough, assuming the encrypted ballots are publicized only after all the voters have voted. Otherwise, we need a stronger security notion, such as CCA2 security, in order to achieve non-malleability.
The above protocol, as described, is neither verifiable nor robust. In order to achieve these two desired properties, we need to add some ingredients to the protocol. These ingredients will be added following the description of re-encryption mix-nets.
As opposed to a mix phase in a decryption mix-net, whose role is both to mix and to partially decrypt, the role of a mix phase in a re-encryption mix-net is only to mix. Note, however, that a mix which merely scrambles the inputs is not good enough. This is so, since by merely scrambling, the resulting set of ciphertexts does not change, and thus for each resulting ciphertext it is easy to recover the voter associated with it. Thus, an extra operation is needed in order to mix in an unrecoverable way. In a re-encryption mix-net, the extra operation added to each mix phase is a re-encryption operation.
In total, a re-encryption mix-net consists of an initial encryption phase E, several mix phases mixi, . . . , mixk, who mix by scrambling and re-encrypting, and a final decryption phase D. Typically, the encryption scheme used in a re-encryption mix-net is the El-Gamal encryption scheme, which has a nice re-encryption property. In what follows, we describe in more detail an El-Gamal based re-encryption mix-net.
Recall that in the El-Gamal encryption scheme, an encryption of a message m, with respect
to a public key (p, g, y), consists of
a pair (gr, myr), where large prime dividing p
all the operations are done 1, where g is a generator of
the subgroup of elements whose order divides q, and m is in this subgroup. corresponding to (p, g, y) is x such that gx = y(mod p).
The secret key
The El-Gamal encryption scheme has the following nice re-encrypting property: any e n c r y p t e d m e s s a g e ( a , b ) = ( g r , m y r ) c a n b e r e - e n c r y p t e d b y c h o o s i n g a r a n d o m s ∈ R r+s q , myr+s and computing (ags, bys) = (g ). Note that this re-encrypting operation results
with a random ciphertext for the same message m.
We are now ready to define the El-Gamal based re-encryption mix net:
1. An El-Gamal public-key (p, g, y) is generated (in some distributed manner).