# 2. The initial encryption phase E simply encrypts all the ballots B_{1}, . . . , B_{n }by applying the El-Gamal encryption algorithm with the public-key (p, g, y). It then posts all the

resulting ciphertexts (C_{1,0}, . . . , C_{n,0}) on a bulletin board. 3. The i’th mix phase, on input a set of ciphertexts (C_{1,i 1 }

, . . . , C_{n,i }_{1 }

), re-encrypts

each ciphertext and permutes the resulting ciphertexts using a secretly chosen random permutation.

4. The final decryption phase D, given a set of ciphertexts (C_{1,k}, . . . , C_{n,k}), simply de- crypts all the ciphertexts in some distributed manner (in order to achieve robustness).

3.2

# Veri

ability

and

# Robustness

Recall that a voting system is said to be verifiable if all voters can verify that their vote was counted. A voting system is said to be robust is a small set of servers cannot disrupt the election. Note that the above mix-net protocol is neither verifiable nor robust. In order to obtain these two properties several ingredients must be added to the protocol.

In particular, one ingredient which may be added is the requirement that each mix server prove that he has indeed done the correct operation. Namely, each mix_{i }will be

r e q u i r e d t o p r o v e t h a t t h e r e e x i s t s a p e r m u t a t i o n π s u c h t h a t C C_{π j),i 1}, for j = 1, . . . , n. j , i

is a re-encryption of

In what follows we consider the simpler task of merely proving that one ciphertext is a r e - e n c r y p t i o n o f a n o t h e r . L e t c 1 = ( 1 , β 1 ) = ( g t , m 1 y t ) a n d c 2 = ( 2 , β 2 ) = ( g u , m 2 y u ) any two ciphertexts. Note that c_{2 }is a re-encryption of c_{1 }if and only if c_{1 }and c_{2 }are both b e

encryptions of the same message. Consider the tuple

( g , y ,

2 1

,

β 2 β 1

) = ( g , y , g u t

,

m

2

m

1

y

^{u t}).

T h u s , c 2 i s a r e - e n c r y p t i o n o f c 1 i f a n d o n l y i f ( g , y , 2 , β 2 β ) i s a D D H t u p l e , i . e . , t u p l e o f t h e f o r m ( g , y , g r , y r ) , w h i c h i s e q u i v a l e n t t o b e i n g a t u p l e o f t h e f o r m ( g , g x , g r , g r x ) . T h u s , p r o v i n g t h a t c 2 i s a r e - e n c r y p t i o n o f c 1 b o i l s d o w n t o p r o v i n g t h a t ( g , y , g r , y r ) ∈ D D H .

In what follows we describe the Chaum-Pederson protocol [CP92] for proving that a tuple (g, y, w, u) = (g, g^{x}, g^{r}, g^{rx}) is a DDH tuple.

# P

# V

s∈

q

(a, b) = (g^{s}, y^{s})

→

← c

c∈

q

t = s + cr

→

accept if and only if g^{t }= aw^{c }∧ y^{t }= bu^{c }

It is easy to verify that the above protocol is an honest verifier zero-knowledge proof-of- knowledge protocol.

# Remarks:

18-3