This page documents tweaks to the Helios v3 Verification Specs that will make data types forward-compatible and able to evolve over time to support other types of elections, in particular other types of homomorphic tallying, mixnet tallying, etc...

NOT FINAL. THIS DOCUMENT IS IN PROGRESS AS OF August 9th 2011.
ALSO worth looking at: Adding Mixnet Support.

Raw Datatypes

Raw, unlabeled datatypes in Helios v4 are only used to represent integers and strings. Integers are base64-encoded.

Adding Type to Data Structures

In order to distinguish between election types, in particular different encryption mechanisms, tallying approaches, etc., data structures will declare types. If they do not declare a type, the default type value assumed is that of Helios v3.0. We use JSON-LD (JSON Linked Data) to add types. JSON-LD is based on the W3C's RDF for extensible linked data.

Public Keys and Ciphertexts

In Helios v3.0, public keys are always ElGamal public keys, as follows:


With v3.1+, a public key should be typed, using the RDF/JSON-LD "a" field name. The value of this field is a URL relative to http://heliosvoting.org/vocab/.


This approach, using _type, is the way we'll do things generally in Helios v3.1+.

Similarly, ciphertexts should be typed.

Elections

Elections in Helios v3.0 do not include type information, but they include a list of questions, and each question does include some type information:

• choice_type: approval or otherwise, e.g. for ranked voting
  
• tally_type: homomorphic or otherwise, e.g. mixnet
  
• result_type: absolute/relative or otherwise.
  

It seems this information is sufficient to express mixnet elections and ranked voting, so no changes are needed here.

Encrypted Answer and Vote

In Helios v3.0, an encrypted vote is a list of encrypted answers. This can remain the same in v3.1+, as there will always be an ordered list of independent questions.
Similarly, a cast vote, which included an encrypted vote, its hash, the hash of the voter, and a date, can remain the same for all election types: these are just the bundling of answers to multiple questions.

However, a single encrypted answer should contain some type information as to how it should be tallied.

The fields within an encrypted answer may, of course, vary depending on _type. An encrypted answer for a mixnet-based system may be:

Complete Datatype Specification

Given the above additions, we now specify the datatypes completely.

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 thus includes 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, with the hashing algorithm specified, e.g:

If the hash value is provided straight, without JSON-LD datatyping, the algorithm is assumed to be SHA256.

Voter

A single voter in Helios is represented using a few fields that identify the voter.

NOTE: should we use a subtype of "voter" here instead of voter_type? TBD.

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

In 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 email-address crawling and 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 typical hash data structure

Voter Aliases

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

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.

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.

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.

voters_hash is the hash of the list of voters for the election. The list of voters is a JSON array of <VOTER> or <ALIASED_VOTER> data structures.

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

and a single question is:

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. In some cases, certain question types are not compatible with homomorphic tallying.

The different types of questions are:

• approval-absolute
• approval-relative

A single answer is then:

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. The specifics of the encrypted answer depend, of course, on the type of encryption used for that question.

The only type of encrypted answer in v3.0 and earlier is the homomorphic approval answer. 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: