1.

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.

2.

Note that that mix

_{k }(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 mix_{k }from aborting, is by making his secret shared. This arouses further issues, such as key management.

3.

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.

4.

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.

3

# 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 mix_{i}, . . . , mix_{k}, 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.

3.1

## El-Gamal

## Based

Re-encryption

Mix-nets

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

modulo

p,

and

r

∈_{R }

q

where

q

is

a

a pair (g^{r}, my^{r}), 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 g^{x }= 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 , my^{r+s }and computing (ag^{s}, by^{s}) = (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).

18-2