0.95 Specification comments

[rc-ms]

As we prepare for the next rev of the ElectionGuard Specification, we opened this thread for anyone to offer feedback to make it more understandable, accessible, or address any missing features or capabilities.
0.95 Specification

[vteague]

I have a bunch of mostly-minor suggestions for making it a bit clearer.

Overview:

ln 14:

2. Voters and observers can verify that the recorded votes have been accurately counted.

Suggest "... that all the recorded votes have been accurately counted"

ln 16:

ElectionGuard is compatible with ... even with Internet voting.

I don't think "compatible with" quite captures the relationship with Internet voting here, in particular it doesn't make it clear that the RLA functionality and the expected (printout-based) cast-as-intended mechanism are both incompatible with Internet voting, nor the problem of not having receipt freeness.

You could expand on this a bit in the Applicability chapter, in particular the distinction between "Election Guard's e2e-v can be used over the Internet (if you write your own cast-as-intended verification step)" and "ElectionGuard constitutes a secure solution for running elections over the Internet," which I don't think you're claiming.

ln 22:

"... ballots that can matched directly ... "

should be "... ballots that can be matched directly ... "

Structure

ln 21:

"* $ℤ_\eta = {0, 1, 2, \dots , n − 1}$ is the additive group of the integers modulo $p$."

Pick one of $\eta$, $n$, or $p$.

ln 23:

"... then $Z_r^p$ is an order $q$ cyclic subgroup ... "

should be $Z^r_p$

ln 30:

"A generator $g$ of the order $q$ subgroup $Z_r^p$ is also fixed. "

Ditto.

Also, at the risk of being a complete pedant, the pretty $ℤ$ character has disappeared.

ln 63: Footnote 7 (ref 9) points to (a duplicate of) the Fiat-Shamir paper but should point to "Cramer, R., Damgård, I. and Schoenmakers, B., 1994, August. Proofs of partial knowledge and simplified design of witness hiding protocols. In Annual International Cryptology Conference (pp. 174-187). Springer, Berlin, Heidelberg."

Baseline Parameters

ln 7:

"256-bit prime $q = 2256 − 189$."

Should be $q = 2^{256} − 189$.

ln 25:

"The hexadecimal representation of $q$ is as follows:"

Should be $p$.

ln 31:

"The hexadecimal representation of the cofactor $r=p-1$ is as follows:"

Should be $r = (p-1)/q$.

ln 37:

"Finally, the generator $g$ is chosen to be $g=2r \bmod p$"

I think it should be $g = 2^r \bmod p$.

ln 47:

An ElectionGuard version 1 election verifier may assume that
the baseline parameters match the parameters provided above.

I haven't thought about this hard, but "assume" may be too ambiguous to be OK. In particular, I think you mean "hardcode and use these parameters" but a naive verifier-implementer might think it's OK to accept any parameters (i.e. "assuming" that they are the standard parameters, without checking) and might be tricked, for example by a malicious prover who sets $g=1$.

[JohnLCaron]

Being an example of a "naive verifier-implementer", I started to write an implementation that would actually allow alternative baseline parameters. Now I see that will require a big refactoring, because in fact the code everywhere assumes those parameters. So Im going to just check that the election parameters are the standard ones.

Perhaps withdraw any mention of verifiers needing to think about alternative parameters, other than mentioning thats a possibility in a future specification?

[JohnLCaron]

I know that someone has worked hard to put the spec on-line, but I really like having an elegantly formatted hard-copy pdf that I can print out and work against. I hope when the dust settles, the web version can be reformed into such a printable document. Printed versions of web pages are so much less, um, elegant. And, thanks, the on-line version is also very useful.

[rc-ms]

Thanks you @vteague for your comments. I'll work to incorporate the typos and will work to make sure no unadorned Z is let loose. And @JohnLCaron the pdf version of the 0.95 spec is here. We wanted to migrate the core spec itself into markdown and Github to make tracking diffs and editing/contributing easier and provide a canonical "code" version. I'll make sure we investigate some kind of mechanism to generate pretty PDFs as well

[JohnLCaron]

Thanks, just making pitch that when the changes are done, a pretty pdf gets made.

[JohnLCaron]

Comments on Section 9 Verifier Construction

• Section Numbering. Its very useful to be able to reference the specific validation equations / paragraphs, so adding section numbers (as in the pdf) as before would be good.

4. Correctness of Selection Encryptions

• Sublists starting at (J) should be starting at (A).

• "A value x is in Z_p^r if and only if x is an integer such that 0 ≤ x < p and x^q mod p = 1 is satisfied."

should be

"A value x is in Z_p^r if and only if x is an integer such that 0 < x < p and x^q mod p = 1 is satisfied."

5. Adherence to Vote Limits

• Sublists starting at (H) should be starting at (A).

6. Validation of Ballot Chaining

• Sublists starting at (D) should be starting at (A).

• 6.B H_i = H(H_i−1, D, T, B_i )

  1. Add D to the definition table. pdf p 19 has "where D consists of the voting device information described above", but I dont see that anywhere, and its currently not implemented.
  2. Add T to the definition table. pdf p 19 has "T is the date and time of ballot encryption" which isnt well defined. In implementing, one just uses whatever is in the election record for that ballot, CiphertextAcceptedBallot.timestamp. Currently thats an int64, "tics since the unix epoch", time zone unclear, but UTC is a good choice.
  3. Add B_i to the definition table. pdf p 19 has "B_i is an ordered list of the individual encryptions on the ballot – with the ordering as specified by the ballot coding file". Currently the implementation uses CiphertextAcceptedBallot.crypto_hash, which might be this definition? And begs the question as to whether the verifier needs to independently calculate that quantity, rather than use whatever is in the election record.

8. Correctness Partial Decryptions

• Add equation numbering starting at (A).

• "(B) The given values a_i and b_i are both in the set Z_q^r."

should be:

"(B) The given values a_i and b_i are both in the set Z_p^r."

9. Correctness of Substitute Data for Missing Guardians

• Sublists starting at (F) should be starting at (A).

• "(B) The given values a_i and b_i are both in the set Z_q^r."

should be:

"(B) The given values a_i and b_i are both in the set Z_p^r."

10. Correctness of Construction of Replacement Partial Decryptions

• Add equation numbering (A) and (B).

• Add U to the definition table. Something like "U is the set of polynomial x_i values, one for each of the available guardians. Note that these must be greater than 0."

12. Validation of Correct Decryption of Spoiled Ballots

• Add paragraph numbering (A) and (B).

• This header is not showing up on the right sidebar contents list.

[nickboucher]

Academic Review of ElectionGuard Specification

Attached to this post are the results from my most recent academic review of the specification. Comments are placed directly on the PDF and Word Doc, respectively. This review was also sent via email, but I'm including it here for centralized tracking:

ElectionGuard Specification v0.95 - Boucher Review
Verifier Construction Guide - Boucher Review

Verifier

The comments raised in the attached documents are also included as warnings in the output of a verifier that I wrote in Python. Here is an example of the verifier's current warnings, for reference:

As these issues are resolved, or if they are shown to be invalid, please communicate as such to me and I will update the verifier warnings respectively.

Change Log

On a related note, if it's possible to create a change log document that tracks changes to the specification, that would be very useful for maintainers of verifiers.

[rc-ms]

thank you @vteague @nickboucher and @JohnLCaron ! This is awesome

[benaloh]

Yup. These are all legit typos and good suggestions for clarification. Note that some of the typos seem to be a result of the transcription from the pdf of v0.95 to the online GitHub version, so we'll need to get these harmonized as we move forward.

[JohnLCaron]

https://www.electionguard.vote/spec/0.95.0/4_Key_generation/

Details of Key Generation

Each guardian T i  in an election with a decryption threshold of  generates  secret polynomial  coefficients  such that  and  and forms the polynomial

  P i (x) = ∑ a i,j x j mod q.

Guardian T i  then publishes commitments  for each of its random polynomial coefficients. 
The constant term  a i,0  of this polynomial will serve as the private key for guardian T i , and will also be denoted as K i = K i,0 .

the last sentence should read some variant of:

The constant term a i,0 of this polynomial will serve as the private key for guardian
T i , and for convenience we denote s i = a i,0 , and its commitment K i,0 will serve as the public
key for guardian T i and will also be denoted as K i = K i,0 .

Otherwise it reads as if the coefficient a i,0 = Ki, instead of its committment = Ki,.

[JohnLCaron]

https://www.electionguard.vote/spec/0.95.0/9_Verifier_construction/#adherence-to-vote-limits

Adherence to Vote Limits

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

for clarity, could be:

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

[JohnLCaron]

https://www.electionguard.vote/spec/0.95.0/4_Key_generation/

An election verifier must verify the correct computation of the joint election public key (A) and extended base hash (B).

(A) Joint election public key

Q̅ = H(Q, K 1,0 , K 1,1 , K 1,2 , ... , K 1,k−1 , K 2,0 , K 2,1 , K 2,2 , ... , K 2,k−1 , ... , K n,0 , K n,1 , K n,2 , ... , K n,k−1 )

(B) Extended base hash

K = ∏ ni=1 K i mod p.

Labels are reversed, should be

(A) Joint election public key

K = ∏ ni=1 K i mod p.

(B) Extended base hash

Q̅ = H(Q, K 1,0 , K 1,1 , K 1,2 , ... , K 1,k−1 , K 2,0 , K 2,1 , K 2,2 , ... , K 2,k−1 , ... , K n,0 , K n,1 , K n,2 , ... , K n,k−1 )

[JohnLCaron]

https://www.electionguard.vote/spec/0.95.0/4_Key_generation/

To share secret values amongst each other, it is assumed that each guardian T_i has previously shared 
an auxiliary public encryption function E_i with the group.[^3]
After verifying (A) and (B) for all other trustees,
each guardian T_i then publishes the encryption E_l ( R_i,l, P_i(l))  for every other guardian T_l – 
where R_i,l is a random nonce.

The meaning of R_i,l is confusing. AFAICT, this is T_l auxiliary public key? Theres no other random nonce used in generating the partial key backup. In which case I guess its just R_l, not R_i,l. And the E is the same for all guardians, but I guess youre trying to be general?

Maybe this is clearer:

To share secret values amongst each other, it is assumed that each guardian T_i has previously shared 
an auxiliary public encryption function E_i with the group.[^3]
After verifying (A) and (B) for all other trustees,
each guardian T_i then publishes the encryption E_i(R_l, P_i(l))  for every other guardian T_l, 
where R_l is the auxiliary public key of T_l.

[JohnLCaron]

Just below we have another reference to the nonce:

If the recipient guardian T_l reports not receiving a suitable value P_i(l), it becomes incumbent on the
sending guardian T_i to publish this P_i(l) together with the nonce R_i,l it used to encrypt P_i(l).

I dont see any such nonce, so not sure what Im missing, of if the spec if just out of sync with the code.

[benaloh]

You're right, I believe that this is a vestige of an earlier approach in which the shares were encrypted with ElGamal. While it would be nice to have a challenged guardian provide any randomness used to encrypt challenged shares with the challenger's auxiliary public key -- as this would allow observers to determine which of the challenging guardian or the challenged guardian has misbehaved, it isn't required. It is sufficient for the challenged guardian to simply publish the challenged shares.

If the challenged shares are consistent with the share commitments (the public coefficients), then the process can proceed -- even though we may never know who acted improperly. If the challenged guardian does not publish shares that match the commitments, then we know that this guardian is misbehaving and must be excluded.