Introduction

Helios 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.

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 <ELECTION_ID>. Assuming a host and prefix that we denote {HELIOS_HOST}, the election data structure, including the election public key, questions, etc., can be obtained by requesting the following URL:

    {HELIOS_HOST}/elections/<ELECTION_ID>

The list of voters, denoted <VOTER_LIST>, is available at:

    {HELIOS_HOST}/elections/<ELECTION_ID>/voters/

Given this list, it is possible to extract individual voter identifiers, denoted <VOTER_ID>

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/

    {HELIOS_HOST}/elections/<ELECTION_ID>/ballots/<VOTER_ID>/all

    {HELIOS_HOST}/elections/<ELECTION_ID>/ballots/<VOTER_ID>/last

    {HELIOS_HOST}/elections/<ELECTION_ID>/result

    {HELIOS_HOST}/elections/<ELECTION_ID>/trustees/

    {HELIOS_HOST}/elections/<ELECTION_ID>/trustees/<TRUSTEE_ID>/robustness_factor

Data Formats

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 alphabetical order and no extraneous whitespace other than that specified by JSON. These two conditions are particularly important, as hashing data structures will only yield the same hash if the conditions are respected. An example of a JSON data structure with these two conditions is:

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 p, the primer-order q of its intended subgroup, the generator g, and the public-key value y (with keys in alphabetical order):

An El-Gamal ciphertext is a JSON structure containing properties alpha and beta, the two components modulo p.

In Helios, all ciphertexts are Exponential ElGamal, so alpha = g^r mod p, and beta = g^m y^r mod p.

In Helios, all hash values are base-64 encoded, prefixed with the algorithm used for hashing, e.g:

Voter

A single voter in Helios is represented using a few fields that identify the voter. This data structure has changed from prior versions of Helios in order to accommodate multiple types of users, not just users identified by email address.

Together, the type and id identify the voter via some external authentication mechanism. In the example above, this is a user whose email address is benadida@gmail.com. Another example might be:

where this is a voter identified by the email address ben@adida.net.

The uuid field is used as a reference key within Helios.

Voters may be identified by OpenID URL rather than email address, in which case their JSON representation is:

Other fields may be present in a <VOTER> data structure, e.g. category. These do not affect the cryptographic processing, but if present, they become part of the hash of the voter list. 

Protecting Voter Privacy

Voter Aliases

An aliased voter still has a UUID, so it can still be referred appropriately in the rest of the system.

Casting a Vote

Once a voter has cast a ballot, the encrypted vote representation is then:

cast_at is the timestamp of the cast vote in UTC.

We describe the details of the <VOTE> data structure later in this document, once we have described all of the required components.

vote_hash is available to enable a shorter version of this data structure:

where only the hash and not the full vote is listed.

Election

An election is represented as:

short_name, name, and description describe the election. The short name must be a few characters without a space (almost like a database key), the name can be a long string, and the description is an even longer description of the election.

REMOVED 2009-11-19 ballot_type indicates the kind of ballot that this election expects. Helios only supports "homomorphic" at this time. And this is a question-level issue anyways, since each question is different.

cast_url indicates the URL where ballots for this election should be cast.

frozen_at indicates the timestamp at which this election was frozen. It remains null until the election is frozen.

openreg indicates whether voters can be added to the list after the election has started.

REMOVED 2009-11-19 tally_type indicates how tallying of the ballots should occur. Helios only supports "homomorphic". This is a separate field from ballot_type because in some homomorphic elections, ballots may be weighted differently depending on the voter category (e.g. students vs. faculty). tally_type also only pertains to each question, not the whole election.

use_voter_aliases indicates whether this election aliases its voters.

uuid is a unique identifier for the election, and name is the election's name.

<ELGAMAL_PUBLIC_KEY> is, as detailed earlier, the JSON data structure that represents an El-Gamal public key.

<QUESTION_LIST> is a data structure that represents the list of questions and available answers to those questions.

and a single question is a JSON object:

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 max indicates the maximum number of options that a voter can select, most often 1. The parameter min indicates the minimum number of options that a voter must select, most often 0. Note how, given that max and min should be small integers, they are in fact serialized as integers, not as strings. choice_type indicates the kind of question, for now just approval (possibly with a maximum number of choices). If max is null, then it's approval voting for as many candidates as desired. tally_type indicates how the question is tallied, e.g. homomorphic or mixnet.

ADDED 2010-08-06: result_type indicates how the result is computed, i.e. absolute or relative, and other result computations. The result_type depends on the choice_type and the max.

voters_hash is the hash of the list of voters for the election. The list of voters is a JSON array of <VOTER> data structures. For example, a list of voters might be:

Note: where Helios v1.0 and v2.0 escaped the "/" character as "\/", Helios v3.0 does not. We believe this escaping was in error.

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 voters_hash, and sets openreg to true.

Election Fingerprint

Once an election is ready to be used for voting, the administrator freezes the election, at which point Helios prevents changing any of the question parameters and voter registration settings: an open election remains an open election, and a closed election remains closed with a fixed voter list. The frozen_at field then indicates the timestamp at which the election was frozen.

Such a frozen election can be designated by its Helios Election Fingerprint, which is the base-64-string-encoded SHA256 of the election data structure serialized as JSON (with properly alphabetized field names). Note how this fingerprint depends on the list of voters if the election registration status is closed, but not if it is open. In any case, this fingerprint does not depend on any cast vote or cast-vote hash.

Vote

A 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.

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.

The value of max in overall_proof matches the value of max in the election's question definition.

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 <VOTE> data structure defined above.

Proofs

A zero-knowledge proof, denoted <ZK_PROOF_0..max>, is a transcript of a non-interactive proof that the corresponding ciphertext encodes an integer value between 0 and max. For the overall proof, the ciphertext whose value is being proven to be between 0 and max is the homomorphic sum (element-wise product) of the choices ciphertexts.

In Helios, all 0..max proofs are disjunctive proofs (CDS & CP), meaning that the transcript includes max+1 proofs, one for each possible value of the plaintext, 0 through max. The max+1 individual challenges must sum up to the single actual protocol challenge, which ensures that one of the proofs is real (while the others are simulated.)

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, A and B. Thus, a ZK proof is:

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> is as follows.

And the contained <ENCRYPTED_ANSWER_WITH_PLAINTEXT> is as follows.

Result

The result of an election is represented using the <RESULT> data structure. The proofs of the decryption are done at the Trustee level. The result simply displays the count of votes for each candidate within each question, in an array of arrays format.

Trustee

Even 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:

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: election, vote, proof, disjunctive_proof, and a few others, all of which correspond to collections of fields that directly map to the JSON data structures described above. However, we note that a verification program need not necessarily parse these JSON strings into custom Python objects. It is perfectly acceptable to extract individual fields when necessary.

In particular, in a number of cases, our sample code will call election.toJSON(), or vote.toJSON() in order to re-convert the data structure to JSON so that it can be hashed and checked for integrity. A verification program that handles JSON strings directly without de-serializing them to Python objects would obviously not need to re-serialize to JSON, either. The original JSON provided by the Helios server hashes appropriately to the intended values.

Verifying a Single Ballot

Recall the Chaum-Pedersen proof that a ciphertext (alpha,beta) under public key (y, (g,p,q)) is proven to encode the value m by proving knowledge of r, the randomness used to create the ciphertext, specifically that g, y, alpha, beta/g^m is a DDH tuple, noting that alpha = g^r and beta/g^m = y^r.

• 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

if pow(public_key.g, proof.response, public_key.p) !=
    ((proof.commitment.A * pow(ciphertext.alpha, proof.challenge, public_key.p)) % public_key.p):
       return False

beta_over_m = modinverse(pow(public_key.g, plaintext, public_key.p), public_key.p) * ciphertext.beta
beta_over_m_mod_p = beta_over_m % public_key.p

if pow(public_key.y, proof.response, public_key.p) !=
   ((proof.commitment.B * pow(beta_over_m_mod_p, proof.challenge, public_key.p)) % public_key.p):
      return False

return True

In a disjunctive proof that the ciphertext is the encryption of one value between 0 and max, all max+1 proof transcripts are checked, and the sum of the challenges is checked against the expected challenge value. Since we use this proof in non-interactive Fiat-Shamir form, we generate the expected challenge value as SHA1(A0 + "," + B0 + "," + A1 + "," + B1 + ... + "Amax" + "," + Bmax) with A0, B0, A1, B1, ... ,Amax, Bmax in decimal form. (Ai and Bi are the components of the commitment for the i'th proof.)

Thus, to verify a <ZK_PROOF_0..max> on a <ELGAMAL_CIPHERTEXT>, the following steps are taken.

for i in range(max+1):
  # the proof for plaintext "i"
  if not verify_proof(ciphertext, i, disjunctive_proof[i], public_key):
    return False

# the overall challenge
computed_challenge = sum([proof.challenge for proof in disjunctive_proof]) % public_key.q

# concatenate the arrays of A,B values
list_of_values_to_hash = sum([[p.commitment.A, p.commitment.B] for p in disjunctive_proof], [])

# concatenate as strings
str_to_hash = ",".join(list_of_values_to_hash)

# hash
expected_challenge = int_sha(str_to_hash)

# last check
return computed_challenge == expected_challenge

Thus, given <ELECTION> and a <VOTE>, the verification steps are as follows:

# check hash (remove the last character which is a useless '=')
computed_hash = base64.b64encode(hash.new(election.toJSON()).digest())[:-1]
if computed_hash != vote.election_hash:
    return False

# go through each encrypted answer by index, because we need the index
# into the question array, too for figuring out election information
for question_num in range(len(vote.answers)):
   encrypted_answer = vote.answers[question_num]
   question = election.questions[question_num]

   # initialize homomorphic sum (assume operator overload on __add__ with 0 special case.)
   homomorphic_sum = 0

   # go through each choice for the question (loop by integer because two arrays)
   for choice_num in range(len(encrypted_answer.choices)):
     ciphertext = encrypted_answer.choices[choice_num]
     disjunctive_proof = encrypted_answer.individual_proofs[choice_num]
     
     # check the individual proof (disjunctive max is 1)
     if not verify_disjunctive_0..max_proof(ciphertext, 1, disjunctive_proof, election.public_key):
        return False
        
     # keep track of homomorphic sum
     homomorphic_sum = ciphertext + homomorphic_sum
   
   # check the overall proof
   if not verify_disjunctive_0..max_proof(homomorphic_sum, question.max,
                                          encrypted_answer.overall_proof,
                                          election.public_key):
       return False
       
# done, we succeeded
return True

Auditing/Spoiling a Single Ballot

Given a <VOTE_WITH_PLAINTEXTS> and a claimed vote fingerprint, verification entails checking the fingerprint, checking all of the proofs to make sure the ballot is well-formed, and finally ensuring that the ballot actually encodes the claimed choices.

# check the proofs
if not verify_vote(election, vote_with_plaintexts):
    return False
    
# check the proper encryption of each choice within each question
# go through each encrypted answer
for encrypted_answer in vote_with_plaintexts.answers:
    # loop through each choice by integer (multiple arrays)
    for choice_num in range(len(encrypted_answer.choices)):
      # the ciphertext and randomness used to encrypt it
      ciphertext = encrypted_answer.choices[choice_num]
      randomness = encrypted_answer.randomness[choice_num]
      
      # the plaintext we expect, g^1 if selected, or g^0 if not selected
      if choice_num == encrypted_answer.answer:
        plaintext = public_key.g
      else:
        plaintext = 1
        
      # check alpha
      if pow(public_key.g, randomness, public_key.p) != ciphertext.alpha:
        return False
        
      # check beta
      expected_beta = (pow(public_key.y, randomness, public_key.p) * plaintext) % public_key.p
      if expected_beta != ciphertext.beta:
        return False

# check the fingerprint
vote_without_plaintexts = vote_with_plaintexts.remove_plaintexts()
computed_fingerprint = base64.b64encode(hash.new(vote_without_plaintexts.toJSON()).digest())[:-1]

return computed_fingerprint == vote_fingerprint

Verifying a Complete Election Tally

To 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.

# Here, we prove that (g, y, ciphertext.alpha, decryption_factor) is a DDH tuple, proving knowledge of secret key x.
# Before we were working with (g, alpha, y, beta/g^m), proving knowledge of the random factor r.
if pow(public_key.g, proof.response, public_key.p) !=
   ((proof.commitment.A * pow(public_key.y, proof.challenge, public_key.p)) % public_key.p):
      return False

if pow(ciphertext.alpha, proof.response, public_key.p) !=
   ((proof.commitment.B * pow(decryption_factor, proof.challenge, public_key.p)) % public_key.p):
      return False

# compute the challenge generation, Fiat-Shamir style
str_to_hash = str(proof.commitment.A) + "," + str(proof.commitment.B)
computed_challenge = int_sha(str_to_hash)

# check that the challenge matches
return computed_challenge == proof.challenge

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.

# compute the election fingerprint
election_fingerprint = b64_sha(election.toJSON())

# keep track of voter fingerprints
vote_fingerprints = []

# keep track of running tallies, initialize at 0
# again, assuming operator overloading for homomorphic addition
tallies = [[0 for a in question.answers] for question in election.questions]

# go through each voter, check it
for voter in voters:
    if not verify_vote(election, voter.vote):
        return False
        
    # compute fingerprint
    vote_fingerprints.append(b64_sha(voter.vote.toJSON()))
    
    # update tallies, looping through questions and answers within them
    for question_num in range(len(election.questions)):
        for choice_num in range(len(election.questions[question_num].answers)):
            tallies[question_num][choice_num] = voter.vote.answers[question_num].choices[choice_num] +
                                                tallies[question_num][choice_num]
    

# now we have tallied everything in ciphertexts, we must verify proofs
for question_num in range(len(election.questions)):
    for choice_num in range(len(election.questions[question_num].answers)):

        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
            # check that it decrypts to the claimed result with the claimed proof
            if not verify_partial_decryption_proof(tallies[question_num][choice_num],
                trustee.decryption_factors[question_num][choice_num],
                trustee.decryption_proof[question_num][choice_num],
                trustee.public_key):
              return False

            # 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
            
# return the complete tally, now that it is confirmed
return {
    'election_fingerprint': election_fingerprint,
    'vote_fingerprints' : vote_fingerprints,
    'verified_tally' : result
}