Ballot Encryption

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 \leq R < q$ , and the following computation is performed.

Zero (not selected) is encrypted as $(g^{R} mod p, K^{R} mod p)$ .
One (selected) is encrypted as $(g^{R} mod p, g \cdot K^{R} mod p)$ .

Note that if multiple encrypted votes $(g^{R_{i}} mod p, g^{V_{i}} \cdot K^{R_{i}} mod p)$ are formed, their component-wise product $(g^{\sum_{i} R_{i}} mod p, g^{\sum_{i} V_{i}} \cdot K^{\sum_{i} R_{i}} mod p)$ serves as an encryption of $\sum_{i} V_{i} -$ which is the tally of those votes.¹

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.² 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³ 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.

With larger selection limits, the number of placeholder options selected corresponds to the number of additional options that a voter could have selected in a contest.

Note

For efficiency, the placeholder options could be eliminated in an approval vote. However, to simplify the construction of election verifiers, we presume that placeholder options are always present – even for approval votes.

Two things must now be proven about the encryption of each vote to ensure the integrity of a ballot.

The encryption associated with each option is either an encryption of zero or an encryption of one.
The sum of all encrypted values in each contest is equal to the selection limit for that contest (usually one).

The use of ElGamal encryption enables efficient zero-knowledge proofs of these requirements, and the Fiat-Shamir heuristic can be used to make these proofs non-interactive. ChaumPedersen proofs are used to demonstrate that an encryption is that of a specified value, and these are combined with the Cramer-Damgård-Schoenmakers technique to show that an encryption is that of one of a specified set of values – particularly that a value is an encryption of either zero or one. The encryptions of selections in a contest are homomorphically combined, and the result is shown to be an encryption of that contest’s selection limit – again using a Chaum-Pedersen proof.

Note

Note that the decryption of the selection limit could be more efficiently demonstrated by just releasing the sum of the nonces used for each of the individual encryptions. But, again to simplify the construction of election verifiers, a Chaum-Pedersen proof is used here as well.

The “random” nonces used for the ElGamal encryption of the ballot nonces are derived from a single 256-bit master nonce $R_{B}$ for each ballot. For each contest listed in the ballot coding file, a contest nonce $R_{C}$ is derived from the master nonce $(R_{B})$ and the contest label $(L_{C})$ as $R_{C} = H (L_{C}, R_{B})$ using the hash function SHA-256. For each option listed in the ballot coding file, the nonce used to encrypt that option is derived from the contest nonce $(R_{C})$ and the selection label for that option $(L_{S})$ as $R = H (L_{S}, R_{C})$ .

A user of ElectionGuard may optionally provide an additional public key. If such a key is provided, ElectionGuard uses that key to encrypt each ballot’s master nonce $R_{B}$ and return this encryption together with the encrypted ballot.

Ballot nonces may be independent across different ballots, and only the nonces used to encrypt ballot selections need to be derived from the master nonce. The use of a single master nonce for each ballot allows the entire ballot encryption to be re-derived from the contents of a ballot and the master nonce. It also allows the encrypted ballot to be fully decrypted with the single master nonce.

Outline for proofs of ballot correctness

To prove that an ElGamal encryption pair $(α, β)$ is an encryption of zero, the Chaum-Pedersen protocol proceeds as follows.

NIZK Proof that $(α, β)$ is an encryption of zero (given knowledge of encryption nonce $R$ )

The prover selects a random value $u$ in $ℤ_{q}$ and commits to the pair $(a, b) = (g^{u} mod p, K^{u} mod p)$ . A hash computation is then performed (using the Fiat-Shamir heuristic) to create a pseudo-random challenge value $c = H (\bar{Q}, (α, β), (a, b))$ , and the prover responds with $v = (u + c R) mod q$ . A verifier can now confirm the claim by checking that both $g^{v} mod p = a \cdot α^{c} mod p$ and $K^{v} mod p = b \cdot β^{c} mod p$ are true.

NIZK Proof that $(α, β)$ is an encryption of one (given knowledge of encryption nonce $R$ )

To prove that $(α, β)$ is an encryption of one, $\frac{β}{g} mod p$ is substituted for $β$ in the above. The verifier can be relieved of the need to perform a modular division by computing $β \bar{g} mod p$ rather than $\frac{β}{g} mod p$ . As an alternative, the verifier can confirm that $g^{c} \cdot K^{v} mod p = b \cdot β^{c} mod p$ instead of $K^{v} mod p = b \cdot (\frac{β}{g})^{c} mod p$ .

As with many zero-knowledge protocols, if the prover knows a challenge value prior to making its commitment, it can create a false proof. For example, if a challenge $c$ is known to be forthcoming, a prover can generate a random $v$ in $ℤ_{q}$ and commit to $(a, b) = (\frac{g^{v}}{α^{c}} mod p, \frac{K^{v}}{β^{c}} mod p) = (g^{v} α^{q - c} mod p, K^{v} β^{q - c} mod p)$ . This selection will satisfy the required checks for $(α, β)$ to appear as an encryption of zero regardless of the values of $(α, β)$ . Similarly, setting $(a, b) = (\frac{g^{v}}{α^{c}} mod p, \frac{K^{v} g^{c}}{β^{c}} mod p) = (g^{v} α^{q - c} mod p, K^{v} g^{c} β^{q - c} mod p)$ will satisfy the required checks for $(α, β)$ to appear as an encryption of one regardless of the values of $(α, β)$ . This quirk is what enables the Cramer-Damgård-Schoenmakers technique to prove a disjunction of two predicates.

Sketch of NIZK Proof that $(α, β)$ is an encryption of zero or one

After the prover makes commitments $(a_{0}, b_{0})$ and $(a_{1}, b_{1})$ to the respective assertions that $(α, β)$ is an encryption of zero and $(α, β)$ is an encryption of one, a single challenge value $c$ is selected by hashing all commitments and baseline parameters. The prover must then provide challenge values $c_{0}$ and $c_{1}$ such that $c = c_{0} + c_{1} mod q$ . Since the prover has complete freedom to choose one of $c_{0}$ and $c_{1}$ , the prover can fix one value in advance – either $c_{0}$ if $(α, β)$ is actually an encryption of one or $c_{1}$ if $(α, β)$ is actually an encryption of zero. In response to the resulting challenge $c$ , the prover uses this freedom to answer its faux claim with its chosen challenge value and then uses the remaining challenge value (as forced by the constraint that $c = (c_{0} + c_{1}) mod q$ ) to demonstrate the truth of the other claim. An observer can see that one of the two claims must be true but cannot tell which.

Details for proofs of ballot correctness

The full protocol proceeds as follows – fully divided into the two cases.

To encrypt an “unselected” option on a ballot, a random nonce $R$ is selected uniformly $ℤ_{q}$ and an encryption of zero is formed as $(α, β) = (g^{R} mod p, K^{R} mod p)$ .

NIZK Proof that $(α, β)$ is an encryption of zero or one (given knowledge of encryption nonce $R$ for which $(α, β)$ is an encryption of zero)

To create the proof that $(α, β)$ is an encryption of a zero or a one, randomly select $c_{1}$ , $v_{1}$ , and $u_{0}$ from $ℤ_{q}$ and form the commitments

(a_{0}, b_{0}) = (g^{u_{0}} mod p, K^{u_{0}} mod p)

and

(a_{1}, b_{1}) = (\frac{g^{v_{1}}}{α^{c_{1}}} mod p, \frac{K^{v_{1}} g^{c_{1}}}{β^{c_{1}}} mod p) = (g^{v_{1}} α^{q - c_{1}} mod p, K^{v_{1}} g^{c_{1}} β^{q - c_{1}} mod p) .

A challenge value $c$ is formed by hashing the extended base hash $\bar{Q}$ together with $(α, β)$ , $(a_{0}, b_{0})$ , and $(a_{1}, b_{1})$ to form a challenge value $c = H (Q, (α, β), (a_{0}, b_{0}), (a_{1}, b_{1}))$ . The proof is completed by forming $c_{0} = (c - c_{1}) mod q$ and $v_{0} = (u_{0} + c_{0} \cdot R) mod q$ and answering the challenge by returning $c_{0}$ , $c_{1}$ , $v_{0}$ , and $v_{1}$ .

To encrypt a “selected” option on a ballot, a random nonce $R$ is selected uniformly from $ℤ_{q}$ and an encryption of one is formed as $(α, β) = (g^{r} mod p, g \cdot K^{r} mod p)$ .

NIZK Proof that $(α, β)$ is an encryption of zero or one (given knowledge of encryption nonce $R$ for which $(α, β)$ is an encryption of one)

To create the proof that $(α, β)$ is an encryption of a zero or a one, randomly select $c_{0}$ , $v_{0}$ , and $u_{1}$ from $ℤ_{q}$ and form the commitments

(a_{0}, b_{0}) = (\frac{g^{v_{0}}}{α^{c_{0}}} mod p, \frac{K^{v_{0}}}{β^{c_{0}}} mod p) = (g^{v_{0}} α^{q - c_{0}} mod p, K^{v_{0}} β^{q - c_{0}} mod p)

and

(a_{1}, b_{1}) = (g^{u_{1}} mod p, K^{u_{1}} mod p)

A challenge value $c$ is formed by hashing the extended base hash $\bar{Q}$ together with $(α, β)$ , $(a_{0}, b_{0})$ , and $(a_{1}, b_{1})$ to form a challenge value $c = H (\bar{Q}, (α, β), (a_{0}, b_{0}), (a_{1}, b_{1}))$ . The proof is completed by forming $c_{1} = (c - c_{0}) mod q$ and $v_{1} = (u_{1} + c_{1} \cdot R) mod q$ and answering the challenge by returning $c_{0}$ , $c_{1}$ , $v_{0}$ , and $v_{1}$ .

In either of the two above cases, what is published in the election record is the encryption $(α, β)$ together with the commitments $(a_{0}, b_{0})$ and $(a_{1}, b_{1})$ which are all hashed together with the election’s extended base hash to form the challenge value $c$ which is published together with values $c_{0}$ , $c_{1}$ , $v_{0}$ , and $v_{1}$ .

Important

An election verifier must confirm the following for each possible selection on a ballot:

(A) The given values $α$ , $β$ , $a_{0}$ , $b_{0}$ , $a_{1}$ , and $b_{1}$ are all in the set $ℤ_{p}^{r}$ . (A value $x$ is in $ℤ_{p}^{r}$ if and only if $x$ is an integer such that 0 ≤ $x$ < $p$ and $x^{q} mod p = 1$ is satisfied.)

(B) The challenge $c$ is correctly computed as $c = H (\bar{Q}, (α, β), (a_{0}, b_{0}), (a_{1}, b_{1}))$ .

(C) The given values $c_{0}$ , $c_{1}$ , $v_{0}$ , and $v_{1}$ are each in the set $ℤ_{q}$ . (A value $x$ is in $ℤ_{q}$ if and only if $x$ is an integer such that $0 \leq x < q$ .)

(D) The equation $c = (c_{0} + c_{1}) mod q$ is satisfied.

(E) The equation $g^{v_{0}} mod p = a_{0} α^{c_{0}} mod p$ is satisfied.

(F) The equation $g^{v_{1}} mod p = a_{1} α^{c_{1}} mod p$ is satisfied.

(G) The equation $K^{v_{0}} mod p = b_{0} β^{c_{0}} mod p$ is satisfied.

(H) The equation $g^{c_{1}} K^{v_{1}} mod p = b_{1} β^{c_{1}} mod p$ is satisfied.

Proof of satisfying the selection limit

The final step in proving that a ballot is well-formed is demonstrating that the selection limits for each contest have not been exceeded. This is accomplished by homomorphically combining all of the $(α_{i}, β_{i})$ values for a contest by forming the aggregate contest encryption $(α, β) = (Π_{i} α_{i} mod p, Π_{i} β_{i} mod p)$ and proving that $(α, β)$ is an encryption of the total number of votes allowed for that contest (usually one). The simplest way to complete this proof is to combine all of the random nonces $R_{i}$ that were used to form each $(α_{i}, β_{i}) = (g^{R_{i}} mod p, K^{R_{i}} mod p)$ or $(α_{i}, β_{i}) = (g^{R_{i}} mod p, g \cdot K^{R_{i}} mod p)$ – depending on whether the value encrypted is zero or one. The aggregate nonce $R = \sum_{i} R_{i} mod q$ matches the aggregate contest encryption as $(α, β) = (Π_{i} α_{i} mod p, Π_{i} β_{i} mod p) = (g^{R} mod p, g^{L} K^{R} mod p)$ - where $L$ is the selection limit for the contest. (Recall that $L$ extra “placeholder” positions will be added to each contest and set to one as necessary to ensure that exactly $L$ selections are made for the contest.)

NIZK Proof that $(α, β)$ is an encryption of $L$ (given knowledge of aggregate encryption nonce $R$ )

An additional Chaum-Pedersen proof of $(α, β)$ being an encryption of $L$ is performed by selecting a random $U$ in $ℤ_{q}$ , publishing $(a, b) = (g^{U} mod p, K^{U} mod p)$ , hashing these values together with election’s extended base hash $\bar{Q}$ to form a pseudo-random challenge $C = H (\bar{Q}, (α, β), (a, b))$ , and responding by publishing $V = (U + C R) mod q$ .⁴

Note that all of the above proofs can be performed directly by the entity performing the public key encryption of a ballot without access to the decryption key(s). All that is required is the nonces $R_{i}$ used for the individual selection encryptions.

Important

An election verifier must confirm the following for each contest on the ballot:

(A) The number of placeholder positions matches the contest’s selection limit $L$ .

(B) The contest total $(A, B)$ satisfies $A = Π_{i} α_{i} mod p$ and $B = Π_{i} β_{i} mod p$ where the $(α_{i}, β_{i})$ represent all possible selections (including placeholder selections) for the contest.

(C) The given value $V$ is in $ℤ_{q}$ .

(D) The given values $a$ and $b$ are each in $ℤ_{q}^{r}$ .

(E) The challenge value $C$ is correctly computed as $C = H (\bar{Q}, (A, B), (a, b))$ .

(F) The equation $g^{V} mod p = (a A^{C}) mod p$ is satisfied.

(G) The equation $(g^{L C} K^{V}) mod p = (b B^{C}) mod p$ is satisfied.

Tracking codes

Upon completion of the encryption of each ballot, a tracking code is prepared for each voter. The code is a running hash that begins with the extended base hash code $\bar{Q}$ and includes an identifier for the voting device, the location of the voting device, the date and time that the ballot was encrypted, and, of course, the encryption of the ballot itself. The hash $(H)$ used for this purpose is SHA-256. The tracking code is formed as follows. $H_{0} = H (\bar{Q})$ where $\bar{Q}$ is the extended base hash code of the election. For ballot with index $i > 0, H_{i} = H (H_{i - 1}, D, T, B_{i})$ where $D$ consists of the voting device information described above, $T$ is the date and time of ballot encryption, and $B_{i}$ is an ordered list of the individual encryptions on the ballot – with the ordering as specified by the ballot coding file. At the conclusion of a voting period (this may be the end of a day in a multi-day election), the hash chain is closed by computing $\bar{H} = H (H_{ℓ},$ "CLOSE" $)$ , where $H_{ℓ}$ is the final tracking code produced by that device during that voting period. The close of the hash chain can be computed either by the voting device or subsequently by election administrators, and it is published as part of the election record.

Important

An election verifier must confirm that each of the values in the running hash is correctly computed. Specifically, an election verifier must confirm each of the following.

(A) The equation $H_{0} = H (\bar{Q})$ is satisfied.

(B) For each ballot $B_{i}, H_{i} = H (H_{i - 1}, D, T, B_{i})$ is satisfied.

(C) The closing hash $\bar{H} = H (H_{ℓ},$ "CLOSE" $)$ is correctly computed from the final tracking code $H_{ℓ}$ .

Once in possession of a tracking code (and never before), a voter is afforded an option to either cast the associated ballot or spoil it and restart the ballot preparation process. The precise mechanism for voters to make these selections may vary depending upon the instantiation, but this choice would ordinarily be made immediately after a voter is presented with the tracking code, and the status of the ballot would be undetermined until the decision is made. It is possible, for instance, for a voter to make the decision directly on the voting device, or a voter may instead be afforded an option to deposit the ballot in a receptacle or to take it to a poll worker to be spoiled. For vote-by-mail scenarios, a voter can be sent (hashes of) two complete sets of encryptions for each selectable option and can effect a ballot challenge implicitly by choosing which encryptions to return.

The initial decryption actually forms the value $g^{\sum_{i} V_{i}} mod p$ . However, since $\sum_{i} V_{i}$ is a relatively small value, it can be effectively computed from $g^{\sum_{i} V_{i}} mod p$ by means of an exhaustive search or similar methods. ↩
Benaloh J., Moran. T, Naish L., Ramchen K., and Teague V. Shuffle-Sum: Coercion-Resistant Verifiable Tallying for STV Voting (2009) in Transactions of Information Forensics and Security. ↩
Chaum D. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms (1981) Communications of the ACM. ↩
One could simply release the aggregate nonce $R = \sum_{i} R_{i} mod q$ to complete this proof. However, since Chaum-Pedersen proofs are being performed elsewhere, it is simpler for a verifier to just repeat the same steps. ↩