X hits on this document

14 views

0 shares

3 / 5

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

resulting ciphertexts (C1,0, . . . , Cn,0) on a bulletin board. 3. The i’th mix phase, on input a set of ciphertexts (C1,i 1

, . . . , Cn,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 (C1,k, . . . , Cn,k), simply de- crypts all the ciphertexts in some distributed manner (in order to achieve robustness).

3.2

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 mixi 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 c2 is a re-encryption of c1 if and only if c1 and c2 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, gx, gr, grx) is a DDH tuple.

# V

s

q

(a, b) = (gs, ys)

c

c

q

t = s + cr

accept if and only if gt = awc yt = buc

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

# Remarks:

18-3

 Document views 14 Page views 14 Page last viewed Tue Jan 17 11:36:30 UTC 2017 Pages 5 Paragraphs 135 Words 2417