Configuration modelling - the Chaum E-voting scheme

Within DIRC, we have made a comprehensive study of the Chaum E-voting scheme [10] which has been designed to support secure and trustworthy electronic voting.

In order to help illustrate the configuration modelling approach, we have selected a real world, complex, socio-technical system to act as a case study. We shall focus upon the domain of ballot based voting, and in particular the Chaum scheme for electronic voting [10]. This scheme is a proposed mechanism to provide a dependable, high security and trustworthy method of electronic voting in national and regional elections or referenda. We have primarily chosen this scheme as our case study because it is a well-documented example of a complex socio-technical system.

The integrity of any voting mechanism is essential to maintaining the electorates trust in the system and the party that it places into power. For this reason, it is not acceptable to sustain failures in the operation of the voting mechanisms. It is highly undesirable to incorporate the new electronic voting components into the overall socio-technical system without first gaining considerable understanding of how the final system will operate and what problems might be encountered. Configuration modelling and analysis provides us with an ideal opportunity to gain some insight into this proposed re-configuration of the system.

In order to understand the motivations behind the Chaum scheme, let us first look at some of the key requirements that underpin it. These high level requirements are as follows:

1) Anonymity - It is essential that the scheme maintains the anonymity of every voter. In order to prevent vote selling, a voter should not be able prove who they voted for. Additionally, to help prevent intimidation of voters, votes should not be traceable back to the voter who cast them and the names of those who voted should never be published.

2) Verifiability - Mechanisms should be present that allow external checking of the voting mechanism to help ensure that votes are counted correctly. To help support this, a voter is provided with a receipt that can be used to (partially) verify vote. A voter can then check that their vote has been counted by finding its entry a published list of counted vote. Partial traceability through the counting process is also provided to allow external auditing of the election.

3) Accuracy - To help ensure a high level of trust in the scheme, it should exhibit a low error rate and features to allow the checking for such errors. This includes checks at various stages to help ensure that once the vote has been cast no one is able to change it and avoid detection. Additionally, partial traceability ensures that no votes are "lost" by the system and that additional, "phantom" votes cannot be inserted.

The Chaum scheme provides an interesting technical solution to the apparently conflicting requirements of a traceable audit trail and maintaining the anonymity of the voters. Due to the limited space available, we are not able to provide a full description of the Chaum scheme. For a more complete description, readers are referred elsewhere [10]. The following sections do however present Strider configuration models that will shed more light on the operation of the Chaum scheme.

A description of some of the key configuration items for the Chaum scheme are shown below. The structural model containg these items is then shown in the diagram.

o Voting option - One of the candidates which can be voted for in an election (can include 'abstain', 'spoil' and 'other')
o Unique identification token - An identification number or card given to the voter upon entry to the polling place which is used to activate a voting machine
o Voting machine - Electrical or mechanical equipment which supports the selection and recording of votes and the printing of receipts
o Receipt - A receipt consists of two transparent layers, both of which have half of the receipt printed onto them (in such away that the whole receipt may be viewed when the two layers are combined and held up to the light). The data on each layer is obscured by random noise to hide the option that was voted for. The random noise is generated such that when the two layers are combined, the noise from each layer cancels each other out, leaving only the voting data
o Random noise - A random pixel pattern used to obscure the text on each layer
o Kept layer - the layer of the receipt retained by a voter
o Discarded layer - the layer of the receipt discarded and destroyed by a voter
o Website - Web page for recording and publishing details of various stages of the trustees work (especially the first and last phases of counting)
o Serial number - Unique number printed on the receipt to identify it. This is used to allow verification via the website. The serial number can either be just the next available consecutive number or a voter specific number (this decision is independent of scheme)
o Unbroken background - A visual security feature present on the receipt which is used by the voter to ensure it's validity
o Public key - A PGP public key used to encrypt a noise removal key for a particular trustee
o Trustee - Person (or machine) charged with the decrypting, mixing, publishing and counting votes
o Private key - A key used to partially remove noise from a layer of the receipt
o Altered receipt layer - A layer of the receipt from which some noise has been removed

<IMG SRC="chaum-structural.gif">

To supplement the description provided by the structural model, a set of 27 processes model fragments have also be derived for the Chaum scheme. A selection of the processes that were identified are as follows:

o Generate serial number - the creation of a serial number which will identify a vote and appear on the voting receipt
o Indicate selection - the selection of one of the voting options by a voter
o Generate receipt - the creation and printing out of the voting receipt
o Visually inspect - the manual, optical checking of both layers of the receipt together to check it's authenticity
o Retaining a single layer - this involves the voter keeping one layer of the receipt for later verification purposes
o Surrender layer - this involves the voter surrendering one layer of the receipt to prevent their choice being determined by an unauthorised individual
o Destroys the surrender half - the destruction of the surrender layer of the receipt
o Published mappings - the act of partially publishing mix mappings on a website
o Votes tallied - the cumulative summation of all votes for the different parties
o External audit - the verification of the counting process by an external independent auditor
o Controlled - the manipulation of one of the officials associated with an election by a political party
o Acts under coercion - the persuasion of voters by a political party, using fair means or foul
o Check website - checking by various interested parties of the voting information published on the website
o Reassures - an attempt by auditors to increase voters confidence in the accuracy and security of the voting scheme

The objective that we will focus on is the ability for a political party to find out who a particular person voted for. As part of the anonymity requirements of the scheme, it should not be possible for anyone (especially member of a political party) to identify the voting option selected by an individual. This is an undesirable objective from the perspective of a free and fair election since its attainment can support intimidation as well as the "sale" of votes by a voter. The purpose of assessing this objective to investigate how the configuration of the Chaum scheme prevents such objectives from being achieved.

During analysis 112 different objective paths were identified, a number of which were of particular interest. These included the identification of the known and acknowledged paths such as the placing of pressure on the voter by the political party to reveal there voting selection (Political party :: acts under coercion :: Voter :: indicate selection) and the controlling of a trustee or returning officer to the extent that they can provide information about the selections made by the voters (Political party :: controlled :: Trustee :: votes tallied :: Vote :: indicate selection) and (Political party :: controlled :: Returning officer :: votes tallied :: Vote :: indicate selection). Various mechanisms are currently available to interrupt these known objective paths and the Chaum scheme competently combats such abuses.

Another particular issue addressed by the Chaum scheme is the provision of a voting receipt for the voter. This is done in such a way as to prevent this receipt being used by any unauthorised personnel to determine the voting option that was selected. The objective path around which this concern is based and which the scheme explicitly blocks was clearly identified during analysis (Political party :: acts under coercion :: Voter :: generate receipt :: Vote :: indicate selection).

The Chaum scheme is less clear on the mechanisms used to prevent poll clerks from determining how a voter has voted, either by observation or questioning, and then reporting this fact back to a political party (Political party :: controlled :: Poll clerk :: destroys the surrendered half :: Voter :: indicate selection). Similarly, the contact that external auditors may have with voters or the tallying process could allow them to determine or imply individual's voting selections (Political party :: controlled :: Auditor :: reassures :: Voter :: indicate selection) and (Political party :: controlled :: Auditor :: external audit :: tally :: votes tallied :: Vote :: indicate selection). Although certain aspects of the Chaum scheme may make such objective paths problematic, there are currently no mechanisms in place that directly address these issues.

An area of particular interest identified during analysis relates to the use of the public web site (used for verifying the decryption and tallying of votes) and the serial numbers generated during the voting process. (Political party :: check website :: Website :: publish mappings :: Serial number :: generate serial number :: Voting machine :: indicate selection). The detection of this path indicates the need to exercise caution when generating such numbers to ensure no traceability is maintained which could allow an interested party to link voters to individual selections.

Finally, the analysis of the specified objective resulted in various suggestions involving controlled trustees manipulating receipt layers in the counting phase of the election. However, due to the encryption and mixing of votes by the Chaum scheme, the individual trustees will either have access to the identities of the original voters, or the votes that they cast, but not both. The implication here is that for such paths, all trustees must be under the control of a political party in order to determine the voting choice of particular voters.

LINKS

E-voting