Skip to content

Ballot Encryption Sequence and Grammar

Introduction

The phrase encrypting a ballot in ElectionGuard carries a lot of weight. When we encrypt a ballot, we want to accomplish many things depending on the use case

From an end-to-end verifiable election perspective, the ballot must be encrypted such that:

  • a verification code is generated and can be presented to the voter
  • an encrypted tally that uses this ballot can be generated by the tally process
  • independent verifiers can reason (as an academic would say) or interrogate (as a security researcher would say) this ballot and determine:
  • it is a valid ballot
  • it has not been tampered with post-sealing

An ElectionGuard ballot is comprised entirely of encryptions of one (indicating selection made) and zero (indicating selection not made). To enable homomorphic addition (for tallying), these values are exponentiated during encryption. Specifically, to encrypt a ballot entry \((V)\), a random value \(R\) is selected such that \(0 \le R \lt q\) and the following computation is performed:

Zero (not selected) is encrypted as

\[ (g^R \bmod p, K^R \bmod p) \]

One (selected) is encrypted as

\[ (g^R \bmod p, g \cdot K^R \bmod p) \]

Note that if multiple encrypted votes

\[ \left(g^{R_i} \bmod p, g^{V_i} \cdot K^{R_i} \bmod p\right) \]

are formed, their component-wise product

\[ \left(g^{\sum_{i}V_i} \cdot K^{\sum_{i}R_i} \bmod p\right) \]

serves as an encryption of \(\sum_iV_i\)which is the tally of those votes.[^19]

A contest in an election consists of a set of options together with a selection limit that indicates the number of selections that are allowed to be made in that contest. In most elections, most contests have a selection limit of one. However, a larger selection limit (e.g., select up to three) is not uncommon in some elections. Approval voting can be achieved by setting the selection limit to the total number of options in a contest. Ranked choice voting is not supported in this version of ElectionGuard, but it may be enabled in a future version.[^20] Also, write-ins are assumed to be explicitly registered or allowed to be lumped into a single "write-ins" category for the purpose of verifiable tallying. Verifiable tallying of free-form write-ins may be best done with a MixNet[^21] design.

A legitimate vote in a contest consists of a set of selections with cardinality not exceeding the selection limit of that contest. To accommodate legitimate undervotes, the internal representation of a contest is augmented with “placeholder” options equal in number to the selection limit. Placeholder options are selected as necessary to force the total number of selections made in a contest to be equal to the selection limit. When the selection limit is one, for example, the single placeholder option can be thought of as a “none of the above” option.