X hits on this document

PDF document

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

14 views

0 shares

0 downloads

0 comments

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

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

P

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 info
Document views14
Page views14
Page last viewedTue Jan 17 11:36:30 UTC 2017
Pages5
Paragraphs135
Words2417

Comments