Agora, a virtual parliament
The Agora Ciudadana project aims to develop an internet voting system that is cryptographically secure, supports vote delegation, and scales well to massive elections. Agora is free software. These ambitious requirements may seem almost unreachable. Nonetheless, this is what the development team is attempting, and we are reasonably confident that it is possible.
The project objectives are those mentioned above, they are clear cut and arise from the idea behind Partido de Internet (PDI), the political party where Agora’s development began. PDI is a policy-agnostic political party that does not have, nor will ever have, a political ideology. It has a single and radical proposal: PDI elected representatives will vote in congress according to what the people have previously voted through the internet using Agora.
Secure voting scheme
Agora’s security scheme is based on voter authentication and digital signing of votes through the DNIe, and a secure voting scheme based on Mixnets and ElGamal encryption, with the added novelty of support for vote delegation. No new cryptographic primitives are proposed or developed, rather existing and well established protocols are used.
Cryptographically secure voting schemes are generally not well known to the public, but they do provide several desirable characteristics that physical voting protocols lack, such as the possibility that anyone can mathematically verify that the election result is correct (this property is called Universal Verifiability) Additionally, the secrecy of the votes depends on a collection of authorities, in a way that as long as one such authority remains honest, the secrecy of the vote is guaranteed.
How an election works
1. Key generation
In a voting system based on mixnets, the first thing that happens to run an election is the selection of several authorities that will jointly guarantee the secrecy of the vote. Each authority generates an ElGamal public/private key pair, and shares the public key. All such public keys are combined using a simple mathematical procedure that generates a joint public key that will serve as the election’s public key. This is the key that voters will use to encrypt their votes. The public key will be published in the bulletin board, a board where all the public data for the election will be published for anyone to see. The authorities will also make their individual public key available, so that anyone can verify that the joint public key does in fact correspond to the public keys of all the authorities.
The larger the number of authorities the better, as this increases the security of the election, since more authorities would have to be corrupted to compromise vote secrecy. However, a larger number of authorities also implies a greater computational cost for the election.
2. Vote reception
Once a public key is created for a specific vote, the vote text is established along with the voting period, that is, the time window during which voting is allowed. Once the voting period starts, voters may begin casting votes through the web, or using the voting system’s public API. Agora is conceived in such that any spanish citizen aged 18 or over can vote. To ensure that only eligible citizens may vote, as well as to avoid duplicate votes,
Agora uses DNIe based voter authentication. The voter, either through a desktop program or through an applet, selects an option for the vote, encrypts the vote and finally signs it digitally with the DNIe. The digital signature allows voter authentication, that both ensures that voters are eligible as well as avoids the possibility of duplicate votes.
The encrypted (and therefore secret/private) and signed votes will be published on the bulleting board so that anyone can check whether a specific voter has voted, and individual voters can verify that the vote received by the system matches their vote as cast.
3. Vote tallying
Once the voting period ends, vote tallying begins. For a voting system based on Mixnets this proceeds in two phases. First, votes are anonymized such that it is impossible to link a vote to the person who cast it. Then the votes are decrypted and then tallied as plaintexts. This process is carried out by the election authorities.
We refer to this system as being “based on mixnets” because it uses a mixnet to anonymize votes: each authority re-encrypts and re-shuffles votes. Each authority re-encrypts votes in such a way that for example if a voter selected “option 1″ and encrypted it as encryption(“option 1″, electionKey) = A (where A is the ciphertext), th re-encryption that authority 1 carries out is re-encryption(A, authority1Key) = A’ = re-encryption(encryption(“option 1″, electionKey), authority1Key) such that A and A’ are ciphertexts that appear completely unrelated but correspond to the same plaintext. This process is carried out by every authority so that the end result is something of the form encryption(encryption(“opción 1″, electionKey), electionKey) = A”.
Because of the homomorphic property of ElGamal systems, the decryption of the final re-encrypted ciphertext results in the original plaintext. The correspondence with partial re-encryptions is impossible to establish. This, together with the fact that authorities also reshuffle re-encrypted votes, guarantees that the final, one step decryption of the ciphertexts does not compromise privacy. In summary, the link from ciphertext to plaintext is broken, the vote is thus anonymized.
(image used from the wombat project http://www.wombat-voting.com/how-to-vote/the-tallying-process)
Once the encrypted votes have anonymized, the authorities jointly decrypt them, the tally is then trivial. The results are published on the bulletin board. Thus, the original ballots emitted by the voters are never decrypted, their secrecy is maintained. The authorities themselves do not know the voter’s choice. Only if all the authorities colluded would it be possible for them to decrypt one or several votes. For this reason a greater number of authorities grants the system more security.
As stated before, the elections are universally verifiable. This means that even if all authorities were corrupt it would be possible to detect election fraud. This is true by virtue of the fact that for each of the steps of the election processing (re-encryption, shuffling and decryption), the authorities must provide mathematical proofs that they operated correctly, and must publish these proofs on the bulletin board. These proofs are zero-knowledge, that is, the content of the proof reveals no information, so secrecy is again maintained. We highly recommend the wikipedia article on zero knowledge proofs (based on the the paper “How to explain zero knowledge proofs to your kids”) to understand how they work.
Delegated voting scheme
According to our calculations, approximately 6600 votes take place per year, only counting congress. This corresponds roughly to a vote every hour, on average. Not many people will be willing or able to excercise their vote in an informed maner given such a high rate of voting events, especially considering that many of these are decisions on lesser matters that may not very significant for the voter. For this reason, vote delegation becomes an essential requirement for Agora, such that voters can delegate their vote to someone they trust and that can spend more time researching voting matters. At the same time, the voter will always maintain the ability to override his delegated vote at any time and excercise a direct vote for specific matters, thus retaining control in a flexible manner.
Anybody can create a delegate (or Proxy) in Agora, all that is necessary is for the delegate to be appropriately registered in the system. Examples of delegates could be “Richard Stallman”, “Green Peace”, “The Republican Party”, “Amnesty International”. Votes cast by delegates are public, and they must be cast prior to the direct voting period. This ensures that delegates can never deceive those that would delegate their votes to them; said voters could always override their delegated vote in time if they are unhappy with their delegate’s choice.
Despite the fact the delegates’ votes are public, the choice of delegate itself remains secret. If you decide to delegate your vote to, for example, “Richard Stallman”, that choice of delegate will be secret. If you decide to create your a delegate named “John Doe” and delegate your vote to your own delegate, that choice of delegate will also remain secret, although your vote as the delegate “John Doe” will be public. So in summary, votes cast by delegates are public, but voters’ choice of delegate is not.
The delegated voting system that we have designed is based on the use a parallel and continuous voting phase that tallies votes that represent a voter’s choice of delegate.
Like in any other election, a number of authorities are necessary that will jointly create the public key, and will process the votes as necessary. For a regular vote taking place in congress the options present in the ballot are “YES”, “NO”, “ABSTAIN”. A ballot for an election in the delegated system contains one option per possible delegate. This particular election (which we can call delegate election) never finishes, tallies are repeated periodically, and the options present in the ballot (corresponding to the list of delegates) may change over time as new delegates are registered.
For example, lets consider that a citizen delegates his vote to Richard Stallman. What that voter is really doing is encrypting his/her ballot whose content is roughly “My delegate is Richard Stallman” with the public key of the delegate election, signing it with their DNIe, and sending it to Agora that will validate it and store it.
In the next vote in congress, say a decision to modify intellectual property law (IPL), the delegate Richard Stallman casts a vote, for example “Yes”. This choice would be public, and once the direct voting period opens, Richard Stallman would have had to already specify his vote. This would allow the voter to override their delegated vote with a direct vote, or change their choice of delegate, in case he/she did not agree with his vote.
Once the direct voting period is over, the tally is carried out for both elections: one corresponding to the specific vote on the IPL, and one corresponding to the delegate election. Say for example that the result in the direct vote is 100,000 YES, 30,000 NO and 1,000 ABSTAIN. Additionaly, in the delegated election, imagine that Richard Stallman received 1,000,000 delegated votes. Because Richard Stallman, as a delegate, published his vote as YES, then those votes would be added to the YES option for the direct vote, resulting in a total of 1,100,000 for YES. The process is exactly the same for all delegates; for each of these their sum total of delegated votes is added to the direct vote option that said delegate publicly selected.
Note that Agora is the first cryptographically secure voting system that supports vote delegation; this represents a genuine contribution. A paper is forthcoming where we will describe this novelty in detail.
Technology
In terms of software components, the Agora project consists of two main parts: the backend and the frontend. The backend is Verificatum, a library whose main developer is Douglas Wikström, a swedish cryptography researcher. We are working on Verificatum to speed it up and allow it to scale massively. For the frontend we will use Agora On Rails, developed by members of PDI. The frontend will need to be modified to accomodate the security scheme we have designed.
Massive Voting
As stated earlier, approximately 6600 votes take place yearly in congress alone. This translates to roughly one vote per hour on average. In the last general election in Spain there were 35 million voters. These two figures together mean that on average we must be able to process 35 million votes per hour to allow all possible voters to participate; if we cannot attain this throughput we could possibly shut out voters, an unacceptable scenario.
We have conducted benchmarks that show that with 3 authorities, a key length of 2048 bits, and a reasonably powerful machine per authority it is possible to process approximately 300,000 votes per hour. However, we are working with the developers of Verificatum on a more optimized version with increased performance, as well as adding the ability to scale out to more machines. Also, we do not rule out the possiblity of processing votes with graphics cards (GPU’s) using OpenCL.
Voting through the internet? Are you mad?!
Internet voting has its dangers, there is no doubt about that. If the client computer is compromised, for example with a virus, it could cast votes incorrectly, not cast them at all, or reveal the voter’s choice, all of these without the voter knowing anything was wrong. In order to address these issues we will create a linux distribution on a LiveCD/LiveUSB so that voters can generate their vote in a secure environment, without an internet connection. They can then cast their vote via the internet once their vote has been encrypted and signed from within the secure environment. Additionally, we will carry out public information campaigns to describe the system, how it works, the possible dangers, and how the DNIe works.
Of course, there is also the issue of coercion, of which we are very aware of. Coercion can take place locally, for example if your boss demands to oversee how you vote to ensure you make the choice he expects. This type of coercion already exists with traditional voting, for example voting through regular mail. It may also exist if somebody demands to enter the private voting booth with you. More specific to internet voting is the problem of non-local coercion or vote buying, where it is possible for a voter to prove to others what he/she voted without the need for said agents to be present. This is a real problem we are aware of and we are researching ways to mitigate it. Nonetheless, the problem of coercion for high frequency, continuous elections is qualitatively different from those of traditional elections. Voting power is spread out in time accross different elections, and it is harder and more costly for malicious agents to achieve their ends than if power were concentrated in few, far between and general elections. We may present a paper to describe these differences in depth in the near future.
We at the Agora project are not actually huge fans of internet voting because of the security issues that may arise. We would prefer to have voting booths with a certified and periodically verified (by third parties) computer at each town and city. It would also be desirable not to depend on the police as the single authority that provides and verifies DNIe signatures and certificates. Nonetheless, despite the problems our system may have, the possibility of offering the citizenship a working and practical liquid democracy through PDI seems to far outweigh the potential dangers, and for this reason it is worth purusing this objective, and do things as best as possible.
If things do move forward positively, we will be able to direct many more resources to create a much more secure and robust system including some of the measures I have suggested above, but some of these are too costly initially.
Agora for all and all for Agora
Although the Agora project was born out of a specific need that PDI had to fulfill, we soon realised that it could be a tool that could be useful to many more people, so Agora was recently detached from PDI and stands as an independent project in its own right. Of course, Agora is still a central element of PDI’s strategy, but anybody who shares an interest in the projects is welcome to collaborate on its development. Agora has been from the beginning been and will be free software.
Agora is a software project with a clear aim to improve our democratic system. The project is well underway but still not complete, and is driven by voluntary work donated generously by members of our team. We welcome anyone, developers, researchers, security enthusiasts, designers, or anyone else who shares our vision, to collaborate and help bring this vision closer to reality.
