A Voting Process Design.
Introduction.
Most people would agree that elections should be fair and free.
Some people have doubts about the architecture and implementations of the Voting Process Systems that are currently being used, and point to weaknesses that might be exploited to manipulate the results of elections.
Those people might be interested in the Voting PS that is presented in this document.
The main design principle is that objects like machines or stacks of paper can not be trusted if the individual people or organizations that are managing the objects can not be trusted.
Trust is something that eventually depends on trusting people, and trusting arbitrary individuals or organizations is impossible for most of us.
The best way that I know of to increase the level of trust in a PS, is the introduction of redundancy, with truly independent subsystems performing the same tasks, and comparing the results of their actions.
The proposed Voting PS is relying on this social networking architecture.
The result is a design that makes it extremely hard for anybody to insert ghost votes, ignore legitimate votes, change the contents of a vote, or try to trace back a vote to an individual voter without being noticed.
After the votes have been counted, every individual Voter is able to check that its personal vote has been processed correctly, and any person is able to check that all votes were legitimate and all votes have been counted.
Implementations are not depending on specific types of technical components (it is primarily a social PS), but in this presentation we will assume the use of computers that are (securely) linked to each other by the Internet as an illustration of a practical, cheap, reliable, user friendly and easy to build system.
Except for the platforms used by the Voter (which will simply never be trusted), all systems involved will be based on open source software (including the OS!), and be verifiable before, during, and after the voting process.
Process Systems.
In this presentation the concept of Process System (PS) is being used as:
A Process System is the combination of the human being or organization of human beings and the tools it uses to perform a specific task in the global voting PS, or a set of related PS's that are being referred to as subsystems.
There are various types of PS's, and per type there are various numbers of individual PS's.
Each individual PS has a human being as its operational manager, called SysAdm.
The special PS called PSreg publishes relevant information about every PS and its SysAdm.
Clusters.
PS's of a specific type are being clustered in one of the two ways shown in figure 1.
Figure 1: clusters
Every PS will report unexpected behavior of other PS's to the PSreg immediately (see TD1 and TD2).
Except for two types of PS's (Anon1 and Anon2, discussed below), all PS's maintain a log of the client-server transactions, without recording the order of processing.
A Cluster is a PS, and all static clusters are documented in PSreg.
Certificates.
A significant part of the communication between PS's and of the recording of individual steps in the process uses statements that are signed by PS's, for example by using public key encryption.
These signed statements are called Certificates.
Certificates that do not relate to an individual voting process sign both the statement and a time stamp; we will refer to them as Tcert(signers).
Since records of individual voting processes should not contain information about time or order of processing, their certificates do not include a time stamp; we will refer to them as Cert(signers).
Roles.
The individual Voter is allowed to play its role by the combination of Auth and Obs.
Voter does not participate anonymously (no PS does) in the voting process, but the contents of its Vote can not be traced back to Voter; its Vote is anonymous.
In our example, the location of the Voter is irrelevant; it would probably prefer to use its PC at home (safest and most convenient), but if polling stations would be needed for people that would choose to vote out there, these polling stations would become little more than internet cafe's.
The community of all individual Voters is the Owner of the overall voting process and its global Voting PS.
Owner delegates the operational management of the PS to Auth.
Auth is a person or organization (e.g. government, administration) that is appointed by Owner, and takes full responsibility for the voting process.
Owner and Auth agree on Obs, that audits the actions of Auth, and reports to both Owner and the rest of the world.
Obs would preferably be an organization that represents both Voters and external PS's.
When an individual Voter feels like it, it should be able to become part of Obs.
SysAdm is a subcontractor of Auth, that is certified by both Auth and Obs.
Anybody can offer to contribute a PS of the types that are typical for personal configurations (explained below), and be its SysAdm.
Both the contributed PS and its SysAdm will have to meet specifications though, that have been formulated by Auth and Obs.
SysAdm builds and maintains its system in a standardized way.
The standards are public domain, and where practical (e.g. software components) so are specific components.
If both Auth and Obs accept the contribution to the global Voting PS, it will be registered in PSreg.
SysAdm allows others to inspect its system at any time on the request of both Obs and Auth, and the inspection reports are published in PSreg.
Personal Configurations.
Figure 2 shows the configuration that a Voter faces during the voting process.
The part marked "personal configuration" (Config), is being assembled by Voter.
Figure 2: configurations
Voter starts its individual voting process by specifying its Config.
This individual Config needs approval from both Auth and Obs, right before Voter actually votes.
Optionally, Obs and Auth together may offer a random Config as a suggestion, that Voter can accept (ease of use) or reject/improve.
So every Voter chooses the machines (actually: people) that it trusts, can create one if it wants to, but both Auth and Obs have to agree with the resulting Config.
Types of PS's.
The function of the various PS's in figure 2 will be discussed in detail below; here we will present an overview:
| Login | : | verifies Voter Id |
| Reg | : | records individual process steps per Voter |
| Anon1 | : | breaks the link between Voter and Vote |
| Uniq | : | guarantees VoteNr uniqueness; could be integrated with CUniq |
| Anon2 | : | could be integrated in Anon1 |
| Res | : | records individual process steps per Vote |
The centralized PS's CReg, Cuniq, and CRes, consolidate the records of the individual Reg, Uniq, and Res PS's during the voting process.
Each individual PS (cluster) must be approved of by various other PS's:
| PS | Approved by |
|---|
| Voter | Voter, Obs, Auth |
| Obs | Obs, Auth |
| Auth | Auth, Obs |
| PSreg | Auth, Obs |
| Uniq | Voter, Auth, Obs |
| Login | Voter, Auth, Obs |
| Reg | Voter, Auth, Obs |
| Anon1 | Voter, Auth, Obs |
| Anon2 | Voter, Auth, Obs |
| Res | Voter, Auth, Obs |
| CReg | Obs, Auth |
| CUniq | Obs, Auth |
| CRes | Obs, Auth |
Preparation Phase.
The preparations start with the setup of the global Config, and the compilation of the Voter Register.
These actions primarily belong within the Auth PS, obviously combined with the efforts of the SysAdm's.
After a while, Obs starts its verification activities.
Verification of the Voter Register is the most challenging task here.
The problem is that Auth will usually be able to to create arbitrary numbers of ghost Voters by giving a single person multiple identities.
At the same time, the results of the vote may have serious implications for many people within the Auth organization.
This clearly visible conflict of interests makes the role of Obs in this phase of the voting process rather crucial.
Obs should be able to check the physical, legal, and unique existence aspects of human beings without depending on information that can exclusively be provided by Auth, and it should definitely not trust internal checks and balances within the Auth organization itself.
Obs should also be very sensitive to the roles of individual people within its own organization that are also a part of Auth.
Note that these aspects of the Voting PS are not specific to the architectural proposals presented in this document.
Voting Phase (per individual Voter).
See figure 3 for an illustration of the steps in the individual voting process:
Figure 3: the individual voting process
1: Voter chooses its Config
2: Voter identifies itself and presents its Config at Login
3: Login checks VoterId (see TD3), creating VoterIdCert: VoterId signed by Login.
4: Reg receives VoterIdCert and Config from Login, and passes them to CReg
4a: CReg receives VoterIdCert and Config, refusing it if Voter had already logged in
5: CReg checks Config at Auth and Obs
6: CReg receives ConfigCerts: Config signed by Auth or Obs, and passes them to Reg
7: Login receives VoterCerts: VoterIdCerts+ConfigCerts signed by CReg
8: Voter receives LoginCerts: VoterCerts signed by Login
9: Voter generates VoteNrProps: a list of random numbers
10: Anon1 receives VoteNrProps + LoginCerts from Voter
11: Anon1 checks LoginCerts
12: Uniq receives VoteNrProps from Anon1, and passes them to CUniq
13: CUniq selects a VoteNr that is still unused, and signs it, giving VoteNrCert1
14: CUniq passes VoteNrCert1 to Uniq, which passes it to Anon1
15: Anon1 tells Reg that Voter has received a VoteNr; Reg obviously passes the message to CReg (not shown here).
16: Reg tells Anon1 that Voter received its first (and last) VoteNr; in case the Voter accidentally tried to get an additional VoteNr, Anon1 will now tell Uniq to cancel the VoteNr just issued.
17: Anon1 signs VoteNrCert1, giving VoteNrCert
18: Voter receives VoteNrCerts
19: Voter determines its actual vote, giving Vote
20: Anon2 receives Vote + VoteNrCerts from Voter
21: Anon2 checks VoteNrCerts and signs (Vote+VoteNrCerts), giving VoteCert
22: Res receives VoteCert from Anon2, and passes it to CRes
23: CRes checks if the VoteNr has not already been used, and signs the VoteCert, giving Receipt1
24 Res receives Receipt1, and passes it to Anon2
25: Anon2 receives Receipt1, and signs it, giving Receipt
26: Voter receives Receipt.
Counting.
When voting is supposed to stop, every Login receives a StopMsg, as a Tcert(Auth, Obs).
From that moment on, the Logins will no longer accept new Voters.
After a short grace period (e.g. 5 minutes) all other PS's receive the same message, and will stop their services.
Auth and Obs now collect the data from all the individual PS's (as Tcert, signed by those PS's), do their counting, and publish both the raw data and the results.
After the vote, the Voter has all the information on its own voting process, and is able to check the processing of his Vote.
The following information is publicly available:
CReg: all (VoterId, Config, Login_Details, Received_a_VoteNr)
CUniq: all issued VoteNrs
CRes: all (VoteNr, Vote)
And all the subsets of the central registers, as they were collected by the individual Reg, Uniq, and Res.
Technical Details.
The following details apply primarily to the implementation that was being used as an example.
TD1: Redundancy.
The systematic redundancy does not only provide trust between Voter, Auth, and Obs, but also offers the technical advantage of robustness.
The Voters Config specification may contain alternatives for every individual PS in the Config, that are to be used in case the primary selection becomes unavailable during the Voters individual voting process.
All PS's will immediately report unexpected behavior of other PS's to PSreg.
In those cases, Auth and Obs together will:
- mark it "off line" in PSreg
- save its data if possible
- start a (remote) inspection if possible
- inspect the two other PS's in the cluster
TD2: Configuration information.
PSreg publishes information about PS's, as Tcert(Auth,Obs).
The following information should be available:
- PSid
- PStype
- SysAdm
- Public Key
- Operational Status
- Audit Reports
Changes in these records are appended to the record, again as a Tcert(Auth, Obs).
During an inspection of a PS, Auth+Obs can make a copy of the complete file system.
These copies are not being published, but stored in a separate location, first encrypted by Obs, then encrypted by Auth.
So both Obs and Auth are needed to analyze the dump after the voting process.
Such an analyses would only be applied in very special cases, where the publicly available data is insufficient for the debugging of technical problems.
TD3: Identification infrastructure.
In the implementation that is being used as an illustration, the identification process is most likely to be structured as shown in figure 4:
Figure 4: the identification process
1: Voter requests access, stating its Id
2: Login asks Rel to identify Voter
3: Rel asks Voter for proof of its Id
4: Voter provides proof
5: Rel confirms Id
6: Voter is granted access
The Rel PS is a centralized database with relations to (records of) individual Voters.
An example of such a PS is the DigiD infrastructure in the Netherlands.
Ideally, Obs and Auth maintain their own independent Rel PS.
The implementation of "step 4: Voter provides proof" knows many technical options, that may even be used in combination with each other; an incomplete impression:
1: specialized hardware (e.g. smartcard)
2: passwords or transaction codes
3: specialized software solutions
4: biometry
Specialized hardware tokens can provide a very reliable solution, but tend to be expensive and rather difficult to manage, both in the roll out and the maintenance phase.
Shared secrets are generally considered to be a cheap solution.
Besides the fact that they are not all that cheap, they can become rather user unfriendly.
Especially the widely used password procedure is extremely vulnerable to identity theft, for example by phishing and key logging techniques.
A specialized software solution could offer an attractive combination of high reliability, low costs, and great ease of use.
On could for example create a challenge-response procedure based on public key encryption, but storing a private key on a general purpose (and thus likely to be compromised) platform would introduce new opportunities for identity theft.
Alternative designs on the other hand would be quite safe to use.
They will obviously introduce an additional development effort, but that would be dwarfed by the overall investments in a Voting PS.
Biometrical techniques (for example voice recognition) are compelling because of their relation with the way that human beings identify each other in the real world.
Currently, they can not offer the reliability of specialized hardware or software solutions though, so this option should not be used without additional techniques.
Status of this document.
This is my contribution to a discussion in 2006 that was triggered by the "discovery" of flaws in electronic voting machines.
It should primarily show that applying ICT to improve processes requires rethinking all of the process.
I do not intend to take part in discussions that might be triggered by this publication, but if desired I can provide individual advise to those who are seriously involved.
I don't want to discourage anybody, but before you start any discussion, be prepared for the standard resistance procedure in these types of improvement processes:
1: it is impossible (technical objections)
2: OK, it is feasible, but to expensive (financial objections)
3: OK, it is better and cheaper, but it takes a long time to implement (tactical delay in strategic retreat)
At every three of the lines of defense, the resistance will use the weapons:
a: You don't want this (existential power)
b: The superior forces don't want this (divine power)
Just to let you know what you would be fighting against; Good Luck!
Jan-Hein van der Burg
jhvdburg@tiscali.nl