## IntroductionHelios is an open-audit voting system, which means that: - Alice can verify that her vote was correctly captured,
- all captured votes are displayed (in encrypted form) for all to see, and
- anyone can verify that the captured votes were correctly tallied.
This document specifies all data formats and the exact verification protocols and algorithms. Using this document, it should be possible for an able programmer to build a complete verification program in any modern programming language. For the sake of concreteness, instead of pseudo-code, we use Python (2.3 or above.) This document covers Helios 3.0, due out for release in Fall 2009. The single biggest change is the introduction of modularity of both services (election preparation, ballot preparation, ballot casting) and algorithms, and the additional verbosity required in the data formats to indicate which module is used for each component of an election. ## ComponentsHelios is split into 4 major components:-
**election builder**: a web-based tool to create an election. -
**voting booth**: a web-based voting booth where ballots are filled out and encrypted. -
**ballot casting server**: the server where filled-out ballots are submitted. -
**audit server**: the place where all data is posted at the end of an election.
## Audit Data All data for an election is easily accessible using simple HTTP GET
requests. The HTTP interface for accessing all data from a given
election is built so as to enable static storage of this data in a
simple filesystem made available over the web, to simplify long-term
robustness. Consider an election with election id {HELIOS_HOST}/elections/<ELECTION_ID>
The list of voters, denoted {HELIOS_HOST}/elections/<ELECTION_ID>/voters/
Given this list, it is possible to extract individual voter identifiers, denoted The list of cast ballots is available at, with each ballot including the <VOTER_ID> that it corresponds to: {HELIOS_HOST}/elections/<ELECTION_ID>/ballots/ This call will return ballots in chronological (oldest to newest) order, and takes optional parameters limit and after. {HELIOS_HOST}/elections/<ELECTION_ID>/ballots/<VOTER_ID>/allFor convenience, the last cast ballot is: {HELIOS_HOST}/elections/<ELECTION_ID>/ballots/<VOTER_ID>/lastThe result of an election is available at: {HELIOS_HOST}/elections/<ELECTION_ID>/resultEvery election has trustees (sometimes just one), and the list of trustees, including each trustee's public key and PoK, decryption factor and proof is at: {HELIOS_HOST}/elections/<ELECTION_ID>/trustees/ NOT YET IMPLEMENTED:While the trustee's robustness information (e.g. Lagrange coeff) is at: {HELIOS_HOST}/elections/<ELECTION_ID>/trustees/<TRUSTEE_ID>/robustness_factor
We begin with a description of the data types and their representations. All data made available by Helios is in JavaScript Object Notation (JSON) format, with keys in Example (not an actual Helios data structure)## Basic Cryptographic Datatypes All large integers are represented in decimal form as strings,
rather than integers. The reason is that some languages do not support
big integers natively, and thus cannot properly parse large integers in
JSON integer form. An El-Gamal public-key is then a dictionary
including the prime <ELGAMAL_PUBLIC_KEY>
An El-Gamal ciphertext is a JSON structure containing properties <ELGAMAL_CIPHERTEXT>
In Helios, all ciphertexts are In Helios, all hash values are base-64 encoded, prefixed with the algorithm used for hashing, e.g: Hash value example## Voter
A single voter in Helios is represented using a few fields that identify the voter. <VOTER>
Together, the <VOTER>where this is a voter identified by the email address ben@adida.net.
The Voters may be identified by OpenID URL rather than email address, in which case their JSON representation is: <VOTER>"voter_id": "http://benadida.myopenid.com", "voter_type": "openid"}
Other fields may be present in a ## Protecting Voter PrivacyIn order to protect voter privacy, Helios can obfuscate the voter_id, especially when that voter_id is an email address. This protection is not meant to resist a powerful attacker with other knowledge about the voter, but mostly to prevent activities such as email-address crawlers for the purpose of spamming. In this case, a voter can be represented with the field voter_id_hash replacing voter_id. The hash is SHA256 by default, or specified as a prefix when it is a different hash:<VOTER>## Voter AliasesIn some elections, it may be preferable to never reveal the identity of the voters. This is particularly applicable when organizers are worried about votes being decryptable in 20-30 years, when cryptographic advances make today's algorithms weaker. An election may thus publish only an ALIASED_VOTER:<ALIASED_VOTER>
{"alias": "voter_123",
"uuid": "b7dbd90a-65e3-11de-8c90-001b63948875"}
An aliased voter still has a UUID, so it can still be referred appropriately in the rest of the system. ## Casting a VoteOnce a voter has cast a ballot, the encrypted vote representation is then: <CAST_VOTE>"voter_hash": "sha256:2bxksdlkxnsdf", "voter_uuid": "b7dbd90a-65e3-11de-8c90-001b63948875"} cast_at is the timestamp of the cast vote in UTC. We describe the details of the
<SHORT_CAST_VOTE>"voter_hash": "sha256:2bxksdlkxnsdf", "voter_uuid": "b7dbd90a-65e3-11de-8c90-001b63948875"} where only the hash and not the full vote is listed. ## ElectionAn election is represented as: <ELECTION>"description": "... blah blah blah ... info about the election", "frozen_at": null, "name": "Student President Election at Foo University 2010", "openreg": false, "public_key": <ELGAMAL_PUBLIC_KEY>, "questions": <QUESTION_LIST>, "short_name": "fooprez2010", "use_voter_aliases": false, "uuid": "1882f79c-65e5-11de-8c90-001b63948875", "voters_hash": "G6yS/dAZm5hKnCn5cRgBGdw3yGo"}
<QUESTION_LIST>and a single question is a JSON object: <QUESTION>"result_type": "absolute", "question": "Who Should be President?", "short_name": "President", "tally_type": "homomorphic"} which, in this case, contains two possible answers (alice and bob),
URLs that describe these answers in greater detail, the text of the
question, and a short name for the question. The parameter
<VOTER_LIST> (example)
## Open Registration Helios supports "open registration elections", when the election
administrator so desires. In those elections, the voter list is not set
ahead of time. In that case, an election data structure contains a null Note: in Helios v1.0 and v2.0, the openreg field was present only for open registration, and voters_hash was absent when openreg was true. For serialization consistency, Helios v3.0 always contains all fields.## Election Fingerprint
Once an election is ready to be used for voting, the administrator
Such a frozen election can be designated by its ## VoteA vote contains a list of encrypted answers, and a reference to the election, both by ID (for convenience) and by hash (for integrity.) The hash is the election fingerprint just described. <VOTE>Each "encrypted answer" corresponds to one election question: it contains a list of ciphertexts (one for each possible choice for that question), a list of corresponding proofs that the ciphertext is correctly formed, and an overall proof that all of the ciphertexts for that election question, taken together, are correctly formed. <ENCRYPTED_ANSWER>
The value of For approval voting questions, the overall_proof is absent. When a voter generates a ballot, Helios provides the ballot
fingerprint, which is the base64-encoding of the SHA256 hash of the ## Proofs
A zero-knowledge proof, denoted
In Helios, all <ZK_PROOF_0..max> A single ZK proof is then composed of three messages: the
commitment, the challenge, and the response. Since the proof is a
Chaum-Pedersen proof of a DDH tuple, the commitment is composed of two
values, <ZK_PROOF(plaintext)>## Ballot Audit Trail When a voter chooses to audit their ballot, each encrypted answer
contains additional information concerning the actual selected choice
and the randomness used to encrypt each choice's ciphertext.
Specifically, the JSON structure for <VOTE_WITH_PLAINTEXTS>{"answers": [<ENCRYPTED_ANSWER_WITH_PLAINTEXT>, <ENCRYPTED_ANSWER_WITH_PLAINTEXT>, ...], "election_hash": <B64_HASH>, "election_uuid": <ELECTION_UUID>}
And the contained <ENCRYPTED_ANSWER_WITH_PLAINTEXT>## Result
The result of an election is represented using the <RESULT>## TrusteeEven if there is only one keypair in the case of a simple election, Helios v3 (in a departure from previous versions), represents every election as having trustees. If there is only one trustee, that's fine, but the data structure remains the same: <TRUSTEE>"decryption_proofs": <LIST_OF_LISTS_OF_DEC_PROOFS>, "pok": <POK_OF_SECRET_KEY>, "public_key": <PUBLIC_KEY>, "public_key_hash": <PUBLIC_KEY_HASH>, "uuid": <UUID_OF_TRUSTEE>} ## A Note on the Source Code in this Specification In the rest of this document, we show how to verify various aspects
of a Helios election using Python code for concreteness and legibility.
We assume that certain data structures have been defined:
In particular, in a number of cases, our sample code will call ## Verifying a Single Ballot
Recall the Chaum-Pedersen proof that a ciphertext - Prover sends
`A = g^w mod p`and`B = y^w mod p`for a random`w`. - Verifier sends
`challenge`, a random challenge`mod q`. - Prover sends
`response = w + challenge * r`. - Verifier checks that:
`g^response = A * alpha^challenge``y^response = B * (beta/g^m)^challenge`
verify_proof(ciphertext, plaintext, proof, public_key):if pow(public_key.g, proof.response, public_key.p) !=
In a disjunctive proof that the ciphertext is the encryption of one value between 0 and Thus, to verify a <ZK_PROOF_0..max> on a <ELGAMAL_CIPHERTEXT>, the following steps are taken. verify_disjunctive_0..max_proof(ciphertext, max, disjunctive_proof, public_key):for i in range(max+1):
Thus, given verify_vote(election, vote):# check hash (remove the last character which is a useless '=') ## Auditing/Spoiling a Single Ballot
Given a verify_ballot_audit(vote_with_plaintexts, election, vote_fingerprint)# check the proofs ## Verifying a Complete Election TallyTo verify a complete election tally, one should: - display the computed election fingerprint.
- ensure that the list of voters matches the election voter-list hash.
- display the fingerprint of each cast ballot.
- check that each cast ballot is correctly formed by verifying the proofs.
- homomorphically compute the encrypted tallies
- verify each trustee's partial decryption
- combine the partial decryptions and verify that those decryptions, the homomorphic encrypted tallies, and the claimed plaintext results are consistent.
In other words, the complete results of a verified election includes: the election fingerprint, the list of ballot fingerprints, the trustee decryption factors and proofs, and the final plaintext counts. Any party who verifies the election should re-publish all of these items, as they are meaningless without one another. This is effectively a "re-tally". Part of this re-tally requires checking a partial decryption proof, which is almost the same, but not quite the same, as checking an encryption proof with given randomness. Given a ciphertext denoted (alpha,beta), and a trustee's private key x corresponding to his public key y, a partial decryption is: dec_factor = alpha^x mod p. The trustee then provides a proof that (g, y, alpha, dec_factor) is a proper DDH tuple, which yields a Chaum Pedersen proof of discrete log equality. Verification proceeds as follows: verify_partial_decryption_proof(ciphertext, decryption_factor, proof, public_key):# Here, we prove that (g, y, ciphertext.alpha, decryption_factor) is a DDH tuple, proving knowledge of secret key x. Then, the decryption factors must be combined, and we check that: dec_factor_1 * dec_factor_2 * ... * dec_factor_k * m = beta (mod p) Then, the re-tally proceeds as follows. retally_election(election, voters, result, result_proof):# compute the election fingerprint ` decryption_factor_combination = 1` ` for trustee_num in range(len(election.trustees)):` ` trustee = election.trustees[trustee_num]` # verify the tally for that choice within that question ` # combine the decryption factors progressively` ` decryption_factor_combination *= trustee.decryption_factors[question_num][choice_num]` ` if (decryption_factor_combination * election.result[question_num][choice_num]) % election.public_key.p` ` != tallies[question_num][choice_num].beta % election.public_key.p:` return False |