E-Voting

Preface

This is written from a cryptography/security perspective, so I assume basic knowledge of public-key and symmetric crypto. If you have comments, suggestions, or feedback, hit me up by email.

Goals

• As much information as possible is public to allow verification by any interested third-party.
• Consists of multiple independent systems to make it impossible for a single well-placed individual to attack.
• Votes are private.
• Voters can verify their vote was recorded correctly.

Description

My hypothetical system consists of three completely independent components: an authenticator, a key signer, and a vote recorder (all separate from the voter's client system). For optimal security, each should be developed by a separate group and kept completely isolated. All source should be published, and each riding or district should have their own instances with their own keys, to reduce the chance a single attacker could control the entire election.

Voter's Perspective

All of the below details could be hidden away behind proper UX of course, so this is more from the perspective of the voter's "app" than the voter themselves.

In order to vote, the voter generates a public/private key pair and a symmetric key. They encrypt their public key with the symmetric key, and submit the resulting ciphertext to the authenticator, along with legal proof of identity (e.g. a driver's license or passport). The authenticator signs and publishes the ciphertext.

The voter then submits the signed ciphertext and their symmetric key to the key-signer, which verifies the authenticator's signature, decrypts the ciphertext to reveal a public key, then signs and publishes the voter's public key.

Finally, the voter signs their vote with their private key, and publishes it to the vote recorder. Anyone can verify that the vote was signed by a private key whose corresponding public key was signed by the key-signer, and that that private key was only used once.

Authenticator

This component is responsible for authenticating that a person is who they say they are, and is eligible to vote. Initial data consists of the electoral voter list (which is public) along with a public/private key pair. Eligible voters may at any time submit proof of identity (whatever that means in your country) as well as an opaque blob. On successful authentication, the system permanently publishes the signed blob alongside the voter's identity.

This system guarantees that it will only ever sign a single blob for each eligible voter. Since the voter list and signed blobs are public, the maximum number of possible legitimate votes is publicly verifiable.

Key Signer

This component is responsible for signing and publishing voters' public keys. Its only initial state is a public/private key pair (different from that used by the authenticator). At any time, an eligible voter may submit a blob signed by the authenticator alongside their symmetric key. The system verifies the authenticator's signature, decrypts the blob, then signs and permanently publishes the resulting plaintext public key.

This system guarantees it will only sign public keys which are first verified by the authenticator. By immediately discarding the symmetric key after decrypting the blob, the window in which an identity may be linked to a signed key is kept to a minimum. Anyone can verify that the number of signed keys is less than or equal to the number of signatures published by the authenticator.

Vote Recorder

This component is responsible for receiving and publishing votes. At any time a voter may sign their vote with their private key and submit the signed vote to the recorder. The recorder verifies that the corresponding public key was signed by the key-signer, and records the vote alongside the signed public key.

This system guarantees that each private key can only be used to sign a single vote, and that users can see their vote recorded publically to verify at any time.

Possible Attacks

Common Problems

Like any remote voting system, without physically private ballots it is possible for individuals to be coerced in their voting. Without physical presence it is also more difficult to accurately authenticate voters, since forging a piece of identity (e.g. a driver's license) is a lot simpler when the photo does not have to match your face. The security of the system also depends heavily on the underlying crypto; if an attacker can cheaply crack symmetric or asymmetric keys then all bets are off.

Casting Additional Votes

An attacker with access to the private key of either the authenticator or the key-signer could cast additional unauthorized votes. However, the number of votes they could cast without detection would be limited in several ways:

• If the key-signer publishes more signatures than the authenticator, this is easily detectable by any third-party, and invalidates the election. Therefore every additional vote cast would require an identity on the electoral role.
• Any voter who submits to the authenticator but not the key-signer would leave their identity open for the above attack, but I expect that number to be extremely low since most voters would use software to accomplish both steps in quick succession.
• Eligible voters who do not even submit to the authenticator could have their identities co-opted for this purpose, but if any significant number of identities were stolen, such people would be able to complain. Ameliorating tactics might be to permit "null" or "protest" votes to be registered through the normal process (thus consuming an identity), and to send a "thank you for voting" notification to each consumed identity, alerting non-voters that their identity had been co-opted.
• With full access to the authenticator, an attacker could simply create additional identities on the electoral role, but this would be difficult to do at any sort of scale without detection since the list is publicly auditable.

Changing or Revoking Votes

This attack is effectively impossible without detection. Since every signature by the authenticator is published, every signature by the key-signer is published, and every vote received by the recorder is published, there is no room for a changed or revoked vote to exist without trivial detection by the voter or a third party.

Miscounting Votes

This attack is effectively impossible; every signed vote is individually published, so any person would be able to trivially check the counts. I expect each major news organization would run their own counter simply in order to publish the most up-to-the-minute results.

Identifying Voters

An attacker with full access to the key-signer would be able to identify voters at will, since they would be able to record the mapping from signed ciphertext to public key which protects that information.

There is also the possibility of a timing attack here, by correlating published blobs from the authenticator with published keys from the key-signer. This can be reduced by adding a random back-off in the client between the two steps.

Finally, simple IP-based identification can be avoided as long as the client uses three distinct TOR routes, one to talk to each of the three components.