6 897: Advanced Topics in Cryptography
Apr 9, 2004
Lecture 18: Mix net Voting Systems
Lecturer: Ron Rivest
ael Tauman Kalai
In the previous lecture, we defined the notion of an electronic voting system, and specified the requirements from such a system. In particular, we required an electronic voting system to be verifiable and robust. Loosely speaking, a voting system is said to be verifiable if any individual can verify that his vote was counted. A voting system is said to be robust if there does not exist any small set of servers that can disrupt the election.
The voting systems that appear in the literature can be roughly categorized into three groups: one based on mix-nets, one based on homomorphic encryptions, and one based on blind signatures. In this lecture we concentrate on mix-net protocols. We describe two types of mix-net protocols: decryption mix nets and re encryption mix nets.
The general structure of mix-nets was illustrated in the previous lecture. They begin with an initial encryption phase E, whose outputs are posted on a bulletin board, in order to achieve verifiability. The initial encryption phase is followed by several mix phases mix1, . . . , mixk. The reason we need several of them is to achieve robustness. In decryption mix-nets, the mix phases mix and partially decrypt, whereas in re-encryption mix-nets, the mix phases mix and re-encrypt. In re-encryption mix-nets a final decryption phase D is added.
A decryption mix-net does not have a final decryption phase. Rather, the initial encryption phase E encrypts its inputs by applying a concatenation of k encryption operations to each input; each mix peels o one of these encryptions by applying a corresponding decryption algorithm; it then mixes all its decrypted inputs by applying a secret random permutation to them. Thus, this scheme has the structure of an onion; E builds the onion, and each mix peels o one layer of the onion.
More specifically, each mix has its own pair of keys. We denote the keys of mixi by ( S K i , P K i ) . m i x i d e c r y p t s i t s i n p u t s u s i n g i t s k e y s ( S K i , P K i ) ; i t t h e n s e c r e t l y p e r m all its decrypted inputs. u t e s
T h e i n i t i a l e n c r y p t i o n E h a s t h e p u b l i c k e y s o f a l l t h e m i x e s ( P K 1 , . . . , P K k ) ; i t e n c r y p t s
e a c h i n p u t b y fi r s t e n c r y p t i n g i t w i t h P K k , t h e n e n c r y p t i n g t h e r e s u l t w i t h P K k 1 e n c r y p t i n g t h e r e s u l t w i t h P K k 2 , a n d s o o n . T h u s , i f w e d e n o t e t h e b a l l o t s , then , . . . , Bn, b y B 1
then for each i = 1, . . . , n,
C i = E ( B i ) = E ( P K 1 . . . E ( P K k 1
, E ( P K k , B i ) ) . . . ) .
There are some issues that need to be addressed: