Verifier Construction
While it is desirable for anyone who may construct an ElectionGuard verifier to have as complete understanding as possible of the ElectionGuard design, this section isolates the items which must be verified and maps the variables used in the specification equations herein to the labels provided in the artifacts produced in an election. ^{1}
Implementation details
There are four operations which must be performed – all on very large integer values: modular addition, modular multiplication, modular exponentiation, and SHA256 hash computations. These operations can be performed using a programming language that provides native support, by importing tools to perform these large integer operations, or by implementing these operations from scratch.
Modular Addition
To compute
one can compute
However, this is rarely beneficial. If it is known that \(a,b \in Z_n\), then one can choose to avoid the division normally inherent in the modular reduction and just use
(if \(a+b \lt n\)) or
(if \(a+b \ge n\)).
Modular Multiplication
To compute
one can compute
Unless it is already known that \(a,b \in Z_n\), it is usually beneficial to perform modular reduction on these intermediate values before computing the product. However, it is still necessary to perform modular reduction on the result of the multiplication.
Modular Exponentiation
To compute
one can compute
but one should not perform a modular reduction on the exponent.^{2} One should, however, never simply attempt to compute the exponentiation \(a^b\) before performing a modular reduction as the number \(a^b\) would likely contain more digits then there are particles in the universe. Instead, one should use a specialpurpose modular exponentiation method such as repeated squaring which prevents intermediate values from growing excessively large. Some languages include a native modular exponentiation primitive, but when this is not available a specialized modular exponentiation tool can be imported or written from scratch.
Hash Computation
Hashes are computed using the SHA256 hash function in NIST (2015) Secure Hash Standard (SHS) which is published in FIPS 1804 and can be found in https://csrc.nist.gov/publications/detail/fips/180/4/final.
For the purposes of SHA256 hash computations, all inputs – whether textural or numeric – are represented as utf8 encoded strings. Numbers are represented as strings in base ten. The hash function expects a singledimensional array of input elements that are hashed iteratively, rather than concatenated together. Each element in the hash is separated by the pipe character (“”). When dealing with multidimensional arrays, the elements are hashed recursively in the order in which they are input into the hash function. For instance, calling
is a function call with 4 parameters, where the 3rd parameter is itself an array. The hash function will process arguments 1 and 2, when it gets to argument 3 it will traverse the array (and hash the values 3, 4 ,5) before hashing the final fourth argument (whose value is 6). When hashing an array element that is empty, the array is instead replaced with the word “null” as a placeholder.
Parameter Validation
Important
An ElectionGuard version 1 election verifier may assume that the baseline parameters match the parameters provided above. However, it is recommended that the below parameters be checked against the parameters of each election to accommodate the possibility of different parameters in future versions of ElectionGuard.^{3}
Variable  Meaning  Folder  File  Level 

\(p\)  4096bit modulus  root  constants.json  large_prime 
\(q\)  256bit prime order of subgroup \(Z_p^*\) of encryptions  root  constants.json  small_prime 
\(r\)  cofactor of \(q\)  root  constants.json  cofactor 
\(g\)  generator of order \(q\) multiplicative subgroup of \(Z_p^*\)  root  contstants.json  generator 
\(n\)  number of guardians  root  context.json  number_of_guardians 
\(k\)  minimum number of guardians required to decrypt tallies and produce verification data  root  context.json  quorum 
\(Q\)  base hash value formed by \(p\), \(q\), \(g\), \(n\), \(k\), date, and jurisdictional information  root  context.json  crypto_base_hash 
Guardian Public Key Validation
Important
An election verifier must confirm the following for each guardian \(T_i\) and for each \(j \in Z_k\):
(A) The challenge \(c_{i,j}\) is correctly computed as
(B) The equation
is satisfied.
Variable  Meaning  Folder  File  Level 

\(K_{i,j}\)  public form of each random coefficient \(a_{i,j}\)  coefficients  every file in this folder  large_prime 
\(h_(i,j)\)  coefficient commitments  coefficients  every file in this folder  coefficient_proofs \(\rightarrow\) [Item] \(\rightarrow\) commitment 
\(c_i\)  challenge value  coefficients  every file in this folder  coefficient_proofs \(\rightarrow\) [Item] \(\rightarrow\) challenge 
\(u_{i,j}\)  response  coefficients  every file in this folder  coefficient_proofs \(\rightarrow\) [Item] \(\rightarrow\) response 
Election Public Key Validation
Important
An election verifier must verify the correct computation of the joint election public key and extended base hash.
(A) Joint election public key
(B) Extended base hash
Variable  Meaning  Folder  File  Level 

\(\bar{Q}\)  extended base hash  Root  context.json  crypto_extended_base_hash 
\(K\)  joint election public key  Root  context.json  elgamal_public_key 
Correctness of Selection Encryptions
Important
An election verifier must confirm the following for each possible selection on a ballot:
The given values \(\alpha\), \(\beta\), \(a_0\), \(b_0\), \(a_1\), and \(b_1\) are all in the set \(Z_p^r\). (A value \(x\) is in \(Z_p^r\) if and only if \(x\) is an integer such that \(0 \le x \lt p\) and \(x^q \bmod p=1\) is satisfied.)
(J) The challenge \(c\) is correctly computed as
(K) The given values \(c_0\), \(c_1\), \(v_0\), and \(v_1\) are each in the set \(Z_q\). (A value \(x\) is in \(Z_q\) if and only if \(x\) is an integer such that 0 \le x \lt q.)
(L) The equation
is satisfied.
(M) The equation
is satisfied.
(N) The equation
is satisfied.
(O) The equation
is satisfied.
(P) The equation
is satisfied.
Variable  Meaning  Folder  File  Level 

\((\alpha,\beta)\)  encryption of vote  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) ciphertext \(\rightarrow\) pad, data 
(a_0,b_0)  commitment to vote being an encryption of zero  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_zero_pad, proof_zero_data 
\((a_1,b_1)\)  commitment to vote being an encryption of one  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_one_pad, proof_one_data 
\(c\)  challenge  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_challenge 
\(c_0\)  derived challenge to encryption of zero  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_zero_challenge 
\(c_1\)  derived challenge to encryption of one  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_one_challenge 
\(v_0\)  response to zero challenge  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_zero_response 
\(v_1\)  response to one challenge  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) proof_one_response 
Adherence to Vote Limits
Important
An election verifier must confirm the following for each contest on the ballot:
(H) The number of placeholder positions matches the contest’s selection limit \(L\).
(I) The contest total \((A,B)\) satisfies
and
where the \((\alpha_i,\beta_i )\) represent all possible selections (including placeholder selections) for the contest.
(J) The given value \(V\) is in \(Z_q\).
(K) The given values a and b are each in \(Z_p^r\).
(L) The challenge value \(C\) is correctly computed as
(M) The equation
is satisfied.
(N) The equation
is satisfied.
Variable  Meaning  Folder  File  Level 

\((\alpha_i,\beta_i)\)  encryption of \(i^th\) vote in contest  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) ciphertext \(\rightarrow\) pad, data 
\((A,B)\)  encryption of total votes in contest  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) total \(\rightarrow\) pad, data 
\((a,b)\)  commitment to vote being an encryption of one  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) total \(\rightarrow\) proof \(\rightarrow\) pad, data 
\(C\)  selection limit challenge  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) challenge 
\(L\)  contest selection limit  root  description.json  contests \(\rightarrow\) [Item] \(\rightarrow\) votes_allowed 
\(V\)  response to selection limit challenge  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) response 
Validation of Ballot Chaining
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.
(D) The equation \(H_0=H(\bar{Q})\) is satisfied.
(E) For each ballot
is satisfied.
(F) The closing hash
is correctly computed from the final tracking code \(H_l\).
Variable  Meaning  Folder  File  Level 

\(H_i\)  running hash of ballots produced  encrypted_ballots  every file in this folder  tracking_hash (also previous_tracking_hash) 
Correctness of Ballot Aggregation
Important
An election verifier must confirm for each (nonplaceholder) option in each contest in the ballot coding file that the aggregate encryption \((A,B)\) satisfies
and
where the \((\alpha_j,\beta_j )\) are the corresponding encryptions on all cast ballots in the election record.
Variable  Meaning  Folder  File  Level 

\((\alpha_j,\beta_j)\)  encryption of vote  encrypted_ballots  every file in this folder  contests \(\rightarrow\) [Item] \(\rightarrow\) ballot_selections \(\rightarrow\) [Item] \(\rightarrow\) ciphertext \(\rightarrow\) pad, data 
\((A,B)\)  encrypted aggregate total of votes in contest  root  tally.json  [prefix] \(\rightarrow\) message \(\rightarrow\) pad, data 
Correctness of Partial Decryptions
Important
An election verifier must then confirm for each (nonplaceholder) option in each contest in the ballot coding file the following for each decrypting trustee \(T_i\).
The given value \(v_i\) is in the set \(Z_q\).
The given values \(a_i\) and \(b_i\) are both in the set \(Z_q^r\).
The challenge value \(c_i\) satisfies
The equation
is satisfied.
The equation \(A^{v_i} \bmod p=(b_i M_i^{c_i} ) \bmod p\) is satisfied.
Correctness of Partial Decryptions
Important
An election verifier must then confirm for each (nonplaceholder) option in each contest in the ballot coding file the following for each decrypting trustee \(T_i\).
(F) The given value \(v_i\) is in the set of \(Z_q\)
(G) The given values \(a_i\) and \(b_i\) are both in the set \(Z_q^r\).
(H) The challenge value \(c_i\) satisfies
(I) The equation
is satisfied.
(J) The equation
is satisfied.
Variable  Meaning  Folder  File  Level 

\((A,B)\)  encrypted aggregate total of votes in contest root  tally.json  [prefix] \(\rightarrow\) message \(\rightarrow\) pad, data  
\(M_i\)  partial decryption of \((A,B)\) by guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) share 
\((a_i,b_i)\)  commitment by guardian \(T_i\) to partial decryption of \((A,B)\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) pad, data 
\(c_i\)  challenge to partial decryption of guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) challenge 
\(v_i\)  response to challenge of guardian \(T_i\)  root tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) proof \(\rightarrow\) response 
Correctness of Substitute Data for Missing Guardians
Note
This is only necessary if some guardians are missing during tallying
Important
An election verifier must confirm for each (nonplaceholder) option in each contest in the ballot coding file the following for each missing trustee \(T_i\) and for each surrogate trustee \(T_\ell\).
(A) The given value \(v_{i,l}\) is in the set \(Z_q\).
(B) The given values \(a_{i,l}\) and \(b_{i,l}\) are both in the set \(Z_q^r\).
(C) The challenge value \(c_{i,l}\) satisfies
(D) The equation
is satisfied.
(E) The equation
is satisfied.
Variable  Meaning  Folder  File  Level 

\((A,B)\)  encrypted aggregate total of votes in contest  root  tally.json  [prefix] \(\rightarrow\) message \(\rightarrow\) pad, data 
\(M_(i,\ell)\)  share of guardian \(T_\ell\) of missing partial decryption of \((A,B)\) by guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) substitute_proof \(\rightarrow\) [item] \(\rightarrow\) share 
\((a_{i,l},b_{i,l})\)  commitment by guardian \(T_\ell\) to share of partial decryption for missing guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) substitute_proof \(\rightarrow\) [item] \(\rightarrow\) pad, data 
\(c_{i,\ell}\)  challenge to guardian \(T_\ell\) share of missing partial decryption of guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) substitute_proof \(\rightarrow\) [item] \(\rightarrow\) challenge 
\(v_{i,l}\)  response to challenge of guardian \(T_\ell\) share of partial decryption of guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) substitute_proof \(\rightarrow\) [item] \(\rightarrow\) response 
Correctness of Construction of Replacement Partial Decryptions
Note
This is only necessary if some guardians are missing during tallying
Important
An election verifier should confirm that for each trustee \(T_\ell\) serving to help compute a missing share of a tally, that its Lagrange coefficient \(w_\ell\) is correctly computed by confirming the equation
An election verifier should then confirm the correct missing tally share for each (nonplaceholder) option in each contest in the ballot coding file for each missing trustee \(T_i\) as
Variable  Meaning  Folder  File  Level 

\(w_\ell\)  coefficient for use with shares of guardian \(T_\ell\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [item] \(\rightarrow\) coefficient 
\(M_{i,\ell}\)  share of guardian \(T_\ell\) of missing partial decryption of \((A,B)\) by guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) substitute_proof \(\rightarrow\) [item] \(\rightarrow\) share 
\(M_i\)  partial decryption of \((A,B)\) by guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) share 
Validation of Correct Decryption of Tallies
Important
An election verifier should confirm the following equations for each (nonplaceholder) option in each contest in the ballot coding file.
(C)
(D)
An election verifier should also confirm that the text labels listed in the election record match the corresponding text labels in the ballot coding file.
Variable  Meaning  Folder  File  Level 

\(M_i\)  partial decryption of \((A,B)\) by guardian \(T_i\)  root  tally.json  [prefix] \(\rightarrow\) shares \(\rightarrow\) [Item] \(\rightarrow\) share 
(M)  full decryption of \((A,B)\)  root  tally.json  [prefix] \(\rightarrow\) value 
\(t\)  tally value  root  tally.json  [prefix] \(\rightarrow\) tally 
Validation of Correct Decryption of Spoiled Ballots
Important
An election verifier should confirm the correct decryption of each spoiled ballot using the same process that was used to confirm the election tallies.
An election verifier should also confirm that for each decrypted spoiled ballot, the selections listed in text match the corresponding text in the ballot coding file.
Validation of Correct Decryption of Spoiled Ballots is a repeat of verification steps 8 through 11 for each spoiled ballot instead of for the aggregate ballot that contains encrypted tallies

Special thanks to Rainbow Huang (@rainbowhuanguw) for her help in producing this mapping. ↩

In general, if \(n\) is prime, one can compute \(a^b \bmod n\) as \((a \bmod n)^{(b \bmod (n1)} ) \bmod n\). But within this application, the efficiency benefits of performing a modular reduction on an exponent are limited, and the risk of confusion or error from doing so likely exceeds the benefit. In the particular instance of this specification, if \(a \in Z_p^r\), then one can compute \(a^b \bmod p\) as \(a^{(b mod q)} \bmod p\). This has greater efficiency benefits, but the risk of confusion or error still likely exceed the efficiency benefit. ↩

If alternative parameters are allowed, election verifiers must confirm that \(p\), \(q\), \(r\), \(g\), and $\bar{g} are such that both \(p\) and \(q\) are prime (this may be done probabilistically using the MillerRabin algorithm), that \(p1=qr\) is satisfied, that \(q\) is not a divisor of \(r\), and \(1 \lt g \lt p\), that \(g^q \bmod p=1\), that \(g \bar{g} \bmod p=1\), and that generation of the parameters is consistent with the cited standard. ↩