Cryptography Reference
In-Depth Information
5.6 Electronic Voting
Democracy substitutes election by the incompetent many for appointment by
the corrupt few.
George Bernard Shaw (
1856
-
1950
)
, Irish dramatist
— from
Man and Superman
(1903), Maxims: Democracy
Cryptographic protocols can be employed to create scenarios where voters
can electronicallycast their ballots. Of course, secrecyis of paramount im-
portance when casting such ballots over a network. Furthermore, most often
we require authentication, for manyreasons, not onlyincluding the need to
protect legitimate voters, but also to prevent an entityfrom voting more than
once. Another requirement is that each legitimate voter should be able to ver-
ifythat their vote has been cast. One method of starting such a process is to
ensure that each voter has a unique secret bitstring identification number
V
j
for
j
=1
,
2
,...,u
. Furthermore, there needs to be a set of
voting authorities
who
tallythe votes. We will call them
A
1
,A
2
,...,A
w
. There will also be a
central
voting authority
who is trusted byall parties. This will be Trent.
A version of the following was first published in 1997 (see [62]).
A Multiauthority Election Protocol
Background Assumptions
: We will assume that the voters are in Cali-
fornia and voting on whether to recall their governor, a “yes or no” vote. The
voters will communicate through what is called a
bulletin board
that maybe
viewed as a public data base. Each voter has a section of the bulletin board
on which to post messages, and can read the entire board, but no voter can
erase anything. A PKC DSS is assumed to have authenticated the origins of
anypostings to the bulletin board (see Section 4.3 on page 180).
Setup Stage
: Trent chooses primes
p
and
q
, with
p
≡
1(mod
q
), and
α
a
generator of
, as in the DSA setup stage (see page 183). Then he randomly
selects a secret key
a
Z
/q
Z
α
a
(mod
p
) known.
Trent uses the ElGamal encryption scheme described on page 185 to encipher a
message
m
via the choice of a random
b
∈
Z
/q
Z
and makes his public key
k
≡
and computing (
α
b
,mk
b
). This
is then an example of a scheme with the homomorphic property(see page 211),
since if (
α
b
,mk
b
) and (
α
b
,m
k
b
) are the encipherings of
m
and
m
, then
∈
Z
/q
Z
(
α
b
,mk
b
)(
α
b
,m
k
b
)
(
α
b
α
b
,mk
b
mk
b
)
(
α
b
+
b
,mm
k
b
+
b
)(mod
p
)
.
≡
≡
Trent selects a (
t, w
)-threshold scheme (see page 212) to split the secret key
a
among the above-defined
w
authorities in the following fashion. Authority
A
j
has secret share (
j, a
j
) where the
a
j
for
j
=1
,
2
,...,w
are the pieces that
make up the secret key
a
. Trent publishes
α
a
j
(mod
p
) for
j
=1
,
2
,...,w
on
the bulletin board.
Protocol Steps
:
1.
Casting Votes
: Each voter
V
j
chooses a vote that is one of
v
j
∈{−
1
,
1
}
(say, with
−
1 meaning no, and 1 meaning yes). Then the ElGamal cipher is
Search WWH ::
Custom Search