A Practical Privacy Preserving E-Voting

Protocol Using Dynamic Ballots

Orhan Çetinkaya1 and Ali Doğanaksoy2

1
Institute of Applied Mathematics, METU 06531 Ankara, Turkey
[email protected]
2
Department of Mathematics, METU 06531 Ankara, Turkey
[email protected]

Abstract. We describe a practical e-voting protocol which guarantees

e-voting protocol requirements: eligibility, privacy, accuracy, fairness,
receipt-freeness, uncoercibility, robustness and verifiability. Unlike ex-
isting blind signature based protocols, in which the authority blindly
signs ballot or part of ballot, the authority in our protocol blindly signs
voter’s pseudo identity. Hereafter, voter becomes ”Pseudo Voter” and
uses this pseudo identity for further steps. Instead of pre-defined static
ballots, the order of candidates in the ballots are dynamically created
and change for each voter. So, it is called as ”Dynamic Ballot”. Both
dynamic ballot and pseudo voter identity is used in order to possess the
strong property of voter privacy and fairness and to solve blind signature
based protocols’ problems: voter abstention and more voter involvement.

Key words: E-voting, blind signature, anonymous channel, dynamic

ballot, pseudo voter, verifier

1 Introduction
Electronic voting (e-voting) is a challenging topic. The challenge arises primarily
from the need to remove voter’s identity from his cast ballot, in order to sus-
tain voter privacy and to prevent vote-buying and the coercion of voter. This
anonymity requirement makes electronic voting different than other protocols (e-
commerce, e-auction, etc.) and can also make fraud easier, as addition, deletion,
or modification of anonymous ballots is harder to detect. Therefore, e-voting has
been intensively studied in the last decades. Up to now, many electronic vot-
ing protocols have been proposed, and the security as well as the effectiveness
have been improved. However, no complete solution has been found in neither
theoretical nor practical domains. It has been widely recognized that a secure
e-voting protocol should satisfy eligibility, privacy, accuracy, fairness, receipt-
freeness, uncoercibility, robustness and verifiability.
The e-voting protocols could be classified by their approaches and underlying
cryptographic mechanisms as: (a) protocols using blind signatures, (b) protocols
using mix-nets and (c) protocols using homomorphic encryption. The suitability
of each of these types varies with the conditions under which it is to be applied.
2 Orhan Çetinkaya and Ali Doğanaksoy

All these protocols satisfy most of the e-voting requirements; however, the blind
signature based protocols are much more efficient because of their simplicity
and low computation complexity. Therefore, they are more practical. Because of
this fact, most current implementations of e-voting systems are based on blind
signature [23], [24], [25], [26].
The idea behind blind signature protocols is that the voter prepares a ballot
stating for whom he wishes to vote. He then interacts with an authentication
authority who issues a blind signature on the ballot. Informally, this means that
the voter obtains the authority’s digital signature on the ballot, without the
authority learning any information about the contents of the ballot. Finally, all
voters send their ballots to another authority that is responsible for counting
votes. In order to preserve the privacy of voters, this must be done through an
anonymous channel. After all ballots have been collected, votes can be counted
directly.
In general, blind signature based e-voting protocols suffer from voter absten-
tion problem. Some of them solved abstaining voter problem; however, most of
them requires more voter involvement. Obviously, voter involvements in count-
ing stage violates receipt-freeness requirement. These protocols have difficulty in
fulfilling the universal verifiability requirement as voter obtains blindly signed
ballot or a part of ballot.
In this paper, we describe a practical multi-candidate e-voting protocol which
is a complete protocol since it guarantees the wide variety of e-voting protocol
requirements: eligibility, privacy, receipt-freeness, uncoercibility, fairness, robust-
ness, accuracy, universal verifiability and individual verifiability. Unlike existing
blind signature based protocols, in which the authority blindly signs ballot or
part of ballot, the authority in our protocol blindly signs voter’s pseudo iden-
tity generated by voter. Hereafter voter becomes ”Pseudo Voter” and uses this
pseudo identity for further communications with the authorities.
Our contribution in this paper is twofold. One of the key ideas behind our
protocol is for the identity of the voter to remain hidden during the election
process; therefore we call him as ”Pseudo Voter” instead of voter. The other one
is using ”Dynamic Ballot” instead of pre-defined static ballot. Both of them are
mainly used to strengthen voter privacy and to solve abstaining voter problem
and more voter involvement issue. Since pseudo identity is used instead of real
identity, the proposed voting protocol possesses the strong property of privacy
and resists authority corruptions. Even if all authorities are corrupted, voter’s
privacy is still kept hidden. As dynamic ballots are employed, the order of candi-
dates in the ballots change dynamically for each voter, thus, nobody cannot gain
any knowledge about the tally before the counting stage. So, proposed protocol
has strong fairness property.
The rest of the paper is organized as follows: In Section 2, the requirements
of e-voting and related works are explained; in Section 3, the proposed e-voting
protocol is illustrated; in Section 4 security of the protocol is discussed. Finally,
the concluding remark is given in Section 5.
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 3

2 Background

2.1 Requirements

A secure electronic voting system should not allow opportunities for fraud and
not sacrifice voter privacy. Therefore, researchers have described a set of ”core”
requirements that need to be satisfied by any secure electronic voting protocol
[10], [23]. These requirements can be grouped and summarized as following.
Eligibility: Only eligible and authorized voters can vote and each voter can
vote only once.
Privacy: All votes must be secret. No participant other than voter should be
able to determine the value of the vote cast by the voter.
Receipt-Freeness: No voter should be able to convince any other participant
of his vote.
Uncoercibility: Voter cannot be coerced to cast his vote in a particular way.
Fairness: Nothing must affect the voting. No participant can gain any knowl-
edge about the (partial) tally before the counting stage.
Robustness: Reasonably sized coalition of voters or authorities cannot dis-
rupt the voting. Every participant should be convinced that the election tally
accurately represents the ”sum” of the votes cast.
Accuracy: It is not possible for a vote to be altered, a validated vote to be
eliminated from the final tally and an invalid vote to be counted in the final tally
without being detected.
Universal Verifiability: A system is verifiable if anyone can independently
verify that all valid votes have been counted correctly. Any participant or passive
observer can check that the published final tally is really the sum of the votes.
Individual Verifiability: Each eligible voter can verify that his vote was really
counted.
Some of the requirements contradict each other. For example, individual ver-
ifiability contradicts with receipt-freeness and uncoercibility. In order for the
voters to be able to object, in case they notice that their vote has been mis-
counted, a receipt describing the way they voted should be supplied to them.
But the same receipt may be utilized for selling their vote, just by presenting
the receipt to the buyer, or make them subject to coercion, since the coercer will
be able to verify the way they voted.

2.2 Related Work

Several election protocols based on blind signatures have been proposed [8], [9],
[10], [11], [12], [13], [14].
Chaum [21] pioneered the notion of e-voting and then several protocols were
proposed. Later, Chaum [9] proposed a protocol based on the sender untraceable
email system. It has large communication complexity at the registration phase.
Ballot tallying authority can immediately open ballots upon receiving them.
Boyd’s protocol [8], based on multiple key ciphers, is more efficient. There is
4 Orhan Çetinkaya and Ali Doğanaksoy

one administrator carry out elections. However, the voting authority can easily
falsify the ballots.
The first practicable protocol ensuring both the privacy and the fairness is
of Fujioka et al. [10]. The proposed e-voting protocol is capable of solving the
fairness problem by using the bit-commitment function. No one, including the
voting authority, can know the intermediate result of the voting. Thus, it pro-
hibits the fraud by either the voter or the authority. The voter has to participate
in three rounds. Reduced number of rounds appears in the protocol of Juang et
al. [12].
E-voting protocol proposed by Baraani et al. [11] extends [10]. This protocol
includes the candidates in the voting process, each computing a partial tally, in
order to prevent malicious authorities from rejecting ballots or stuffing the ballot
box. The final tally is produced by using a threshold scheme. The model of the
original protocol has been further modified with the addition of a trusted third
party. However, it is emphasized that the fulfillment of all security requirements
strongly relies on the assumption that the trusted authority is functioning as
expected.
Okamoto [14] constructs his proposal based on untappable channel and even
stronger physical assumptions in order to satisfy receipt-freeness. However, voter
should involve more rounds.
Juang et al. [12] proposal introduces scrutineers other than administrator.
The protocol uses threshold cryptosystem to guarantee the fairness among the
candidates campaign. It preserves privacy of the voter against the administrator
and scrutineers. However, it needs more voter involvement. In order to over-
come this problem and to permit voter abstention, Juang et al., [13] extends the
protocol by employing uniquely blind signature.
All voting protocols mentioned above suffer from the ”abstaining voters”
problem except [12], [13]. They assume that every eligible voter should not ab-
stain after the registration phase. The assumption, ”No voter abstains from
voting” is impractical. Since there is the possibility that a voter registers but
does not vote, therefore if the authorities conspire, they can add false vote to
the list when one voter does not vote after the registration phase. Obviously,
both robustness and accuracy requirements are violated with this attack. The
proposed protocol solves this problem.
None of the mentioned voting protocols provide receipt-freeness except [14].
At the end of the election, people who want to know a voter’s token can easily
find it out in the published list. Moreover, all of them only offer individual
verifiability not universal verifiability. The proposed protocol satisfies both of
them.
All mentioned protocols satisfies a subset of the e-voting requirements given
in section 2.1, on the other hand the proposed one describes a complete protocol
which fulfills the whole requirement set.
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 5

2.3 Cryptographic Mechanisms

Bulletin Board (BB): This is a public-broadcast channel with universally ac-
cessible memory. Authorities can write on BB in designated areas via secure
communication, but cannot overwrite or erase existing data; however they could
append data in case of need. Any party (or passive observer) can read informa-
tion from BB. More information can be found in Reiter’s studies [3].
Anonymous Channel: Anonymous channels cannot be traced, in other words,
they are used to assure the anonymity of voters. Anonymous channels can be
realized in a practical way by use of mixnets [1], [2], proxy-based systems [4],
[5], [7] or combination of both [6].
Blind Signatures: The concept of blind signature was introduced by Chaum
[22] as a method to digitally authenticate a message without knowing the con-
tents of the message. The signer cannot drive any association between the signing
process and the signature, which is later made public. In other words, blind sig-
natures are the equivalent of signing carbon paper lined envelopes. Writing a
signature on the outside of such envelope leaves a carbon copy of the signature
on a slip of paper within the envelope. When the envelope is opened, the slip
will show the carbon image of the signature.
Threshold cryptography: The idea of threshold cryptography [19], [20] is to
protect secret information by distributing it among trusted parties. It allows
one to distribute a piece of secret information among several parties in a way
that meets the following requirements: first, no group of corrupt parties (smaller
than a given threshold) can figure out what the secret is, even if they cooperate;
second, when it becomes necessary that the secret information be reconstructed,
a large enough number of parties (a number larger than the above threshold)
can always do it. In the election paradigm, secret key used to authenticate voters
can be distributed among ”n” parties in order to increase robustness.

3 Proposed E-Voting Protocol

3.1 Assumptions
Anonymous Channel: Our protocol does not require untappable channels, but
instead assumes voter access to an anonymous channel while sending his vote
to tallying authorities. Anonymous channels can be realized in a practical way,
while untappable channels require largely unrealistic physical assumptions. We
note that anonymous channels are in fact a minimal requirement for any blind
signature based protocols [8], [9], [10], [11] [12], [13], [14].
Voting Booth: There exists a voting booth, in which only voter casts his
vote by interactively communicating with the authorities. The aim of the voting
booth is just to keep voter alone while he is casting his vote, nothing else. It is
not assumed to guarantee the secrecy of the communication between the voter
and voting authorities. On the other hand, the same assumption with additional
secure communication requirement (i.e. two-way untappable channel) is made
by most of the receipt-free protocols in the literature [15], [14], [18]. Some others
assume that there exists, at least, one-way untappable channel [16], [17].
6 Orhan Çetinkaya and Ali Doğanaksoy

3.2 Definitions

We are now ready to introduce our proposed protocol. We begin by describing

proposed definitions: ”Dynamic Ballot” and ”Pseudo Voter”.
Dynamic Ballot: In usual ballots, the order of candidates in ballot is pre-
determined, so everyone at least authorities know the order of candidates. In
dynamic ballots, the candidate orders change randomly for each ballot.
In usual ballots, if voter has any kind of receipt which explains voter’s cast
order, it shows his intent. On the other hand, in dynamic ballots, voter’s cast
order has contextual meaning. Even if voter shows both his cast and ballot itself,
he could not persuade anybody.
We assume that any ballot contains ”n” number of candidates as B = {c1 , c2 ,
... , cn }. ci represents different candidates for each dynamically generated ballot.
Therefore, counting authorities cannot count intermediate results and further-
more voters do not have to involve more than one round. With dynamic ballots,
any participant or authority including the counter cannot gain any knowledge
about the tally before the counting stage.
Pseudo Voter: In usual voting protocols, voter generally uses his real iden-
tity while communicating with the authorities. If voter obtains a pseudo identity,
he can use it throughout entire communications. While doing this, he can easily
hide his real identity. If someone obtains any information going back and forth
between voter and authorities, voter’s privacy is still kept secret since no real
voter identity is used.
Verifier Authority: It is not a new concept in the literature; however,
we stressed it and actively used it to fulfil the verifiability requirements. We
employ it to keep the verification keys of cast votes in order to satisfy universal
verifiability, fairness and indirectly individual verifiability.

We use the following notations.

ξex (m): m is encrypted with key ex
δdx (m): m is decrypted/signed with key dx
(ex , dx ): (public key, private key) pair (Voter: (ep , dp ), (ev , dv ); Registrar: (er ,
dr ); Authenticator: (ea , da ); Ballot Generator: (eb , db ); Verification Key
Generator: (ek , dk ); Counter: (ec , dc ); Verifier: (ef , df ))
Φ[m]dx ,ey = ξey (δdx (m)) where m is message, dx is sender’s private key and ey
is receiver’s public key
H(m): Hash of m
|x|: List of x
B(m, r): Blinded message m by random r
BS(m): Blindly signed message m

3.3 Overview

The proposed protocol is a multi-authority e-voting protocol. It has 7 actors,

one is voter and the rest are distinct voting authorities. Authorities can be
grouped as Voting Authorities (Registrar, Authenticator, Ballot Generator and
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 7

Verification Key Generator) and Tallying Authorities (Counter and Verifier). An

Authenticator’s Bulletin Board (ABB), on which Authenticator can publish in-
formation, is installed to record H(AuthID+ev ) and status information publicly.
All authorities and their interaction are shown in Fig. 1. A corrupted Authen-
ticator could change voter’s status to allow voter to use more than one vote. In
order to prevent this corruption, we employ ABB. Instead of storing plain AuthID
and ev in ABB, we publish H(AuthID+ev ) in order to be sure that this AuthID
is sent by voter. All communications through ABB is public and can be read by
any party or passive observer. No party can erase any information from ABB, but
Authenticator can append status information to the designated record.

[RegID, B(PAuthID, r)]

Registrar
( er , dr )
[BS(PAuthID, r)] -VoterList

(AuthID, e v )

Voter Authenticator
( ep , dp ), ( ev , dv ) [Ack] ( ea , da )
-RegID -AuthIDList
-PAuthID

(AuthID, e v ) [AuthID, e v
] Status

[Ballot] Status

Ballot Generator
( eb , db ) H(AuthID+ e v )
-BallotList
(Ballot, AuthID, e v
)

[AuthID, e v ]
[Ballot] H(AuthID+ e v )
[VerKey]
(EncBallotChoice) (VerKey)
ABB
Verification Key
Generator
( ek , dk ) H(AuthID+ e v )
-VerKeyList

Counter Verifier
( ec , dc ) ( ef , df )
-EncBallotChoiceList -UsedVerKeyList

Fig. 1. Overview of the proposed protocol

E-voting protocols without using voting booths suffer from bribe and co-
ercion, and sacrifice uncoercibility to establish accuracy for the voting results,
i.e., the voter may be bribed or coerced to vote for a certain candidate. In the
proposed e-voting protocol, we employ the physical voting booth which is only
protected by guards, and is not assumed to guarantee the secrecy of the com-
munication between the voter and voting authorities.
Authorities are explained briefly with the associated information.
Voter: Voter is the active participant of the e-voting process. He has Regis-
tration ID (RegID) and permanent public-private key pair (ep , dp ). He generates
session public-private key pair (ev , dv ) and Pre-Authentication ID (PAuthID).
Registrar: It keeps track of voters who are participating in voting pro-
cess. It gives initial authentication to voter by signing his PAuthID. It does not
make any online communication with other authorities. It keeps and maintains
8 Orhan Çetinkaya and Ali Doğanaksoy

VoterList which consists of voters’ RegIDs, public keys (ep ), status informa-
tion and blindly signed message (BS(PAuthID, r)). Status information contains
whether voter already requested authentication or not. Threshold cryptography
is used to maintain voter information in VoterList. Thus, to authenticate any
voter, certain amount of parties should involve to the process. Hence, Registrar
cannot either impersonate voters who are not committed to the voting or issue
any voter request more than one.
Authenticator: It keeps and maintains AuthIDList which is a list of voters’
AuthIDs with status information. In order to obtain ballot, voter should register
himself to Authenticator. Authenticator populates ABB as soon as getting voter’s
request. It is used to separate ballot generation from authentication. So, Ballot
Generator could not generate extra ballots. It certainly depends on Authentica-
tor. Authenticator should publish any request comes from voter to ABB. ABB is
open to all authorities and observers.
Ballot Generator: It generates dynamic ballot and sends it to both voter
and Verification Key Generator. Voter uses it to cast his vote, Verification Key
Generator uses it to generate unique verification key (VerKey). It keeps and
maintains BallotList which is a list of Ballots.
Verification Key Generator: It generates unique verification key for each
ballot received from Ballot Generator. It keeps and maintains VerKeyList which
is a list of VerKeys with status information and Ballots. When voter requests
verification key for a Ballot, it checks VerKeyList, finds the Ballot and sends
VerKey to voter.
Counter: It collects all encrypted ballot choices in EncBallotChoiceList
which is a list of EncBallotChoices sent by voter. At the end of the election, it
counts all votes by using other lists.
Verifier: It collects all used VerKeys in UsedVerKeyList which is a list of
VerKeys sent by voter. At the end of the election, it provides the list to Counter.
In addition to this, it verifies the election results by checking VerKeys. It works
on behalf of voter in counting stage. So, Counter could not discard and change
any vote.

3.4 Proposed Protocol Steps

The proposed voting protocol takes place in 5 phases: Preparation, Authentica-

tion & Authorization, Vote Preparation, Voting and Tallying.

I. Preparation:

Before the Election Day, all eligible voters should identify and register themselves
to Registration Office. Voter obtains a Registration Card which holds RegID,
permanent public-private key pair (ep , dp ) and public keys of all authorities.
After this Preparation phase is completed, no more voters are allowed to register.
Registration Office sends the last VoterList, which contains the voters’ |RegID,
ep | list, to Registrar and closes the Preparation phase.
.
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 9

II. Authentication & Authorization:

1. Voter identifies himself to the system with his Registration Card and pass-
word by using any voting booth.
2. Voter generates a PAuthID for himself and creates a blinded message with
random bits as B(PAuthID, r). He sends RegID and B(PAuthID, r) to Reg-
istrar as Φ[RegID, B(P AuthID, r)]dp ,er . At this step, voter uses his perma-
nent public-private key pair (ep , dp ).
3. Registrar checks voter’s eligibility from VoterList. If voter is not eligible or
has voted before, protocol terminates. If voter is eligible Registrar signs the
B(PAuthID, r) and obtains blindly signed message BS(PAuthID, r).
4. Registrar updates voter’s status and saves blindly signed message BS(PAuthID,
r) in VoterList. Then, Registrar sends Φ[BS(P AuthID, r)]dr ,ep to voter.
5. After checking Registrar’s signature, voter removes r random bits and ex-
tracts signed PAuthID, (δdr (PAuthID)), which is in fact voter’s AuthID for
the rest of the protocol. After this step, voter becomes a pseudo voter and
uses AuthID for further communications with authorities.
6. Voter generates a session public-private key pair (ev , dv ).
7. Voter sends ξea (AuthID, ev ) to Authenticator.
8. Authenticator saves AuthID into AuthIDList with status information; and
publishes H(AuthID+ev ) with status in ABB.
9. Authenticator sends an acknowledgement to voter, as Φ[Ack]da ,ev .

III. Vote Preparation:

1. Voter sends ξeb (AuthID, ev ) to Ballot Generator.

2. Ballot Generator checks H(AuthID+ev ) from ABB.
3. Ballot Generator sends Φ[AuthID, ev ]db ,ea to Authenticator.
4. Authenticator sends status to Ballot Generator and updates AuthID status.
5. Ballot Generator checks whether ABB is updated correctly by Authenticator.
6. Ballot Generator creates ”Dynamic Ballot” and saves it in BallotList.
7. Ballot Generator sends Φ[Ballot]db ,ev to voter and Φ[Ballot]db ,ek to Verifi-
cation Key Generator.
8. Verification Key Generator creates a unique verification key (VerKey) and
saves |VerKey, Ballot| in VerKeyList.
9. Voter sends ξek (Ballot, AuthID, ev ) to Verification Key Generator.
10. Verification Key Generator checks H(AuthID+ev ) from ABB.
11. Verification Key Generator sends Φ[AuthID, ev ]dk ,ea to Authenticator.
12. Authenticator sends status to Verification Key Generator and updates AuthID
status. Later, Verification Key Generator checks whether ABB is updated cor-
rectly by Authenticator.
13. Verification Key Generator finds the VerKey from the VerKeyList for that
Ballot, and marks that VerKey as used. If there are more than one Ballot
which have same order, then Verification Key Generator selects one of them.
This case strengths privacy.
14. Verification Key Generator sends Φ[V erKey]dk ,ev to voter.
10 Orhan Çetinkaya and Ali Doğanaksoy

IV. Voting:

1. Voter selects his vote which is ballot choice (BallotChoice).

2. Voter encrypts BallotChoice with VerKey and obtains ξV erKey (BallotChoice)
namely EncBallotChoice .
3. Voter sends ξec (EncBallotChoice) to Counter and ξef (VerKey) to Verifier
via anonymous channel.
4. Voter gets a confirmation receipt ”You have voted to the X th positioned
candidate in the list” by using BallotChoice. X represents BallotChoice
and has contextual meaning.
5. Counter saves EncBallotChoice in EncBallotChoiceList.
6. Verifier saves VerKey in UsedVerKeyList.

V. Tallying:

1. Registrar announces how many eligible voters obtained blindly signed AuthID.
2. Ballot Generator announces BallotList, Verification Key Generator an-
nounces VerKeyList, Verifier announces UsedVerKeyList and Counter an-
nounces the EncBallotChoiceList.
3. Counter decrypts EncBallotChoices in EncBallotChoiceList with VerKeys
in UsedVerKeyList (O(n2 )). Counter obtains a list which contains |Verkey,
BallotChoice| pair list. To find out actual votes, each BallotChoice should
be matched with proper Ballot from VerKeyList.
4. Counter matches all |Verkey,BallotChoice| list elements with VerKeyList
(|Ballot,Verkey|), and obtains |Ballot, BallotChoice| pair list which is
in fact the result of the election. Ballot-VerKey and VerKey-BallotChoice
matching is done over VerKey.
5. Verifier verifies the election result against VerKeyList.
6. Ballot Generator checks the election result against BallotList.
7. All announced lists and number of elements in them are verified for equality.
8. Votes are counted according to Vote = Ballot & BallotChoice (for each
VerKey). Thus, BallotChoice has a meaning with the associated Ballot.
9. Counter announces the election results, which can be verified by Verifier.

4 Security Analysis

4.1 Fulfillment of Requirements

In this section, we will illustrate that the proposed e-voting protocol satisfies e-
voting requirements: eligibility, privacy, receipt-freeness, uncoercibility, accuracy
and both individual and universal verifiability.
Eligibility: Actual registration takes place before election, so the eligible
voter list is published before election. On Election Day, voter sends his RegID and
B(AuthID, r) to Registrar, and Registrar checks user privileges and eligibility.
If he is eligible, Registrar blindly signs B(AuthID, r) and changes his status. If
voter tries to obtain another key, it can be easily identified by Registrar. Since
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 11

Threshold cryptography is used while issuing voter’s request, Registrar cannot

be corrupted. Therefore, the proposed e-voting protocol satisfies eligibility.
Privacy: Voter generates AuthID on the fly. Nobody knows AuthID other
than voter. The relation between RegID or any user information with AuthID is
kept in nowhere. Actually, voter becomes pseudo voter after obtaining blindly
signed AuthID from Registrar. Even if all authorities agree with each other,
they could not identify voter’s vote. They may identify the relation between any
AuthID and vote; however, it doesn’t give any information about voter. Bal-
lots are generated dynamically and randomly, independent of voter information.
AuthID is used to verify voter before ballot generation. Voter’s privacy is kept.
Hence, the proposed e-voting protocol satisfies privacy.
Receipt-Freeness: Voter has RegID and permanent public-private key pair
(ep , dp ). These two data don’t give any information about voter’s vote. Voter
gets a confirmation receipt as ”You have voted to the X th positioned candidate in
the list.” X has just contextual meaning. Although proposed protocol provides
receipt, receipt-freeness is fulfilled.
Uncoercibility: By employing voting booths with guards, no one can mon-
itor the voting process of others. Thus, there is no way for the coercer to know
the content of the ballot. So in addition to receipt-freeness, the proposed voting
protocol satisfies uncoercibility.
Fairness: Counting comes after the voting stage is completed so no one
can gain any partial knowledge about the tally before the counting stage; as
a consequence, voting is not affected. Since we are employing dynamic ballots,
even if Counter and Verifier conspire, they could not calculate any partial result.
So, this requirement is achieved.
Robustness: The dishonest voter cannot disrupt the voting, he has just right
over his vote, and he may disrupt his vote only. Even if he sends more than one
votes, in this case, just one of them is counted since VerKey is unique. Depending
on the election policy, these votes can be discarded; thus voter is aware of that
if he sends more than one votes, his vote will be discarded. Since Threshold
cryptography is used in Registrar and Bulletin Board is used in Authenticator.
Even dishonest authorities cannot impersonate abstained voters. Therefore, this
requirement is achieved.
Accuracy: When voter acquires authentication from Authenticator, its in-
formation is written into ABB. After this stage, since the power is distributed
over different authorities, if anybody alters or eliminates any vote or introduces
an invalid vote, it can easily be detected. Hence, accuracy is satisfied.
Universal Verifiability: At the end of the election, before counting, all
authorities publish their lists so any participant or passive observer can check
whether votes are counted correctly or not. Verifier has responsibility to verify
all results and publish them. Therefore, universal verifiability is fulfilled.
Individual Verifiability: There is always a trade-off between individual
verifiability and receipt-freeness and uncoercibility. If individual verifiability is
fully satisfied, achievement of receipt-freeness and uncoercibility fail. In the pro-
posed protocol, system just gives confirmation receipt, nothing more. However,
12 Orhan Çetinkaya and Ali Doğanaksoy

Verifier verifies each vote on behalf of voter. Hence, this requirement is satisfied
by the help of Verifier authority.

4.2 Discussion

If voter is allowed to keep VerKey, then Individual Verifiability achieved directly.

However, in this case receipt-freeness is violated. In most of the real-world elec-
tions, receipt-freeness has more importance than individual verifiability. So, in
our protocol we prefer receipt-freeness instead of direct individual verifiability.
There is a natural trade-off between uncoercibility and more flexibility. Our
protocol can easily be modified to satisfy remote voting requirements. We can
abandon from voting booth depending on the type of election and importance
of uncoercibility to acquire more flexibility.
In counting stage, there is a computational overhead in which Counter de-
crypts EncBallotChoices in EncBallotChoiceList with VerKeys. If there are
N voters, then this process requires O(n2 ) operations, which can be acceptable
since the decryption takes place in counting stage. So, it does not affect the
practicality of voting protocol.

5 Conclusion

We propose a practical multi-candidate complete e-voting protocol by using

dynamic ballots instead of static ballots and pseudo voter identity instead of
normal voter identity. The proposed protocol, which is based on blind signature,
guarantees e-voting protocol requirements: eligibility, privacy, receipt-freeness,
uncoercibility, fairness, robustness, accuracy, universal verifiability and individ-
ual verifiability. Unlike previous blind signature based protocols, in which the
authority blindly signs ballot or part of ballot, the authority in our protocol
blindly signs voter’s pseudo identity generated by voter.
In the proposed protocol, dynamic ballot and pseudo voter identity are used
in order to possess the strong property of voter privacy, to keep voter privacy
even if all authorities are corrupted and to solve abstaining voter and more voter
involvement problems.
As a future work, we are planning to implement the protocol and to use it
in university-wide student elections. Then, our aim is to propose an extended
version of this protocol to use in nation-wide elections.

References

1. J. Furukawa and K. Sako. An efficient scheme for proving a shuffle. In J. Kilian,

editor, CRYPTO ’01, volume 2139 of Lecture Notes in Computer Science, pages
368-387. Springer-Verlag, 2001.
2. A. Neff. A verifiable secret shuffle and its application to e-voting. In P. Samarati,
editor, ACM CCS ’01, pages 116-125. ACM Press, 2001.
 A Practical Privacy Preserving E-Voting Protocol Using Dynamic Ballots 13

3. Reiter, M. The Rampart Toolkit for Building High-Integrity Services. In Theory

and Practice in Distributed Systems, LNCS 938, Springer-Verlag, pp. 99-110, 1995.
4. Anonymizer, http://www.anonymizer.com
5. The Lucent Personalized Web Assistant, http://www.bell-labs.com/project/lpwa/
6. Reiter M., and Rubin A. Crowds, Anonymity for Web Transactions, DIMACS Tech-
nical Report 97-15, April 1997.
7. D., Goldschlag, M., Reed, P., Syverson: Onion Routing for Anonymous and Private
Communications. Communications of the ACM, Vol. 42, No. 2, pp. 39-41, 1999.
8. Boyd, C.: A new multiple key cipher and an improved voting scheme. Advances in
Cryptology - EUROCRYPT ’89, pp. 617-625. Springer-Verlag, 1989.
9. Chaum, D. L.: Elections with unconditionally-secret ballots and disruption equiva-
lent to breaking RSA. EUROCRYPT’88, 1988.
10. Fujioka, A., Okamoto, T. and Ohta, K.: A practical secret voting scheme for large
scale elections, Advaced in Cryptology - AUSCRYPT’92, 1992.
11. A. Baraani, J. Pieprzyk, R. Safavi, A Practical Electronic Voting Protocol Using
Threshold Schemes, Centre for Computer Security Research, Department of Com-
puter Science, University of Wollongong, Australia, May 1994.
12. Juang, W. S. and Lei, C. L.: A secure and practical electronic voting scheme for
real world environment. IEICE Trans. On Fundamentals, E80-A(1), January 1997.
13. Juang, W. S., Lei, C. L. and Liaw, H. T.: A Verifiable Multi-Authority Secret
Election Allowing Abstention from Voting. Computer Journal, pp. 672-682, 2002.
14. Okamoto, T.: Receipt-Free Electronic Voting Schemes for Large Scale Elections.
5th Security Protocols Workshop, LNCS 1163, Springer-Verlag, pp. 125-132, 1997.
15. Benaloh J, Tuinstra D. Receipt-free secret-ballot elections. Proceedings of the 26th
ACM Symposium on the Theory of Computing; ACM, 544-553, 1994.
16. Sako K, Killian J. Receipt-free mix-type voting schemes - a practical solution
to the implementation of voting booth. Proceedings of EUROCRYPT ’95, LNCS;
Springer-Verlag, 921:393-403, 1995.
17. Hirt M, Sako K. Efficient receipt-free voting based on homomorphic encryption.
Proceedings of EUROCRYPT 2000, LNCS; Springer-Verlag, 1807:539-556, 2000.
18. B. Lee, and K. Kim, Receipt-free electronic voting scheme with a tamperresistant
randomizer, ICISC 2002, LNCS 2587, Springer-Verlag, pp. 389-406, 2002.
19. Desmedt, Y. Threshold cryptography. In: Proceedings of the 3rd Symposium on:
State and Progress of Research in Cryptography (W. Wolfowicz, Ed.), February
15-16, pp. 110-122, 1993.
20. Desmedt, Y. Threshold Cryptography. In European Transactions on Telecommu-
nications, 5(4), pp. 449-457, 1994.
21. Chaum, D. L.: Untraceable electronic mail, return addresses, and digital
pseudonyms. Communications of ACM, Vol. 24, pp. 84-88, 1981.
22. Chaum, D. L.: Blind Signatures for Untraceable Payments. CRYPTO ’82, pp. 199-
203, 1982.
23. Cranor, L. and Cytron, R.: Sensus: A Security-Conscious Electronic Polling Sys-
tem for the Internet. Hawaii International Conference on System Sciences, Wailea,
Hawaii, 1997.
24. Davenport, B., Newberger, A. and Woodard, J.: Creating a Secure Digital Voting
Protocol for Campus Elections. Princeton University, 1996.
25. Herschberg, M.: Secure Electronic Voting Using the World Wide Web. Ms Thesis,
MIT, June 1997.
26. Joaquim, R., Zuquete, A. and Ferreira, P.: REVS - A Robust Electronic Voting
System. Proceedings of IADIS International Conference e-Society 2003, Lisbon, Por-
tugal, pp. 95-103, 2003.