TODO.txt

====vvvv====vvvv====vvvv====vvvv====vvvv==== DONE ====vvvv====vvvv====vvvv====vvvv====vvvv====

electionguard.exe: common parameter: election filesystem directory to look for files (%ELECTIONGUARD_ARTIFACTS_DIR%)
electionguard.exe: seed: write random seed to artifact file
electionguard.exe manifest: write ElectionManifest to pretty json file
electionguard.exe manifest: write ElectionManifest to canonical bytes file
electionguard.exe parameters: write ElectionParameters to json file
H_V, H_P, H_M, and H_B updated for 2.0 calculation
Generate joint election public key
Extended base hash H_E
electionguard-test script: implementation in cmd started
electionguard-test script: implementation in cmd exercises all (current) functionality
BigUint values (mod p or q) now left-padded as necessary to avoid leaking value via serialized file size
Hash values now serialized with 'H(upper hex)' format to match spec
exe: Csprng now seeded with more entropy from the operating system RNG
Election-varying parameters (n and k) now checked for validity
Serialization of BigUints now uses base64 encoding
Rename guardian private key to secret key
electionguard.exe: generate guardian secret key
electionguard.exe: write guardian secret key
electionguard.exe: derive guardian public key from secret key
electionguard.exe: write guardian public key
Guardian i uses 1-based indexing
compute H_E extended base hash
compute joint election public key
electionguard.exe: write joint election public key to json file
standardize on 'validate' instead of 'verify' when checking deserialized structures
instead of from_json and to_json implement from_stdioread and to_stdiowrite
every struct that has Self::from_stdioread*() should prefer Self::from_stdioread_validated() and have a self.validate()
electionguard.exe: write H_E extended base hash to json file
convert many uses of if !() { bail!() } to ensure!()
Generate data structure docs from the Reference Implementation in Rust
eg: New constrained numeric type for indices. Convert n, k, and other indices to this type.
build-docs script: initial implementation in cmd
evaluate scripting language 'nu' https://www.nushell.sh/
electionguard-test script: begin rewrite in nu
doc/LICENSE: checked
doc/SECURITY.md: complete
docs/general: begin writing
docs/api: begin writing
Remove link to internal site
VaryingParameters: enum BallotChaining { Prohibited, Allowed, Required, }
remove old EG 1.54 constants
exe: Under artifacts dir, first level dirs are specific to secrecy requirements
Ballot define data type
get fixeduint stuff out of bunna branch
Merge code from Anunay
doc/SUPPORT.md: complete
doc/README.md: complete
doc/CODE_OF_CONDUCT.md: complete
doc/BUILDING.md: complete
Complete all planned code reorganization/renaming
docs/implementation guide/References: complete
a trait for fn to_canonical_json()
many to_stdiowrite() methods have common code that could be factored into a common function
a trait for types that have to_stdiowrite()
a trait for types that have to_stdiowrite() and perhaps _pretty() and _canonical() variants

====^^^^====^^^^====^^^^====^^^^====^^^^==== DONE merged to main ====^^^^====^^^^====^^^^====^^^^====^^^^====

Add .errorviz-version to .gitignore
incorporate the latex of egds2.0 into todo.txt
add todo.txt to repo
serialize bignums only all as uppercase hex
serialize bignums includes base e.g., "base16:f81e2b3..."

====^^^^====^^^^====^^^^====^^^^====^^^^==== locally committed ====^^^^====^^^^====^^^^====^^^^====^^^^====

====vvvv====vvvv====vvvv====vvvv====vvvv==== TODO general ====vvvv====vvvv====vvvv====vvvv====vvvv====

UG left pad as necessary to ensure length is correct
serialize format wrapped in version

ensure SecretCoefficient is serialized in a fixed-length format

Election parameters: add a type field initally set to 'HomomorphicTallying'

[Security: out of scope] TOCTOU bug with --insecure-deterministic flag electionguard.exe main.rs. Should be fixed, but in practice if that filesystem is writable by a malicious party then you likely have much, much bigger concerns.

build-docs script: finish rewrite in nu

electionguard-test script: incorporate ballots
electionguard-test script: incorporate tally

Build on Linux64

Test on Linux64

new electionguard-testdata.exe tool example_election_manifest
new electionguard-testdata.exe tool generates test data, example_election_manifest
new electionguard-testdata.exe tool does validate-standard-parameters

docs/general: style sheet for markdown, ideally match API docs

If an overvote occurs, the overvote must be captured, encrypted, and never decrypted.

docs/specs/serialization: data formats section
docs/specs/serialization: standards and references section
docs/specs/serialization: election manifest section
docs/specs/serialization: election record section
docs/specs/serialization: vendor data section

docs/implementation guide/Requirements for election systems vendors: complete
docs/implementation guide/Requirements for verifier app authors: complete
docs/implementation guide/roles: consider splitting into separate pages: complete
docs/implementation guide/roles/Election Administrator: complete
docs/implementation guide/roles/Election Guardians: complete
docs/implementation guide/roles/Voters: complete
docs/implementation guide/roles/Political parties and voter-interest organizations: complete
docs/implementation guide/roles/Journalists and other media: complete
docs/implementation guide/Hardware requirements/Gurardian secret key storage: complete
docs/implementation guide/Hardware requirements/Gurardian secret key operations: complete
docs/implementation guide/step-by-step/Advance preparation: complete
docs/implementation guide/step-by-step/Key ceremony: complete
docs/implementation guide/step-by-step/Tally ceremony: complete
docs/implementation guide/step-by-step/Publishing: complete
docs/implementation guide/step-by-step/Verification: complete
docs/implementation guide/step-by-step/Reporting: complete

docs/api: use correct logo
docs/api: complete

docs: complete, #![warn(missing_docs)]

doc: upload docs to github pages (see compliance notes)

security review: ensure that no file leaks info through filesize

====----====----====----====----==== milestone: "alpha" release ====----====----====----====----====

alpha testing

====----====----====----====----==== milestone: "beta" release ====----====----====----====----====

beta testing

#![warn(missing_doc_code_examples)]
#![warn(missing_debug_implementations)]
#![warn(missing_copy_implementations)]
#![warn(unused_doc_comments)]

distinguish between PartySelection, BallotMeasureSelection, CandidateSelection

open issues for any remaining TODO items for 1.0

====----====----====----====----==== milestone: "1.0" release ====----====----====----====----====

BallotDefinition doc for write-in option

would be nice to support a PartySelection type vote, rather than rely on the vendor to give us the correct selections explicitly

a trait for types that have pub fn validate(&Self)
a trait for types that have pub fn validate(&Self, &ElectionParameters)

docs: more investigation into using rust modules to build documentation along with api, observe how cargo_crev does it with the include_str! macro: https://github.com/crev-dev/cargo-crev/blob/master/cargo-crev/src/doc/mod.rs
docs: more investigation into using mdbook for all project documentation https://github.com/rust-lang/rust/issues/66249
docs: cargo-external-doc is nice but doesn't support virtual manifests https://github.com/Geal/cargo-external-doc

VaryingParameters (n, k) This isn't really an 'index' (ordinal), it's a cardinal number. Maybe we need a general purpose ranged number type.

exe: common parameter: election filesystem directory to look for files (%ELECTIONGUARD_ARTIFACTS_DIR%)
exe: common parameter: manifest file
exe: common parameter: others

exe: create artifact directories if they don't exist. q: what about permissions on guardian secret directories?

exe: read guardian secret key, print info, suppressing secrets in secret key
exe: read guardian public key, print info

Proof of valid decryption

design: document
design: define standard election directory layout - look at other implementers and users
design: key file represents its kind: guardian, ..., ?

Consider structures defined in JSON schema https://github.com/usnistgov/ElectionResultsReporting/blob/version2/NIST_V2_election_results_reporting.json

if electionguard.exe fails to read or write a file, check the path to see if it has a leading ~. If so, print a good error message.

test on 32-bit target such as x86 or wasm32
test on big-endian target such as powerpc64-unknown-linux-gnu, s390x-unknown-linux-gnu, riscv64gc-unknown-linux-gnu, or loongarch64-unknown-linux-gnu

docs/api: reference NIST CDF where types clearly correspond. E.g., BallotStyle https://github.com/usnistgov/ElectionResultsReporting/blob/nist-pages/index.md#17_0_2_4_78e0236_1389366224561_797289_2360

====vvvv====vvvv====vvvv====vvvv====vvvv==== TODO EG 2.0 Design Specification text ====vvvv====vvvv====vvvv====vvvv====vvvv====

Abbreviations:

RI Reference Implementation
OI Other implementation


%%%%%%%%%%%%% The plan here is to chop up the specification text and extract statements that can be translate into test cases

\pagebreak

\tableofcontents

\pagebreak

-------- Section 1

\section{Introduction}
This document describes the cryptographic details of the design of \EG which can be used in conjunction with many new and existing voting systems to enable both end-to-end (E2E) verifiability and privacy-enhanced risk-limiting audits (RLAs). \EG is not a complete election system.  It instead provides components that are designed to be flexible and to promote innovation by election officials and system developers. When properly used, it can promote voter confidence by empowering voters to independently verify the accuracy of election results.

---- S1a
\subsubsection*{End-to-end (E2E) verifiability}
An E2E-verifiable election provides artifacts which allow voters to confirm that their votes have been accurately recorded and counted. Specifically, an election is End-to-end (E2E) verifiable if two properties are achieved.
\begin{enumerate}
\item Individual voters can verify that their votes have been accurately recorded.
\item Voters and observers can verify that all recorded votes have been accurately counted.
\end{enumerate}
An E2E-verifiable tally can be used as the primary tally in an election or as a verifiable secondary tally alongside traditional methods. \EG is compatible with in-person voting -- either using an electronic ballot-marking device or an optical scanner capable of reading hand-marked or machine-marked ballots, with voting by mail, and even with Internet voting\footnote{
Note that there are many challenges to responsible Internet voting that are mitigated but not fully solved by E2E-verifiability.  The 2015 U.S. Vote Foundation report at https://www.usvotefoundation.org/E2E-VIV details many of these issues, and the 2018 National Academies report at https://nap.nationalacademies.org/catalog/25120/securing-the-vote-protecting-american-democracy includes a section on Internet voting (pp. 101--105).
}.

---- S1b
\subsubsection*{Risk-limiting audits (RLAs)}
RLAs offer election administrators efficient methods to validate reported election tallies against physical ballot records. There are several varieties of RLAs, but the most efficient and practical are \emph{ballot-comparison audits} in which electronic \emph{cast-vote records} (CVRs) are individually compared against physical ballots.

The challenge with ballot-comparison audits is that public release of the full set of CVRs can compromise voter privacy while an audit without public disclosure of CVRs offers no basis for public confidence in the outcome. \EG can bridge this gap by enabling public disclosure of encrypted ballots that can be matched directly to physical ballots selected for auditing and can also be proven to match the reported tallies.

---- S1c
\subsubsection*{About this specification}
This specification can be used by expert reviewers to evaluate the details of the \EG process and by independent parties to write \EG implementations. This document is not intended to be a fully detailed implementation specification. It does not specify serialization and data structures for the election record or mappings between the notation used here and the corresponding data types and components of a specific implementation. However, this document, together with a detailed implementation specification or a well-documented \EG implementation, can be used by independent parties to write \EG verifiers to confirm the consistency of election artifacts with announced election results. 

S1 Individual voters can verify that their votes have been accurately recorded.
S1 Voters and observers can verify that all recorded votes have been accurately counted.
S1 An E2E-verifiable tally can be used as the primary tally in an election sor as a verifiable secondary tally alongside traditional methods.
S1 ElectionGuard is compatible with in-person voting using an electronic ballot-marking device
S1 ElectionGuard is compatible with in-person voting using an optical scanner capable of reading hand-marked ballots
S1 ElectionGuard is compatible with in-person voting using an optical scanner capable of reading machine-marked ballots
S1 ElectionGuard is compatible with with voting by mail
S1 ElectionGuard is compatible with with Internet voting
S1 ElectionGuard can enable public disclosure of encrypted ballots that can sbe matched directly to physical ballots selected for auditing
S1 ElectionGuard can enable public disclosure of encrypted ballots that can be proven to match the reported tallies.


-------- Section 2

%pagebreak
---- S2a
\section{Overview}

This section gives a very brief and high-level overview of the \EG system's functionality and how it can be used during an election or in a post-election audit such as an RLA.

To use \EG in an election, a set of \emph{guardians} is enlisted to serve as trustees who manage cryptographic keys.  The members of a canvassing board can serve as guardians.  Prior to the commencement of voting or auditing, the guardians work together to form a public encryption key that will be used to encrypt individual ballots.

After the conclusion of voting or auditing, a \emph{quorum} of guardians is necessary to produce the artifacts required to enable public verification of the tally.

S2a A quorum of guardians can produce the artifacts required to enable public verification of the tally.
S2a A quorum of guardians is necessary to produce the artifacts required to enable public verification of the tally.

---- S2b
\subsubsection*{Key generation}
Prior to the start of voting (for an E2E-verifiable election) or auditing (for an RLA), the election guardians participate in a process wherein they generate public keys to be used in the election. Each guardian generates its own public-secret key pair.  These public keys will be combined to form a single public key with which votes are encrypted. They are also used individually by guardians to exchange information about their secret keys so that the election record can be produced after voting or auditing is complete -- even if not all guardians are available at that time.

The key generation ceremony begins with each guardian publishing its public keys together with proofs of knowledge of the associated secret keys.  Once all public keys are published, each guardian uses each other guardian's public key to encrypt shares of its own secret keys. Finally, each guardian decrypts the shares it receives from other guardians and checks them for consistency.  If the received shares verify, the receiving guardian announces its completion.  If any shares fail to verify, the receiving guardian challenges the sender.  In this case, the sender is obliged to reveal the shares it sent. If all challenged guardians release their challenged shares and these shares all verify, the ceremony concludes and the election proceeds. If a challenged guardian fails to produce key shares that verify, that guardian is removed and the key generation ceremony restarts with a replacement guardian.

S2b Each guardian generates its own public-secret key pair.
S2b The guardian public keys can be combined to form a single public key
S2b The single public key can encrypt votes.
S2b The guardian public keys can be used individually by guardians to exchange information about their secret keys enabling the election record tob be produced after voting or auditing is complete
S2b The guardian public keys can be used individually by guardians to exchange information about their secret keys enabling the election record tob be produced after voting or auditing is complete even if not all guardians are available at that time
S2b Each guardian can publish their public keys together with proofs of knbowledge of the associated secret keys.
S2b Each guardian can use each other guardian's public key to encrypt shares ofb its own secret keys
S2b Each guardian can decrypt the shares it receives from other guardians
S2b Each guardian can check the decrypted shares for consistency
S2b A guardian sender can reveal the shares it sent
S2b If all challenged guardians release their challenged shares and these shbares all verify, the ceremony can conclude and the election proceed.
S2b A guardian can be removed if they are challenged and fail to produce key shbares that verify
S2b the key generation ceremony can be restarted with a replacement guardian.

---- S2c
\subsubsection*{Ballot encryption}
In most uses, the election system makes a single call to the \EG API after each voter completes the process of making selections or with each ballot to be encrypted for an RLA. \EG will encrypt the selections made by the voter and return a confirmation code which the system should give to the voter.\footnote{The confirmation code is not necessary for RLA usage.} 

This is the only point where an existing election system must interface with \EG. In most uses of \EG, voters will have an opportunity to challenge their encrypted ballots and view their decryptions to ensure that the encryptions are correct.\footnote{A ballot that has been decrypted should be regarded as a test ballot and should not be included in an election tally. After a ballot is challenged, the voter should have an opportunity to cast a fresh ballot.  In an E2E-verifiable election, a decypted ballot should never be cast.  However, in an RLA, some anonymized cast ballots may ultimately be challenged and decrypted.}
In certain vote-by-mail scenarios and when \EG is used within an RLA, cast-vote records can be provided in batch without any interface between the voting equipment and \EG. 

The encrypted ballots are published along with non-interactive zero-knowledge (NIZK) proofs of their well-formedness. The proofs assert that an encrypted ballot is well-formed, which means that it is a legitimate ballot and adheres to the limits imposed on selection options and contests. For example, they prove that a selection did not receive more votes than allowed and that no more than the allowed number of votes were received across the selection options in each contest. The encryption method used herein has a homomorphic property which allows the encrypted ballots to be combined into a single aggregate ballot which consists of encryptions of the election tallies.

S2c The election system can make a single call to the ElectionGuard API after each voter completes the process of making selections
S2c The election system can make a single call to the ElectionGuard API with each ballot to be encrypted for an RLA.
S2c ElectionGuard will encrypt the selections made by the voter and return a confirmation code for the system to give to the voter after they complete the process of making selections. (not relevant to RLA scenario)
S2c No other point at which an existing election system must interface with EG is required.
S2c Voters will have an opportunity to challenge their encrypted ballots and view their decryptions to ensure that the encryptions are correct.
S2c A decypted ballot should never be cast, can EG somehow ensure this?
S2c In an RLA, some anonymized cast ballots may be challenged and decrypted.
S2c In certain vote-by-mail scenarios, cast-vote records can be provided in batch without any interface between the voting equipment and ElectionGuard. 
S2c When ElectionGuard is used within an RLA, cast-vote records can be provided in batch without any interface between the voting equipment and ElectionGuard
S2c Encrypted ballots can be published along with non-interactive zero-knowledge (NIZK) proofs of their well-formedness.
S2c The NIZK proofs assert that an encrypted ballot is a legitimate ballot
S2c The NIZK proofs assert that an encrypted ballot adheres to the limits S2c imposed on selection options
S2c The NIZK proofs assert that an encrypted ballot adheres to the limits imposed on contests
S2c The NIZK proofs prove that a selection did not receive more votes than allowed 
S2c The NIZK proofs prove that no more than the allowed number of votes were received across the selection options in each contest.
S2c The encryption method allows the encrypted ballots to be combined into a single aggregate ballot
S2c The single aggregate ballot into which the encryption method combined the encrypted ballots consists of encryptions of the election tallies.

---- S2d
\subsubsection*{Verifiable decryption}
In the final step, election guardians independently use a share of the secret decryption key, which each guardian computes from the previously shared secret key fragments, to jointly decrypt the election tallies and generate associated verification data. It is not necessary for all guardians to be available to complete this step.  If some guardians are missing, a quorum of guardians is sufficient to complete decryption and generate the verification data.

S2d Each guardian can compute from the previously shared secret key fragments a share of the secret decryption key
S2d Guardians can independently use their share of the secret decryption key to jointly decrypt the election tallies
S2d Guardians can independently use their share of the secret decryption key to generate associated verification data
S2d Only a quorum of guardians is sufficient to complete decryption
S2d Only a quorum of guardians is sufficient to generate the verification data

---- S2e
\subsubsection*{Independent verification}
Observers can use this open specification and/or accompanying materials to write independent \emph{election verifiers} that can confirm the well-formedness of each encrypted ballot, the correct aggregation of these ballots, and the accurate decryption of election tallies.

The verification of an election consists of various verification steps that can be separated into three groupings.

S2e An observer can use this open specification and/or accompanying materials to write independent election verifiers that can confirm the well-formedness of each encrypted ballot
S2e An observer can use this open specification and/or accompanying materials to write independent election verifiers that can the correct aggregation of these ballots
S2e An observer can use this open specification and/or accompanying materials to write independent election verifiers that can the accurate decryption of election tallies.

\paragraph{Verification of key generation.}
The first group of verification steps pertain to the key generation process.  Under normal circumstances, guardians will engage in a key generation ceremony and produce an election public key without controversy, and there is no need for independent verification of this process.  However, if one or more parties to the key generation ceremony complain about the process, the associated independent verification steps can help to resolve conflicts.

These steps should therefore be considered to be optional.  The integrity of an election record can be fully verified by independent parties without any of the key verification steps.  However, a ``premium'' verifier may wish to include these steps to verify the correctness of guardian actions during the key generation ceremony.

The key generation verification steps are highlighted in orange boxes.

\paragraph{Verification of ballot correctness.}
As will be described in detail below, there are instances in both the E2E-verifiability application and the RLA application where it is desirable to verifiably decrypt individual ballots.  In the former application, this allows voters to confirm that their selections have been correctly recorded within an encrypted ballot, and in the latter application, this allows encrypted electronic ballots that have been selected for audit to be compared with their associated paper ballots.

The steps required to verify the correct decryption of a ballot are grouped together to allow independent verifiers to be easily constructed whose sole purpose is to allow voters or observers to directly verify correct decryption of individual ballots.

The ballot correctness verification steps are highlighted in blue boxes.

\paragraph{Verification of election record.}
The remaining verification steps apply to the election as a whole.  These steps enable independent verification that every ballot in an election record is well-formed, that cast ballots have been correctly aggregated homorphically, and that these aggregated values have been correctly decrypted to produce election tallies.

It is critical that a complete verification of an election record also includes verification of the correct decryption of any individual ballots that have been decrypted as part of the process.  A complete election verifier must therefore incorporate an individual ballot generator as described above.

The election record verification steps are highlighted in green boxes.

---- S2f
\subsubsection*{Using this specification}
The principal purposes of this document are to specify the functionality of the \EG toolkit and to provide details necessary for independent parties to write election verifiers that consume the artifacts produced by the toolkit.


\pagebreak

-------- Section 3

---- S3a
\section{Components}\label{sec:EGcomponents}
This section describes the four principal components of \EG.
\begin{enumerate}

\item \emph{Parameter Requirements:} These are properties required of parameters to securely and efficiently instantiate the cryptographic components of ElectionGuard. These \emph{cryptographic parameters} are fixed ahead of every election and the same parameters can be used across multiple elections. A specific, recommended set of standard parameters is provided. In addition, there are properties required of the \emph{election parameters} that define the election contests, selectable options, and ballot styles, among other information.
\item \emph{Key Generation:} Prior to each individual election, guardians must generate individual public-secret key pairs and exchange shares of secret keys to enable completion of an election even if some guardians become unavailable.  Although it is preferred to generate new keys for each election, it is permissible to use the same keys for multiple elections so long as the set of guardians remains the same.  A complete new set of keys must be generated if even a single guardian is replaced.

S3a2 Guardians can generate individual public-secret key pairs
S3a2 Guardians can exchange shares of secret keys
S3a2 If the set of guardians and parameters k and n remain the same, they can re-use the same keys for multiple elections
S3a2 A complete new set of keys must be generated if k is changed
S3a2 A complete new set of keys must be generated if n is changed
S3a2 A complete new set of keys must be generated if even a single guardian is replaced
S3a2 TODO is this true?: A complete new set of keys must be generated if any of p, q, r, g is changed

\item \emph{Ballot Encryption:} While encrypting the contents of a ballot is a relatively simple operation, most of the work of \EG is the process of creating externally-verifiable artifacts to prove that each encrypted ballot is well-formed (i.e., its decryption is a legitimate ballot without overvotes or improper values).
\item \emph{Verifiable Decryption:} At the conclusion of each election, guardians use their secret key shares to jointly produce election tallies together with verifiable artifacts that prove that the tallies are correct.
\end{enumerate}

S3a3 Guardians can use their secret key shares to jointly produce election tallies together with verifiable artifacts that prove that the tallies are correct.

---- S3b
\subsubsection*{Notation}
In the remainder of this specification, the following notation will be used.
\begin{itemize}
  \item $\Z = \{\dots,-3,-2,-1,0,1,2,3,\dots\}$ is the set of integers.
  \item $\Z_n = \{0,1,2,\dots,n-1\}$ is the ring of integers modulo $n$.
  \item $\Z_n^*$ is the multiplicative subgroup of $\Z_n$ that consists of all invertible elements modulo $n$.  When $p$ is a prime, $\Z_p^* = \{1,2,3,\dots,p-1\}$.
  \item $\Z_p^r$ is the set of $r$-th-residues in $\Z_p^*$. Formally, $\Z_p^r = \{y\in\Z_p^* \mbox{ for which there exists } x\in\Z_p^* \mbox{ such that } y=x^r \bmod p\}$.  When $p$ is a prime for which $p-1=qr$ with $q$ a prime that is not a divisor of the integer $r$, then $\Z_p^r$ is an order-$q$ cyclic subgroup of $\Z_p^*$ and for each $y\in\Z_p^*$, $y\in\Z_p^r$ if and only if $y^q  \bmod p = 1$.
  \item $x\equiv_n y$ is the predicate that is true if and only if $x \bmod n=y \bmod n$.
  \item The function $\HMAC(\ ,\ )$ shall be used to denote the \HMAC-\SHA keyed Hash Message Authentication Code (as defined in NIST PUB FIPS 198-1\footnote{NIST (2008) The Keyed-Hash Message Authentication Code (HMAC). In: FIPS 198-1. \url{https://csrc.nist.gov/publications/detail/fips/198/1/final}}) instantiated with \SHA (as defined in NIST PUB FIPS 180-4\footnote{NIST (2015) Secure Hash Standard (SHS). In: FIPS 180-4. \url{https://csrc.nist.gov/publications/detail/fips/180/4/final}}). $\HMAC$ takes as input a key $k$ and a message $m$ of arbitrary length and returns a bit string $\HMAC(k,m)$ of length 256 bits.
  \item The \EG hash function $H(\ ,\ )$ is instantiated with \HMAC and thus has two inputs, both given as byte arrays. The first input to $H$ is used to bind hash values to a specific election. The second is a byte array of arbitrary length and consists of domain separation bytes and the data being hashed. $H$ outputs a digest of 256 bits, which is interpreted as a byte array of length 32. The detailed specification for $H$ is given in Section~\ref{sec:hashing} below.
  \item The symbol $\oplus$ denotes bitwise XOR.
  \item The symbol $\parallel$ denotes concatenation.
  \item In general, the variable pairs $(\alpha,\beta)$, $(a,b)$, and $(A,B)$ will be used to denote encryptions. Specifically, $(\alpha,\beta)$ will be used to designate encryptions of votes (usually an encryption of a zero or a one), $(A,B)$ will be used to denote aggregations of encryptions -- which may be encryptions of larger values, and $(a,b)$ will be used to denote encryption commitments used to prove properties of other encryptions.
\end{itemize}

---- S3c
\subsubsection*{Encryption of votes}
Encryption of votes in \EG is performed using a public key encryption method suggested by Devillez, Pereira, and Peters,\footnote{Devillez H., Pereira, O., Peters, T. (2022) \emph{How to Verifiably Encrypt Many Bits for an Election?} in ESORICS 2022 Lecture Notes in Computer Science, vol 13555.  Springer, Berlin, Heidelberg. \url{https://link.springer.com/chapter/10.1007/978-3-031-17146-8_32}} which is a variant exponential form of the ElGamal cryptosystem,\footnote{ElGamal T. (1985) \emph{A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms}. In: Blakley G.R., Chaum D. (eds) Advances in Cryptology. CRYPTO 1984. Lecture Notes in Computer Science, vol 196. Springer, Berlin, Heidelberg. \url{https://link.springer.com/content/pdf/10.1007/3-540-39568-7_2.pdf}} which is, in turn, a static form of the widely-used Diffie-Hellman(-Merkle) key exchange\footnote{Diffie W., Hellman, M. (1976) \emph{New Directions in Cryptography} IEEE Transactions on Information Theory, vol 22}.  This encryption method is called \emph{DPP vote encryption} or simply \emph{vote encryption} in this document and rests on precisely the same security basis as Diffie-Hellman(-Merkle) key exchange---which is used to protect the confidentiality of the vast majority of Internet traffic.

S3c Encryption of votes in ElectionGuard is performed using the DPP vote encryption method of Devillez, Pereira, and Peters (2022)

Primes $p$ and $q$ are publicly fixed such that $q$ is not a divisor of $r=(p-1)/q$.  A generator $g$ of the order $q$ subgroup $\Z_p^r$ is also fixed.  (Any $g=x^r \bmod p$ for which $x\in\Z_p^*$ suffices so long as $g\neq 1$.)

S3c P is fixed
S3c P is prime
S3c Q is fixed
S3c Q is prime
S3c Q is is not a divisor of r=(p-1)/q
S3c G is fixed.
S3c G is a generator $g$ of the order $q$ subgroup $\Z_p^r$

A public-secret key pair can be chosen by selecting a random $s\in\Z_q$ as a secret key and publishing $K=g^s \bmod p$ as the corresponding public key\footnote{As will be seen below, the actual public key used to encrypt votes will be a combination of separately generated public keys.  So, no entity will ever be in possession of a secret key that can be used to decrypt votes.}. 

S3c No entity is ever in possession of a secret key that can be used to decrypt votes

A message $m\in\Z_p^r$ is then encrypted by selecting a random nonce $\xi\in\Z_q$ and forming the pair $(\alpha, \beta) = (g^\xi \bmod p, K^m\cdot K^\xi \bmod p) = (g^\xi \bmod p, K^{m+\xi} \bmod p)$. An encryption $(\alpha, \beta)$ can be decrypted by the holder of the secret $s$ as $\beta/\alpha^s\bmod p = K^m \bmod p$ because
\begin{equation}
\frac{\beta}{\alpha^s} \equiv_p \frac{K^m\cdot K^\xi}{(g^\xi)^s} \equiv_p \frac{K^m\cdot (g^s)^\xi}{(g^\xi)^s} \equiv_p \frac{K^m\cdot g^{\xi s}}{g^{\xi s}} \equiv_p K^m.
\end{equation}

S3c A message $m\in\Z_p^r$ can be encrypted by selecting a random nonce $\xi\in\Z_q$ and forming the pair $(\alpha, \beta) = (g^\xi \bmod p, K^m\cdot K^\xi \bmod p) = (g^\xi \bmod p, K^{m+\xi} \bmod p)$
S3c An encryption $(\alpha, \beta)$ can be decrypted by the holder of the secret $s$ as $\beta/\alpha^s\bmod p = K^m \bmod p$

The value of $m$ can be computed from $K^m \bmod p$ as long as the message $m$ is limited to a small, known set of options.\footnote{The simplest way to compute $m$ from $K^m \bmod p$ is an exhaustive search through possible values of $m$.  Alternatively, a table pairing each possible value of $K^m \bmod p$ with $m$ can be pre-computed.  A final option which can accommodate a larger space of possible values for $m$ is to use Shanks's baby-step giant-step method as described in the 1971 paper \emph{Class Number, a Theory of Factorization and Genera}, Proceedings of Symposium in Pure Mathematics, Vol. 20, American Mathematical Society, Providence, 1971, pp. 415-440.} 

The value of $K^m$ and therefore $m$ can also be computed from the encryption nonce $\xi$, namely via $\beta/K^\xi \equiv_p K^m$. While the secret key $s$ allows decryption of any ciphertext encrypted to the public key $K$, the encryption nonce only allows decryption of the specific ciphertext it was used to generate. The encryption nonce must therefore be securely protected. Release of an encryption nonce can, when appropriate, serve as a fast and convenient method of verifiable decryption.

Usually, only two possible messages are encrypted in this way by \EG. An encryption of one is used to indicate that an option is selected, and an encryption of zero is used to indicate that an option is not selected. For some voting methods such as cumulative voting, Borda count, and a variety of cardinal voting methods like score voting and STAR-voting, it can be necessary to encrypt other small, positive integers.

S3c The value of $K^m$ can be computed from the encryption nonce $\xi$
S3c The value of $m$ can be computed from the encryption nonce $\xi$
S3c An encryption of one is used to indicate that an option is selected
S3c An encryption of zero is used to indicate that an option is not selected

---- S3d
\subsubsection*{Homomorphic properties}
A fundamental quality of the DPP vote encryption is its additively homomorphic property. If two messages $m_1$ and $m_2$ are respectively encrypted as $(A_1,B_1 ) = (g^{\xi_1} \bmod p , K^{m_1+\xi_1} \bmod p)$ and $(A_2, B_2) = (g^{\xi_2}\bmod p, K^{m_2+\xi_2} \bmod p)$, then the component-wise product 
\begin{equation}
  (A,B) = ( A_1 A_2 \bmod p, B_1 B_2 \bmod p) = (g^{\xi_1+\xi_2} \bmod p, K^{(m_1+m_2) + (\xi_1+\xi_2)} \bmod p)
\end{equation}
is an encryption of the sum $m_1+m_2$. (There is an implicit assumption here that $(m_1+m_2) < q$ which is easily satisfied when $m_1$ and $m_2$ are both small. If $(\xi_1+\xi_2)\geq q$, $(\xi_1+\xi_2) \bmod q$ may be substituted without changing the equation since $g^q\equiv_p 1$.)

This additively homomorphic property is used in two important ways in \EG.  First, all of the encryptions of a single option across ballots can be multiplied to form an encryption of the sum of the individual values. Since the individual values are one (or some other integer for certain voting methods) on ballots that select that option and zero otherwise, the sum is the tally of votes for that option and the product of the individual encryptions is an encryption of the tally.

S3d All the encryptions of a single option across ballots can be multiplied to form an encryption of the sum of the individual values
S3d An encryption of some other integer is used for certain voting methods
S3d The product of the encryptions of a single option across ballots is an encryption of the tally

The other use is to sum all of the selections made in a single contest on a single ballot. In the simplest case, after demonstrating that each option is an encryption of either zero or one, the product of the encryptions indicates the number of options that are encryptions of one, and this can be used to show that no more ones than permitted are among the encrypted options -- i.e., that no more options were selected than permitted. When larger integers are allowed, i.e. an option can receive multiple votes or weighted votes, the product of the ciphertexts then encrypts the total number of votes or the sum of weights and is used in the same way to ensure only the permitted number of votes or permitted sum of weights were used.

S3d Every option can be demonstrated to be an encryption of either zero or one
S3d Every option can be demonstrated to be an encryption of some other integer for certain voting methods
S3d The product of the encrypted options of a single ballot can be used to show that no more options were selected than permitted
S3d When an option can receive multiple or weighted votes, the product of the encrypted options of a single ballot can be used to show that only the permitted number of votes or permitted sum of weights were used

However, as will be described below, it is possible for a holder of a nonce $\xi$ to prove to a third party that a pair $(\alpha, \beta)$ is an encryption of $m$ without revealing the nonce $\xi$ and without access to the secret $s$.

S3d A holder of a nonce $\xi$ can prove to a third party that a pair $(\alpha, \beta)$ is an encryption of $m$ without access to the secret $s$ or revealing the nonce $\xi$

---- S3e 
\subsubsection*{Non-interactive zero-knowledge (NIZK) proofs}
\EG provides numerous proofs about encryption keys, encrypted ballots, and election tallies using the following four techniques.
\begin{enumerate}
\item A Schnorr proof\footnote{Schnorr C.P. (1990) Efficient Identification and Signatures for Smart Cards. In: Brassard G. (eds) Advances in Cryptology — CRYPTO' 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. \url{https://link.springer.com/content/pdf/10.1007\%2F0-387-34805-0_22.pdf}} allows the holder of a secret key $s$ to interactively prove possession of $s$ without revealing $s$.

S3e1 The holder of a secret key $s$ can interactively prove possession of $s$ without revealing $s$ using a Schnorr proof.

\item A Chaum-Pedersen proof\footnote{Chaum D., Pedersen T.P. (1993) \emph{Wallet Databases with Observers}. In: Brickell E.F. (eds) Advances in Cryptology — CRYPTO' 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. \url{https://link.springer.com/content/pdf/10.1007\%2F3-540-48071-4_7.pdf}} allows an encryption to be interactively proven to decrypt to a particular value without revealing the nonce used for encryption or the secret decryption key $s$. (This proof can be constructed with access to either the nonce used for encryption or the secret decryption key.)

S3e2 An encryption can be interactively proven to decrypt to a particular value without revealing the nonce used for encryption or the secret decryption key $s$, with access to the nonce used for encryption with a Chaum-Pedersen proof.
S3e2 An encryption can be interactively proven to decrypt to a particular value without revealing the nonce used for encryption or the secret decryption key $s$, with access to $s$ using a Chaum-Pedersen proof.

\item The Cramer-Damgård-Schoenmakers technique\footnote{Cramer R., Damgård I., Schoenmakers B. (1994) \emph{Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols}. In: Desmedt Y.G. (eds) Advances in Cryptology — CRYPTO' 94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. \url{https://link.springer.com/content/pdf/10.1007\%2F3-540-48658-5_19.pdf}} enables a disjunction to be interactively proven without revealing which disjunct is true.

S3e3 A disjunction can be interactively proven without revealing which disjunct is true using the Cramer-Damgård-Schoenmakers technique.

\item The Fiat-Shamir heuristic\footnote{Fiat A., Shamir A. (1987) \emph{How To Prove Yourself: Practical Solutions to Identification and Signature Problems}. In: Odlyzko A.M. (eds) Advances in Cryptology — CRYPTO' 86. CRYPTO 1986. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. \url{https://link.springer.com/content/pdf/10.1007\%2F3-540-47721-7_12.pdf}} allows interactive proofs to be converted into non-interactive proofs.

S3e4 An interactive proof can be converted into a non-interactive proof using the Fiat-Shamir heuristic.

\end{enumerate}
Using a combination of the above techniques, it is possible for \EG to demonstrate that keys are properly chosen, that ballots are well-formed, and that decryptions match claimed values.\footnote{For all proof variants, \EG uses a compact representation that omits the commitments. Proofs consist of the challenge and response values only. When verifying proofs, the verification equations can be used to recompute the commitments and check their correctness via the challenge hash computation.}

S3e ElectionGuard can demonstrate that keys are properly chosen.
S3e ElectionGuard can demonstrate that ballots are well-formed.
S3e ElectionGuard can demonstrate that decryptions match claimed values.

---- S3f
\subsubsection*{Threshold encryption}
Threshold encryption is used for encryption of ballots and other data. This form of encryption makes it very easy to combine individual guardian public keys into a single public key.  It also offers a homomorphic property that allows individual encrypted votes to be combined to form encrypted tallies.

S3f Threshold encryption is used for encryption of ballots and other data.
S3f It is very easy to combine individual guardian public keys into a single public key.
S3f Threshold encryption offers a homomorphic property that allows individual encrypted votes to be combined to form encrypted tallies.

The guardians of an election will each generate a public-secret key pair. The public keys will then be combined (as described in the following section) into a single election public key which is used to encrypt all selections made by voters in the election.

S3f Every guardian can generate a public-secret key pair.
S3f The guardians' public keys can be combined into a single election public key.
S3f The single election public key can be used to encrypt all selections made by voters in the election.

At the conclusion of the election, each guardian will compute a verifiable partial decryption of each tally. These partial decryptions will then be combined to form full verifiable decryptions of the election tallies.

S3f A guardian can compute a verifiable partial decryption of every tally.
S3f Verifiable partial tally decryptions can be combined  to form full verifiable decryptions of the election tallies.

To accommodate the possibility that one or more of the guardians will not be available at the conclusion of the election to form their partial decryptions, the guardians will cryptographically share\footnote{Shamir A. (1979) \emph{How to Share a Secret}. Communications of the ACM, vol 22.} their secret keys amongst each other during key generation in a manner to be detailed in Section~\ref{sec:keygen}. Each guardian can then compute a share of the secret decryption key, which they use to form the partial decryptions. A pre-determined threshold quorum value ($k$) out of the ($n$) guardians will be necessary to produce a full decryption.

S3f During key generation, a guardian can cryptographically share their secret keys with another guardian per Section~\ref{sec:keygen}.
S3f A guardian, having received secret keys from other guardians, can compute a share of the secret decryption key
S3f A guardian, having computed a share of the secret decryption key, can
form a partial decryption.

---- S3g 
\subsubsection*{Encryption of other data}
\EG provides means to encrypt data other than votes, which are selections usually encoded as zero or one that need to be homomorphically aggregated. Such data may include the cryptographic shares of a guardian's secret key that are sent to the other guardians and are encrypted to the receiving guardians' public keys, write-in information that needs to be attached to an encrypted selection and is encrypted to the election public key, or other auxiliary data attached to an encrypted ballot, either encrypted to the election public key or to an administrative public key. The non-vote data do not need to be homomorphically encrypted and can use a more standard form of public-key encryption removing the data size restrictions imposed by the vote encryption. \EG encrypts such data with hashed ElGamal encryption, which deploys a key derivation function (\KDF) to generate a key stream that is then XORed with the data. To implement the \KDF and to provide a message authentication code (\MAC), encryption makes use of the keyed Hash Message Authentication Code \HMAC. In \EG, \HMAC is instantiated as \HMAC-\SHA with the hash function \SHA.

S3g EGRI provides a non-homomorphic encryption method known as "hashed ElGamal" for encrypting data other than votes
S3g EGRI provides a way to use the appropriate private key to decrypt data encrypted with hashedElGamal
S3g data encrypted with hashedElGamal cannot be decrypted without the private key
S3g hashed ElGamal encryption does not have the data size restrictions imposed by the vote encryption
S3g hashed ElGamal encryption uses a KDF based on HMAC-SHA-2-256 to generate a key stream XORed with the data
S3g EGRI allows to encrypt the cryptographic shares of a guardian's secret key to the receiving guardians' public keys
S3g EGRI allows to encrypt to the election public key write-in information to be attached to an encrypted selection
S3g EGRI allows to attach to an encrypted selection write-in information that is encrypted to the election public key
S3g EGRI allows to attach to an encrypted ballot other auxiliary data without size restrictions encrypted with hashed-ElGamal to the election public key
S3g EGRI allows to attach to an encrypted ballot other auxiliary data without size restrictions encrypted with hashed-ElGamal to an administrative public key

---- S3.1
\subsection{Parameter requirements}
\EG uses integers to instantiate the encryption rather than elliptic curves in order to make construction of election verifiers as simple as possible without requiring special tools and dependencies. The encryption scheme used to encrypt votes is defined by a prime $p$ and a prime $q$ which divides $(p-1)$. We use $r = (p-1)/q$ to denote the cofactor of $q$, and a generator $g$ of the order $q$ subgroup $\Z_p^r$ is fixed. We also require $r/2$ to be prime. The specific values for a 4096-bit prime $p$ and a 256-bit prime $q$ which divides $(p-1)$ and a generator $g$ that define all standard baseline parameters are given below. 

S3.1 EGRI uses integer-based encryption rather than elliptic curves
S3.1 EGRI does not use elliptic curves
S3.1 The encryption scheme used to encrypt votes is defined by primes p and q.
S3.1 q divides p - 1
S3.1 r = (p-1)/q is fixed. We also require $r/2$ to be prim
S3.1 r is a generator g of the order q subgroup Z_p^r
S3.1 subgroup Z_p^r is of order q
S3.1 r/2 is prime
S3.1 The value of p matches the specific value given in EG 2.0 DS section 3.1
S3.1 The value of q matches the specific value given in EG 2.0 DS section 3.1
S3.1 The value of r matches the specific value given in EG 2.0 DS section 3.1
S3.1 The value of g matches the specific value given in EG 2.0 DS section 3.1

---- S3.1.1
\subsubsection{Standard baseline cryptographic parameters}\label{sec:parameters}
Standard parameters for \EG begin with the largest 256-bit prime $q = 2^{256}-189$. The (big endian) hexadecimal representation of $q$ is as follows.
\begin{equation}
q = \mathtt{0xFFFFFFFF \ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFF43}
\end{equation}
The modulus $p$ is then set to be a 4096-bit prime with the following properties.
\begin{enumerate}
	\item The first 256 bits of $p$ are all ones.
	\item The last 256 bits of $p$ are all ones.
	\item $p-1$ is a multiple of $q$.
	\item $(p-1)/2q$ is also prime.
\end{enumerate}
The middle 3584 bits of $p$ are chosen by starting with the first 3584 bits of the constant $\mathrm{ln}(2)$ (the natural logarithm of $2$).\footnote{See \url{https://oeis.org/A068426} for the integer sequence consisting of the bits of $\mathrm{ln}(2)$.} After pre-pending and appending 256 ones, $p$ is determined by finding the smallest prime larger than this value that satisfies the above properties.

This works out to $p = 2^{4096}-2^{3840}+2^{256} (\lfloor2^{3584} \mathrm{ln}(2)\rfloor + \delta) + (2^{256} - 1)$ where the value of $\delta$ is given by 
{\small
$$\delta=287975203778583638958138611533602521491887169409704874643524560756486080635197037903.\footnote{Discovering this value $\delta$ required enumerating roughly 2.49 million values satisfying the first three of the above properties to find the first one for which both $p$ and $(p-1)/2q$ are both prime.}
$$ 
}
The hexadecimal representation of $p$ is as follows.
{\allowdisplaybreaks
\begin{align*}
  p \ = \ \mathtt{0x}
  & \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF}\\
  & \mathtt{B17217F7\ D1CF79AB\ C9E3B398\ 03F2F6AF\ 40F34326\ 7298B62D\ 8A0D175B\ 8BAAFA2B}\\
  & \mathtt{E7B87620\ 6DEBAC98\ 559552FB\ 4AFA1B10\ ED2EAE35\ C1382144\ 27573B29\ 1169B825}\\
  & \mathtt{3E96CA16\ 224AE8C5\ 1ACBDA11\ 317C387E\ B9EA9BC3\ B136603B\ 256FA0EC\ 7657F74B}\\
  & \mathtt{72CE87B1\ 9D6548CA\ F5DFA6BD\ 38303248\ 655FA187\ 2F20E3A2\ DA2D97C5\ 0F3FD5C6}\\
  & \mathtt{07F4CA11\ FB5BFB90\ 610D30F8\ 8FE551A2\ EE569D6D\ FC1EFA15\ 7D2E23DE\ 1400B396}\\
  & \mathtt{17460775\ DB8990E5\ C943E732\ B479CD33\ CCCC4E65\ 9393514C\ 4C1A1E0B\ D1D6095D}\\
  & \mathtt{25669B33\ 3564A337\ 6A9C7F8A\ 5E148E82\ 074DB601\ 5CFE7AA3\ 0C480A54\ 17350D2C}\\
  & \mathtt{955D5179\ B1E17B9D\ AE313CDB\ 6C606CB1\ 078F735D\ 1B2DB31B\ 5F50B518\ 5064C18B}\\
  & \mathtt{4D162DB3\ B365853D\ 7598A195\ 1AE273EE\ 5570B6C6\ 8F969834\ 96D4E6D3\ 30AF889B}\\
  & \mathtt{44A02554\ 731CDC8E\ A17293D1\ 228A4EF9\ 8D6F5177\ FBCF0755\ 268A5C1F\ 9538B982}\\
  & \mathtt{61AFFD44\ 6B1CA3CF\ 5E9222B8\ 8C66D3C5\ 422183ED\ C9942109\ 0BBB16FA\ F3D949F2}\\
  & \mathtt{36E02B20\ CEE886B9\ 05C128D5\ 3D0BD2F9\ 62136319\ 6AF50302\ 0060E499\ 08391A0C}\\
  & \mathtt{57339BA2\ BEBA7D05\ 2AC5B61C\ C4E9207C\ EF2F0CE2\ D7373958\ D7622658\ 90445744}\\
  & \mathtt{FB5F2DA4\ B7510058\ 92D35689\ 0DEFE9CA\ D9B9D4B7\ 13E06162\ A2D8FDD0\ DF2FD608}\\
  & \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF}
\end{align*}
The hexadecimal representation of the cofactor $r = (p-1)/q$ is as follows.
\begin{align*}
  r \ = \ \mathtt{0x01}\ 
  & \mathtt{00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 000000BC}\\
  & \mathtt{B17217F7\ D1CF79AB\ C9E3B398\ 03F2F6AF\ 40F34326\ 7298B62D\ 8A0D175B\ 8BAB857A}\\
  & \mathtt{E8F42816\ 5418806C\ 62B0EA36\ 355A3A73\ E0C74198\ 5BF6A0E3\ 130179BF\ 2F0B43E3}\\
  & \mathtt{3AD86292\ 3861B8C9\ F768C416\ 9519600B\ AD06093F\ 964B27E0\ 2D868312\ 31A9160D}\\
  & \mathtt{E48F4DA5\ 3D8AB5E6\ 9E386B69\ 4BEC1AE7\ 22D47579\ 249D5424\ 767C5C33\ B9151E07}\\
  & \mathtt{C5C11D10\ 6AC446D3\ 30B47DB5\ 9D352E47\ A53157DE\ 04461900\ F6FE360D\ B897DF53}\\
  & \mathtt{16D87C94\ AE71DAD0\ BE84B647\ C4BCF818\ C23A2D4E\ BB53C702\ A5C8062D\ 19F5E9B5}\\
  & \mathtt{033A94F7\ FF732F54\ 12971286\ 9D97B8C9\ 6C412921\ A9D86797\ 70F499A0\ 41C297CF}\\
  & \mathtt{F79D4C91\ 49EB6CAF\ 67B9EA3D\ C563D965\ F3AAD137\ 7FF22DE9\ C3E62068\ DD0ED615}\\
  & \mathtt{1C37B4F7\ 4634C2BD\ 09DA912F\ D599F433\ 3A8D2CC0\ 05627DCA\ 37BAD43E\ 64A39631}\\
  & \mathtt{19C0BFE3\ 4810A21E\ E7CFC421\ D53398CB\ C7A95B3B\ F585E5A0\ 4B790E2F\ E1FE9BC2}\\
  & \mathtt{64FDA810\ 9F6454A0\ 82F5EFB2\ F37EA237\ AA29DF32\ 0D6EA860\ C41A9054\ CCD24876}\\
  & \mathtt{C6253F66\ 7BFB0139\ B5531FF3\ 01899612\ 02FD2B0D\ 55A75272\ C7FD7334\ 3F7899BC}\\
  & \mathtt{A0B36A4C\ 470A64A0\ 09244C84\ E77CEBC9\ 2417D5BB\ 13BF1816\ 7D8033EB\ 6C4DD787}\\
  & \mathtt{9FD4A7F5\ 29FD4A7F\ 529FD4A7\ F529FD4A\ 7F529FD4\ A7F529FD\ 4A7F529F\ D4A7F52A}
\end{align*}
Finally, the generator $g$ is chosen to be $g = 2^r \bmod p$ and has the following hexadecimal representation.
\begin{align*}
  g \ = \ \mathtt{0x}
  & \mathtt{36036FED\ 214F3B50\ DC566D3A\ 312FE413\ 1FEE1C2B\ CE6D02EA\ 39B477AC\ 05F7F885}\\
  & \mathtt{F38CFE77\ A7E45ACF\ 4029114C\ 4D7A9BFE\ 058BF2F9\ 95D2479D\ 3DDA618F\ FD910D3C}\\
  & \mathtt{4236AB2C\ FDD783A5\ 016F7465\ CF59BBF4\ 5D24A22F\ 130F2D04\ FE93B2D5\ 8BB9C1D1}\\
  & \mathtt{D27FC9A1\ 7D2AF49A\ 779F3FFB\ DCA22900\ C14202EE\ 6C996160\ 34BE35CB\ CDD3E7BB}\\
  & \mathtt{7996ADFE\ 534B63CC\ A41E21FF\ 5DC778EB\ B1B86C53\ BFBE9998\ 7D7AEA07\ 56237FB4}\\
  & \mathtt{0922139F\ 90A62F2A\ A8D9AD34\ DFF799E3\ 3C857A64\ 68D001AC\ F3B681DB\ 87DC4242}\\
  & \mathtt{755E2AC5\ A5027DB8\ 1984F033\ C4D17837\ 1F273DBB\ 4FCEA1E6\ 28C23E52\ 759BC776}\\
  & \mathtt{5728035C\ EA26B44C\ 49A65666\ 889820A4\ 5C33DD37\ EA4A1D00\ CB62305C\ D541BE1E}\\
  & \mathtt{8A92685A\ 07012B1A\ 20A746C3\ 591A2DB3\ 815000D2\ AACCFE43\ DC49E828\ C1ED7387}\\
  & \mathtt{466AFD8E\ 4BF19355\ 93B2A442\ EEC271C5\ 0AD39F73\ 3797A1EA\ 11802A25\ 57916534}\\
  & \mathtt{662A6B7E\ 9A9E449A\ 24C8CFF8\ 09E79A4D\ 806EB681\ 119330E6\ C57985E3\ 9B200B48}\\
  & \mathtt{93639FDF\ DEA49F76\ AD1ACD99\ 7EBA1365\ 7541E79E\ C57437E5\ 04EDA9DD\ 01106151}\\
  & \mathtt{6C643FB3\ 0D6D58AF\ CCD28B73\ FEDA29EC\ 12B01A5E\ B86399A5\ 93A9D5F4\ 50DE39CB}\\
  & \mathtt{92962C5E\ C6925348\ DB54D128\ FD99C14B\ 457F883E\ C20112A7\ 5A6A0581\ D3D80A3B}\\
  & \mathtt{4EF09EC8\ 6F9552FF\ DA1653F1\ 33AA2534\ 983A6F31\ B0EE4697\ 935A6B1E\ A2F75B85}\\
  & \mathtt{E7EBA151\ BA486094\ D68722B0\ 54633FEC\ 51CA3F29\ B31E77E3\ 17B178B6\ B9D8AE0F}
\end{align*}
}

Alternative parameter sets are possible and may be allowed in future versions of \EG\footnotemark.

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

\EGnote{As an example for alternative parameters, the Appendix provides a set of reduced parameters that offer better performance at a lower security level, and additionally provides various sets of very small and insecure parameters for testing purposes only. A good source for parameter generation is appendix A of FIPS 186-4\footnotemark. Allowing alternate non-standard parameters would force election verifiers to recognize and check that parameters are correctly generated. Since these checks are very different from other checks that are required of a verifier, allowing such parameters would add substantial complexity to election verifiers. For this reason, this version of \EG fixes the parameters as above.}
\footnotetext{NIST (2013) Digital Signature Standard (DSS). In: FIPS 186-4. \url{https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf}}

---- S3.1.2
\subsubsection{Parameter base hash}\label{sec:parameterhash}
The prime modulus $p$, the subgroup order $q$, and the subgroup generator $g$ are hashed using the \EG hash function $H$ (as specified in detail in Section~\ref{sec:hashing}) to form the parameter base hash
\begin{equation}\label{eq:parameterhash}
\HH_P = H(\mathtt{ver}; \mathtt{0x00}, p, q, g).
\end{equation}
The symbol $\mathtt{ver}$ denotes the version byte array that encodes the used version of this specification. The array has length 32 and contains the UTF-8 encoding of the string $\Str{v2.0.0}$ followed by \texttt{0x00}-bytes, i.e. $\mathtt{ver} = \mathtt{0x76322E302E30} \parallel \bytes(0,27)$. The \texttt{0x00}-byte at the beginning of the second argument of $H$ is a domain separation byte (written in hexadecimal notation), see Section~\ref{sec:hashinputdata}. For the baseline parameters specified in Section~\ref{sec:parameters} above, the hexadecimal representation of the parameter base hash is
\begin{equation}
H_P = \mathtt{0x2B3B025E50E09C119CBA7E9448ACD1CABC9447EF39BF06327D81C665CDD86296}.
\end{equation}
This hash value is an input to all subsequent hash computations, either directly or indirectly, which binds all hash outputs to the baseline parameters and the version of the specification used for the election.

S3.1.2 H_P is computed as H("v2.0.0" zero extended to length 32 ; 0x00, p, q, g)
S3.1.2 The value computed for H_P is 0x2B3B025E50E09C119CBA7E9448ACD1CABC9447EF39BF06327D81C665CDD86296

---- S3.1.3
\subsubsection{Election parameters and the election manifest}\label{sec:manifest}
Another parameter of an election is a public election manifest. The ElectionGuard manifest is a single file that describes the modalities of the election and must specify a wide range of data about it.  Most importantly, the manifest lists, among other information, all the contests in an election, the candidates (selectable options) for each contest together with associations between each option and its representation on a virtual ballot, and the contest selection limit—the number of options that a voter may select in that contest. It is assumed that each contest in the manifest has a unique label and that within each contest, each option also has a unique label. For instance, if Alice, Bob, and Carol are running for governor, and David and Ellen are running for senator, the election manifest file could enable the vector $\langle 0,1,0;0,1\rangle$ to be recognized as a ballot with votes for Bob as governor and Ellen as senator. This section defines how the manifest must uniquely specify the election parameters.

S3.1.3a The RI provides a parameter for a public election manifest
S3.1.3a The election manifest is a single file
S3.1.3a The election manifest describes the modalities of the election and specifies a wide range of data about it
S3.1.3a The election manifest lists for each contest, the candidates (selectable options)
S3.1.3a The election manifest lists for each contest, associations between each selectable option and its representation on a virtual ballot
S3.1.3a The election manifest lists for each contest, the number of options that a voter may select in that contest (selection limit)
S3.1.3a The election manifest lists for each contest, defines a label unique across all contests in the manifest
S3.1.3a The election manifest lists for each selectable option, defines a label unique across all selectable options in that contest

\paragraph{Labels.}
The election objects relevant for \EG such as contests, selectable options, and ballot styles are identified by unique labels. A \emph{label} is a string, it should be a short, concise name or identifier and should therefore not contain any long-form descriptions or line break characters, tabs, and similar special characters. Likewise, a label should not have leading or trailing whitespace characters.

The \EG manifest must contain a label that contains a unique and descriptive identifier for the election.

S3.1.3b Contests are identified by labels unique within the election manifest
S3.1.3b Selectable options are identified by labels unique within their contest
S3.1.3b The RI rejects labels that contain line break characters, tabs, or similar special characters
S3.1.3b The RI rejects labels that have leading or trailing whitespace
S3.1.3b The election manifest has a unique and descriptive identifier for the election. The RI rejects any manifest without it

\paragraph{Indices.} Instead of using the labels directly, \EG handles contests, selectable options, ballot styles, etc. in terms of their position in a unique ordered list. They can therefore be uniquely identified by an index value. An \emph{index} is a $1$-based ordinal in the range $1 \leq i < 2^{31}$.\footnote{The upper bound of $2^{31}-1$ is in consideration of languages and runtimes that do not have full support for unsigned integers.}

S3.1.3c Index values are integers in the range 1 <= i < 2^31
S3.1.3c Every contest within the election manifest is uniquely identified by an index value, implied by the order defined in the election manifest.
S3.1.3c Every selectable option within a contest is uniquely identified by an index value, implied by the order defined in the contest election manifest.
S3.1.3c Every ballot style within the election manifest is uniquely identified by an index value implied by the order defined in the election manifest.
S3.1.3c The first ballot style within the election manifest has index value 1.

\paragraph{Contests and the contest index.}
The election manifest must contain a single ordered list of all the contests that can appear on any ballot generated for the election. Each contest must have a contest label $\lambda_\Ccal$ that is unique within the election. The position of a given contest $\Ccal$ in this list is the \emph{contest index} $\indc(\lambda_\Ccal)$. The contest list provides a bijective mapping between the unique contest labels and the corresponding contest index values. Note that the first contest in the list has contest index $1$. 

S3.1.3d The election manifest defines a single ordered list of all contests on any ballot
S3.1.3d The first contest within the election manifest has index value 1.

\paragraph{Selectable options and the option index.}
For each contest in the contest list, the election manifest must also contain a single ordered list of all the selectable options in this contest. Each selectable option $\Ocal$ must have an option label $\lambda_\Ocal$ that is unique within the contest. The position of a given selectable option $\Ocal$ in this list is the \emph{option index} $\indo(\lambda_\Ocal)$. This option list provides a bijective mapping between the unique selectable option labels and the corresponding option index values. The first selectable option in the list has option index $1$.

S3.1.3e Every contest in the election manifest defines a single ordered list of all selectable options.
S3.1.3e The first selectable option within each contest has index value 1.

\paragraph{Ballot styles and the ballot style index.}
A \emph{ballot style} is a single list of contest indices that defines which contests appear on a ballot generated according to this ballot style. If a contest index is contained in this list, the corresponding contest is present, otherwise it is not. The list is not ordered and only specifies whether a contest is present or not on a ballot of this ballot style. Each ballot style $\Scal$ must have a ballot style label $\lambda_\Scal$ that is unique within the election. The election manifest must contain a single, ordered list of all ballot styles that are possible in the election. The position of a given ballot style $\Scal$ in this list is the \emph{ballot style index} $\inds(\lambda_\Scal)$. The ballot style list provides a bijective mapping between the unique ballot styles and the corresponding ballot style index values. Again, the first ballot style in the list has ballot style index $1$.

S3.1.3f The election manifest defines a single ordered list of all ballot styles
S3.1.3f The first ballot style within the election manifest has index value 1.
S3.1.3f Every ballot style defines a label unique across all ballot styles in the manifest
S3.1.3f Every ballot style defines a single list of contest indices
S3.1.3f Order is not significant in a ballot style contest index list
S3.1.3f The RI rejects the manifest if any contest index does not refer to a contest in the election manifest
S3.1.3f The RI rejects the manifest if any contest index appears more than once in the same ballot style contest index list

\paragraph{Selections, option selection limits and contest selection limits.}
A \emph{selection} is the assignment of a value to an option by the voter. This could be the value $1$, meaning that the voter selected this option, or the value $0$, meaning that the voter did not select this option. To allow other voting methods, \EG allows a selection to be the assignment of a value in a range $\{0,1,\dots,R\}$, where $R$ is the \emph{option selection limit}, a positive integer that defines the maximal value allowed to be assigned to this option by the voter. For each contest, the election manifest must specify the option selection limit for the options in this contest, and must also specify a \emph{contest selection limit} $L$, which is the maximal total value for the sum of all selections made in that contest.

S3.1.3g Every contest in the election manifest may specify a nonnegative integer contest selection limit
S3.1.3g If not specified, the contest selection limit defaults to 1
S3.1.3g The contest selection limit limits the maximum total value that can be assigned all options in that contest

S3.1.3g Every selectable option in every contest may specify a nonnegative integer option selection limit
S3.1.3g If not specified, the option selection limit defaults to 1
S3.1.3g The option selection limit limits the maximum value that can be assigned to that selectable option
S3.1.3g Every selectable option field must be voter-assigned a nonnegative integer value less than or equal to the smaller of the contest and option selection limits.
S3.1.3g RI may warn if any contest selection limit is zero
S3.1.3g RI may warn if any option selection limit is zero
S3.1.3g RI may warn if any option selection limit is greater than the contest selection limit

\paragraph{Optional data fields.}
The election manifest offers optional data fields for additional data that can be attached to any of the above concepts and to the manifest in general at the top level. They can be used to provide additional information on contests, selectable options, and ballot styles that go beyond the short unique labels described above. In addition, there can be data fields that describe general information about the election, jurisdiction, election device manufacturers, software versions, the date and location, etc. that help to interpret the additional data. 


There are many other things that a manifest may specify.  Some examples are listed here.

S3.1.3h Election manifest allows additional data to describe general information about the election
S3.1.3h Election manifest allows additional data to describe general information about the jurisdiction
S3.1.3h Election manifest allows additional data to describe general information about the election device manufacturers
S3.1.3h Election manifest allows additional data to describe general information about software versions
S3.1.3h Election manifest allows additional data to describe general information about date
S3.1.3h Election manifest allows additional data to describe general information about location

\paragraph{Undervotes.}
An undervote occurs in a contest if the number of selected options (or more generally, the total sum of selections assigned by the voter) is strictly less than the contest selection limit, the number (or total sum) of allowed selections a voter can make in that contest.

S3.1.3i 'Undervote condition' or 'undervoted' is a per-contest state in which the sum of the selections is strictly less than the contest selection limit

\paragraph{Counting undervoted contests.}
A manifest may specify whether the fact that a contest was undervoted should be recorded for public verification.  If this is specified, the indicated contest should have an additional field that functions very much like a selectable option field. The value of this field is an encryption of one if the contest was undervoted on the ballot and an encryption of zero otherwise. The undervote field should be set to one only when the number of option fields that are set to one is strictly less than the contest selection limit. This can be enforced by checking that the sum of all field contents should not exceed the contest selection limit for that contest.

This field is an undervote indicator field and is added to all ballots that contain this contest if the occurrence of an undervote is to be verifiably recorded. The field only indicates that an undervote has occurred on the specific ballot in this contest. A tally of this field will contain the total number of ballots that showed an undervote in this contest.
The field does not record by how many votes the contest was undervoted, i.e. by how much the total number of selections by the voter is less than the contest selection limit. This number can be recorded in an undervote difference count field.

S3.1.3j Every contest within the election manifest can specify that an undervote condition is to be recorded for public verification
S3.1.3j If a contest specifies to record undervote conditions, the contest has an additional 'undervoted' field that functions much like a selectable option
S3.1.3j Every contest 'undervoted' field must be system-assigned a value of 0 or 1
S3.1.3j Every contest 'undervoted' field must be system-assigned a value 1 if and only if that contest was undervoted on that ballot
S3.1.3j Every contest 'undervoted' field must include a range proof that the encrypted value is either 0 or 1
S3.1.3j The value of a contest 'undervoted' field does not count against the contest selection limit

\paragraph{Undervote Difference Count.}
A manifest may specify whether the total number of undervotes, i.e. the difference between the number of selections the voter made and the contest selection limit, for each contest should be recorded for public verification. If this is specified, the indicated contest should have an additional field that functions very much like an option field but whose value need not be limited to zero or one.  The value of this field is an encryption of the number of undervotes on that ballot for that contest.  This can be enforced by checking that the sum of all field contents should exactly match the contest selection limit for that contest.

S3.1.3k Every contest within the election manifest can specify that the net undervote is to be recorded for public verification. TODO: Does it make sense to specify this in addition to the S3.1.3j 'undervoted' additional field, or are they mutually exclusive?
S3.1.3k If a contest specifies to record the net undervote, the contest has an additional 'net undervote' field that functions much like a selectable option, but is not voter-assigned
S3.1.3k Every contest 'net undervote' field must be system-assigned a value of 0 through the contest selection limit, according to the net undervote on that ballot
S3.1.3k Every contest 'net undervote' field must include a range proof that the encrypted value is 0 through the contest selection limit, inclusive
S3.1.3k The value that the system assigns to a contest 'net undervote' field must be the contest selection limit minus the sum of the voter-assigned selections
S3.1.3k The value of any 'net undervote' field does not count against the contest selection limit
S3.1.3k TODO: range proof for 'net undervote' field?

\paragraph{Overvotes.}
An overvote occurs in a contest if the voter selected more options than allowed, i.e. more than the contest selection limit for that contest specifies.
A manifest may specify whether an overvoted contest should be recorded for public verification.  If this is specified, the indicated contest should have an additional field that functions very much like an option field.  The value of this field is an encryption of one if the contest was overvoted on the ballot and an encryption of zero otherwise.  When the overvote field is set to one, all other selection fields should be set to zero, and this can be enforced by checking that the sum of the other fields---when added to the product of the contest selection limit with the overvote field contents should not exceed the selection limit for that contest.\footnote{An alternative implementation would be to always set the overvote field to either zero or the contest selection limit. This would be slightly more efficient computationally, but the publicly verified number of overvotes for that contest would be scaled up by a factor of the contest selection limit and the selection limit would then need to be divided out for reporting purposes.} Similar to the undervote difference count, the overvote difference count can be verifiably recorded in a separate overvote difference field.

S3.1.3l 'Overvote condition' or 'overvoted' is a per-contest state in which a selection is strictly greater the option selection limit and/or the sum of the selections is strictly greater than the contest selection limit.
S3.1.3l Every contest within the election manifest can specify that an overvote condition is to be recorded for public verification
S3.1.3l If a contest specifies to record overvote conditions, the contest has an additional 'overvoted' field that functions much like a selectable option, but is not voter-assigned
S3.1.3l Every contest 'overvoted' field must be system-assigned a value of 0 or 1
S3.1.3l Every contest 'overvoted' field must be system-assigned a value of 1 if and only if that contest was overvoted on that ballot
S3.1.3l Every contest 'overvoted' field must include a range proof that the encrypted value is either 0 or 1
S3.1.3l The value of an 'overvoted' field does not count against the contest selection limit
S3.1.3l Whenever a contest 'overvoted' field is set to 1, all voter-assigned fields must be set to 0
S3.1.3l RI (tallying? verification?) must verify for every contest that the sum of all voter-assigned fields, 'undervoted', 'net undervote', and (the product of the 'overvoted' field and the contest selection limit) is less than or equal to the contest selection limit.

S3.1.3l Every contest within the election manifest can specify that the net overvote is to be recorded for public verification. TODO: Does it make sense to specify this in addition to the S3.1.3l 'overvoted' additional field, or are they mutually exclusive?
S3.1.3l If a contest specifies to record the net overvote, the contest has an additional 'net overvote' field that functions much like a selectable option, but is not voter-assigned
S3.1.3l Every contest 'net overvote' field must be system-assigned the nonnegative integer value that is the the greater of (each option's voter-assigned selection minus the option selection limit), (the sum of the voter-assigned selections minus the contest selection limit), and 0. I.e., the total selection value that would need to be removed to cure the overvote condition.
S3.1.3l Every contest 'net overvote' field must include a range proof that the encrypted value is a nonnegative integer less than or equal to the greater of [(the sum of the voter-assigned selection option fields minus the contest selection limit) and (the sum of the voter-assigned selection option fields minus the smallest option selection limit)]. TODO could this identify the overvoted field
S3.1.3l The value of any 'net overvote' field does not count against the contest selection limit


\paragraph{Write-Ins.}
A manifest may specify whether the utilization of each write-in field in each contest is recorded for public verification.  If this is specified, the indicated contest should have one or more additional fields (usually matching the contest selection limit) that function very much like option fields.  If a single write-in is utilized in a contest, the first write-in field is set to one and all others are set to zero; if two write-ins are utilized in a contest, the first two write-in fields are set to one and all others are set to zero; etc.  Range proofs should be included to show that each of these individual write-in fields is an encryption of either zero or one.

S3.1.3m Every contest within the election manifest can specify the number of write-in fields to be recorded for public verification
S3.1.3m RI may warn if any contest specifies a number of write-in fields greater than the contest selection limit
S3.1.3m If a contest specifies to include a nonzero number of write-in fields, the contest has that number additional 'write-in N' fields as voter-assignable selectable options
S3.1.3m Any such write-in fields are to be labeled as "write-in N", where 'N' is the corresponding 1-based index value within the contest
S3.1.3m "Written-in" means that the election system has recorded some voter-supplied, non-empty, non-blank data in associated with a contest and write-in field index value
S3.1.3m Write-in fields must be written-in in index order. I.e., write-in field N can only be written-in if all write-in fields having lower-valued indexes are also written-in.
S3.1.3m All write-in fields must be assigned a value of 0 or 1
S3.1.3m A write-in field field must be assigned a value of 1 if and only if it was written-in
S3.1.3m The value of an write-in field counts against the contest selection limit
S3.1.3m Every write-in field must supply a range proof that the encrypted value is either 0 or 1
S3.1.3m TODO can we prove they are written-in in order?


\paragraph{Write-Ins Total.} 
A manifest may specify whether the total number of write-ins selected in each contest is recorded for public verification.  If this is specified, the indicated contest should have a single additional field that functions very much like option fields but whose value need not be limited to zero or one.  The value of this field is an encryption of the number of write-ins utilized on that ballot for that contest.  Range proofs should be used to demonstrate that in each instance, the value of this field is non-negative and does not exceed the contests selection limit.

S3.1.3n Every contest within the election manifest can specify that the count of write-in fields written-in is to be recorded for public verification.
S3.1.3n If a contest specifies to record the the count of fields written-in, the contest has an additional system-assigned 'count written-in' field
S3.1.3n Every contest 'count written-in' field must be system-assigned a value of 0 through the contest selection limit
S3.1.3n The value that the system assigns to a contest 'count written-in' field must be the count of write-in fields that were written-in
S3.1.3n The value of any 'count written-in' field does not count against the contest selection limit

\paragraph{A note on selection limit proofs.}  In general, a combination of the above fields can be merged into a single selection limit proof per contest per ballot.  For example, a contest which includes an undervote field, an overvote field, and two separate write-in fields can include a single range proof that the sum of these fields is non-negative and does not exceed the contest selection limit.  The only exceptions are the very unusual cases where a manifest specifies including both an undervote field and an undervote count field or both individual write-in fields and a write-in total field.  In these cases, the selection limit proofs should each include only one of the paired fields (e.g., undervote or undervote count) and a second selection limit proof should be included if both paired fields are to be verified.  

S3.1.3o TODO Range proofs of the various combinations of fields (selectable options, undervoted, net undervote, overvoted, net overvote, write-in N, count written-in) may be combined under specific conditions

---- S3.1.4
\subsubsection{Election manifest hash}\label{sec:manifesthash}
The data in the election manifest is written to a file \texttt{manifest} in a canonical representation that may be implementation specific.
The election manifest file \texttt{manifest} is hashed\footnote{The file that constitutes the election manifest is input to $H$ as an entire file. Again the $\mathtt{0x01}$ byte at the beginning of the second argument is a domain separation byte (in hex). In what follows, all uses of the function $H$ include such domain separation bytes.} using the \EG hash function with the parameter hash $\HH_P$ to produce the manifest digest
\begin{equation}\label{eq:manifesthash}
\HH_M = H(\HH_P; \mathtt{0x01}, \mathtt{manifest}).
\end{equation}

S3.1.4 A canonical byte representation is defined for the election manifest.
S3.1.4 RI allows to write the election manifest canonical representation to a file.
S3.1.4 RI uses the election manifest canonical representation in the hash computation.
S3.1.4 H_M is computed as H(H_P; 0x01, [election manifest canonical representation])

---- S3.1.5
\subsubsection{Election base hash}\label{sec:basehash}
The election base hash $\HH_B$ is computed from the parameter base hash $\HH_P$ and the manifest hash $\HH_M$ together with the number $n$ of guardians that participate in the election, and the quorum value $k$, as 
\begin{equation}\label{eq:basehash}
  \HH_B = H(\HH_P; \mathtt{0x02}, \HH_M, n, k).
\end{equation}
Incorporating the byte array $\HH_B$ into subsequent hash computations binds those hashes to the election parameters, the number of guardians, the threshold value and to a specific election by including the manifest.

S3.1.5 parameter n is the number of guardians
S3.1.5 parameter k is the number of guardians required to form a quorum for decryption
S3.1.5 H_B is computed as H(H_P; 0x02, H_M, n, k)

\EGverif{\veriftitleParameterValidation}{\label{verif:parameters}
\veriftextParameterValidation}

---- S3.2
\subsection{Key Generation}\label{sec:keygen}
Before an election, the number of guardians ($n$) is fixed together with a quorum value ($k$) that describes the number of guardians necessary to decrypt tallies and produce election verification data. The values $n$ and $k$ are integers subject to the constraint that $1\leq k \leq n$.  Canvassing board members can often serve the role of election guardians, and typical values for $n$ and $k$ could be 5 and 3 -- indicating that 3 of 5 canvassing board members must cooperate to produce the artifacts that enable election verification. The reason for not setting the quorum value $k$ too low is that it will also be possible for $k$ guardians to decrypt individual ballots.

\EGnote{Decryption of individual ballots does not directly compromise voter privacy since links between encrypted ballots and the voters who cast them are not retained by the system.  However, voters receive confirmation codes that can be associated with individual encrypted ballots, so any group that has the ability to decrypt individual ballots can also coerce voters by demanding to see their confirmation codes.}

Threshold encryption is used for encryption of ballots. This form of encryption makes it very easy to combine individual guardian public keys into a single public key for encrypting votes and ballots. It also offers a homomorphic property that allows individual encrypted votes to be combined to form encrypted tallies.

The guardians of an election will each generate a public-secret key pair. The public keys will then be combined (as described in the following section) into a single election public key which is used to encrypt all selections made by voters in the election.

At the conclusion of the election, each guardian will compute a verifiable partial decryption of each tally. These partial decryptions will then be combined to form full verifiable decryptions of the election tallies.

To accommodate the possibility that one or more of the guardians will not be available at the conclusion of the election to form their partial decryptions, the guardians will cryptographically share\footnote{Shamir A. (1979) \emph{How to Share a Secret}. Communications of the ACM, vol 22.} their secret keys amongst each other during key generation in a manner to be detailed in the next section. Each guardian will then compute a share of the secret decryption key, which it uses to form the partial decryptions.
A pre-determined quorum value ($k$) out of the ($n$) guardians will be necessary to produce a full decryption.

If the same set of $n$ guardians support multiple elections using the same threshold value $k$, the generated keys and key shares may be reused across several elections.

ref: S3a2 Guardians can generate individual public-secret key pairs
ref: S3a2 Guardians can exchange shares of secret keys
ref: S3a2 If the set of guardians and parameters k and n remain the same, they can re-use the same keys for multiple elections
ref: S3a2 A complete new set of keys must be generated if even a single guardian is replaced

S3.2 RI rejects any election manifest unless 1 <= k <= n < 2^31
S3.2 Ballots are encrypted using threshold encryption
S3.2 It is straightforward to combine individual guardian public keys into a single election public key
S3.2 Every guardian can Shamir-share their secret key during key generation
S3.2 All selections made by voters can be encrypted to the single election public key
S3.2 After the election, every guardian can compute a verifiable partial decryption of every tally
S3.2 'k' distinct guardian secret keys can produce a full decryption of every tally
S3.2 Fewer than 'k' distinct guardian secret keys can not produce a full decryption of any tally

---- S3.2.1
\subsubsection{Overview of key generation}
The $n$ guardians of an election are denoted by $G_1,G_2,\dots,G_n$.  Each guardian $G_i$ generates an independent public-secret key pair by generating a random integer secret $s_i\in\Z_q$ and forming the public key $K_i = g^{s_i} \bmod p$. Each of these public keys will be published in the election record together with a non-interactive zero-knowledge Schnorr proof of knowledge of the associated secret key.  

The joint election public key will be
\begin{equation}
  K = \prod_{i=1}^n K_i \bmod p.
\end{equation}
To enable robustness and allow for the possibility of missing guardians at the conclusion of an election, the \EG key generation includes a sharing of secret keys between guardians to enable decryption by any $k$ guardians.  This sharing is verifiable, so that receiving guardians can confirm that the shares they receive are correct; and the process allows for decryption without explicitly reconstructing secret keys of missing guardians.

Each guardian $G_i$ generates $k-1$ random polynomial coefficients $a_{i,j}$ such that $0<j<k$ and $0\leq a_{i,j} < q$ and forms the polynomial
\begin{equation*}
  P_i(x) = \sum_{j=0}^{k-1} a_{i,j} x^j \bmod q
\end{equation*}
by setting $a_{i,0}$ equal to its secret value $s_i$.  Guardian $G_i$ then publishes commitments $K_{i,j} = g^{a_{i,j}} \bmod p$ to each of its polynomial coefficients. As with the primary secret keys, each guardian should provide a Schnorr proof of knowledge of the secret coefficient value $a_{i,j}$ associated with each published commitment $K_{i,j}$. Since polynomial coefficients will be generated and managed in precisely the same fashion as secret keys, they will be treated together in a single step below.

At the conclusion of the election, individual encrypted ballots will be homomorphically combined into a single encrypted aggregate ballot -- consisting of an encryption of the tally for each option offered to voters. Each guardian will use its share of the secret decryption key to generate a partial decryption of each encrypted tally value, and these partial decryptions will be combined into full decryptions. If any election guardians are missing during tallying, any set of $k$ guardians who are available can cooperate to complete decryption.

All challenged ballots are individually decrypted in precisely the same fashion.

ref: S3.2 Each guardian can Shamir-share their secret key during key generation
S3.2.1 Receiving guardians can confirm that the key shares they receive are correct
S3.2.1 Every guardian can generate an independent public-secret key pair by generating a random integer secret s_i in Z_q
S3.2.1 Every guardian can form their guardian public key as K_i = g^{s_i} mod p
S3.2.1 The election record contains every guardian's public key
S3.2.1 The election record contains, for every guardian public key, a non-interactive zero-knowledge Schnorr proof of knowledge of the associated secret key
S3.2.1 The joint election public key K is computed as \prod_{i=1}^n K_i mod p
S3.2.1 Every guardian G_i can generate k - 1 random polynomial coefficients a_{i,j} such that 0 < j < k and 0 <= a_{i,j} < q
S3.2.1 Every guardian G_i can generate and publish commitments K_{i,j} = g^{a_{i,j}} mod p to each of its polynomial coefficients
S3.2.1 Guardian polynomial coefficients are generated and managed in precisely the same fashion as secret keys
S3.2.1 Individual encrypted ballots can be homomorphically combined into a single encrypted aggregate ballot
S3.2.1 The single encrypted aggregate ballot consists of an encryption of the tally for each contest (e.g. selection option) field
S3.2.1 Any set of k guardians' private keys is sufficient to complete decryption of the tally for each contest (e.g. selection option) field
S3.2.1 No set of fewer than k guardians' private keys is sufficient to complete decryption of the tally for any contest (e.g. selection option) field
S3.2.1 Any challenged ballot can be individually decrypted in the same fashion as the tally for a contest (e.g. selection option) field


---- S3.2.2
\subsubsection{Details of key generation}\label{sec:keygendetails}
\paragraph{Guardian coefficients and key pair.}
Each guardian $G_i$ in an election with a decryption threshold of $k$ generates $k$ secret polynomial coefficients $a_{i,j}$, for $0 \leq j < k$, by sampling them uniformly, at random in the range $0 < a_{i,j} < q$ and forms the polynomial
\begin{equation}
  P_i(x) = \sum_{j=0}^{k-1} a_{i,j} x^j \bmod q.
\end{equation}
Guardian $G_i$ then publishes commitments 
\begin{equation}
  K_{i,j} = g^{a_{i,j}} \bmod p
\end{equation}
for each of its polynomial coefficients $a_{i,j}$, for $0 \le j <k$. The constant term $a_{i,0}$ of this polynomial will serve as the secret key for guardian $G_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 $G_i$ and will also be denoted as $K_i = K_{i,0}$.
In order to prove possession of the coefficient associated with each public commitment, for each $K_{i,j}$ with $0\leq j < k$, guardian $G_i$ generates a Schnorr proof of knowledge for each of its coefficients as follows.

S3.2.2a Every guardian i can generate and store k secret polynomial coefficients (indexed as 0 <= j < k) by sampling a CSRNG uniformly as 0 < a_{i,j} < q
S3.2.2a Every guardian i can generate, store, and publish a Schnorr proof of knowledge for each of its k secret polynomial coefficients (indexed as 0 <= j < k).

\paragraph{NIZK Proof:} Guardian $G_i$ proves knowledge of secrets $a_{i,j}$ such that $K_{i,j}= g^{a_{i,j}} \bmod p$.

\noindent For each $0\leq j < k$, Guardian $G_i$ generates random integer values $u_{i,j}$ in $\Z_q$ and computes 
\begin{equation}
h_{i,j} = g^{u_{i,j}} \bmod p.
\end{equation}
Then, using the hash function $H$ (as defined in Section~\ref{sec:hashing} below), guardian $G_i$ performs a single hash computation
\begin{equation}\label{eq:hash_nizk_keygen}
  c_{i,j} = H(\HH_P; \mathtt{0x10}, i, j, K_{i,j}, h_{i,j})
\end{equation}
and publishes the Schnorr proof $(c_{i,j}, v_{i,j})$ consisting of the challenge value $c_{i,j}$ and the response value $v_{i,j} = (u_{i,j}-c_{i,j} a_{i,j}) \bmod q$ together with $K_{i,j}$.

\EGverifExtended{\veriftitleGuardianPublicKeyValidation}{\label{verif:guardiansPK}\veriftextGuardianPublicKeyValidation}
\footnote{This verification box and some others below contain computation steps as well as verification conditions. The former are numbered with decimal numerals, while the latter are numbered with capital letters alphabetically.}

It is worth noting here that for any fixed constant $\alpha$, the value $g^{P_i(\alpha)} \bmod p$ can be computed entirely from the published commitments as
\begin{equation}
g^{P_i(\alpha)} \bmod p = g^{\sum_{j=0}^{k-1} a_{i,j} \alpha^j}\bmod p
= \prod_{j=0}^{k-1} g^{a_{i,j} \alpha^j}\bmod p
= \prod_{j=0}^{k-1} (g^{a_{i,j}})^{\alpha^j}\bmod p
= \prod_{j=0}^{k-1} K_{i,j}^{\alpha^j} \bmod p.
\end{equation}

\EGnote{Although this formula includes double exponentiation -- raising a given value to the power $\alpha^j$ -- in what follows, $\alpha$ and $j$ will always be small values (bounded by $n$). This can also be reduced since the same result will be achieved if the exponents $\alpha^j$ are reduced to $\alpha^j \bmod q$.}

S3.2.2b [1/7] The Schnorr proof of knowledge for a guardian G_i coefficient 0 <= j < k is formed by
S3.2.2b [2/7] generating a random integer value by sampling a CSRNG uniformly as 0 <= u_{i,j} < q
S3.2.2b [3/7] computing h_{i,j} = g^{u_{i,j}} mod p.
S3.2.2b [4/7] computing challenge value c_{i,j} = H(H_P; 0x10, i, j, K_{i,j}, h_{i,j})
S3.2.2b [5/7] computing response value v_{i,j} = (u_{i,j} - c_{i,j}*a_{i,j}) mod q
S3.2.2b [6/7] the Schnorr proof is then the pair (c_{i,j}, v_{i,j}).
S3.2.2b [7/7] The Schnorr proof of knowledge for a guardian G_i coefficient 0 <= j < k can be published.

\paragraph{Share encryption.}
To share secret values amongst each other, each guardian $G_i$ encrypts its share for each other guardian $G_\ell$ using an encryption function $E_\ell$ that can be instantiated using that guardian's public/secret key pair $(K_\ell = g^{s_\ell} \bmod p, s_\ell)$ as laid out in the section describing the encryption of other data above. This means that each guardian $G_i$ publishes the encryption $E_\ell(P_i(\ell))$ for every other guardian $G_\ell$ as follows.

Guardian $G_i$ uses guardian $G_\ell$'s public key $K_\ell$ and a randomly-selected nonce $\xi_{i,\ell}\in\Z_q$ to compute 
\begin{equation}
(\alpha_{i,\ell}, \beta_{i,\ell}) = (g^{\xi_{i,\ell}} \bmod p, K_\ell^{\xi_{i,\ell}} \bmod p)
\end{equation}
and the secret key
\begin{equation}\label{eq:hash_shareenc}
  k_{i,\ell} = H(\HH_P; \mathtt{0x11}, i, \ell, K_\ell,\alpha_{i,\ell}, \beta_{i,\ell}).
\end{equation}
Using the keyed Hash Message Authentication Code \HMAC instantiated with \SHA, this key is used to derive\footnote{NIST (2022) \emph{Recommendation for Key Derivation Using Pseudorandom Functions}. In: SP 800-108r1 \url{https://csrc.nist.gov/publications/detail/sp/800-108/rev-1/final}.} the \MAC key 
\begin{equation}\label{eq:share_enc_MACkey}
k_0 = \HMAC(k_{i,\ell},\mathtt{0x01}\parallel\mathtt{Label}\parallel\mathtt{0x00}\parallel\mathtt{Context}\parallel\mathtt{0x0200})
\end{equation}
and the encryption key
\begin{equation}\label{eq:share_enc_ENCkey}
k_1 = \HMAC(k_{i,\ell},\mathtt{0x02}\parallel\mathtt{Label}\parallel\mathtt{0x00}\parallel\mathtt{Context}\parallel \mathtt{0x0200}),
\end{equation}
which both are 256 bits (32 bytes) long, and where $\mathtt{Label} = \bytes(\Str{share\_enc\_keys},14)$ and $\mathtt{Context} = \bytes(\Str{share\_encrypt},13)\parallel\bytes(i,4)\parallel\bytes(\ell,4)$.\footnote{This key derivation uses the KDF in counter mode from SP 800-108r1. The second input to \HMAC contains the counter in the first byte, the UTF-8 encoding of the string $\Str{share\_enc\_keys}$ as the \emph{Label} (encoding is denoted by $\bytes(\dots)$, see Section~\ref{sec:stringencoding}), a separation \texttt{0x00} byte, the UTF-8 encoding of the string $\Str{share\_encrypt}$ concatenated with encodings of the numbers $i$ and $\ell$ of the sending and receiving guardians as the \emph{Context}, and the final two bytes specifying the length of the output key material as 512 bits in total.}

Since $P_i(\ell)$ is an integer modulo $q$, it can be encoded as a byte array $\bytes(P_i(\ell),32)$ of exactly 32 bytes as specified in Section~\ref{sec:intmodq}. The encoded value is then encrypted as
\begin{equation}  
E_\ell(P_i(\ell)) = (C_{i,\ell,0},C_{i,\ell,1},C_{i,\ell,2}),
\end{equation}
where
\begin{equation}
C_{i,\ell,0} = g^{\xi_{i,\ell}} \bmod p,\quad 
C_{i,\ell,1} = \bytes(P_i(\ell),32) \oplus k_1,\quad  
C_{i,\ell,2} = \HMAC(k_0, \bytes(C_{i,\ell,0},512)\parallel C_{i,\ell,1}).
\end{equation}



S3.2.2c Every guardian G_i can encrypt its key share for every other guardian G_l to that guardian's public key K_l = g^{s_l} mod p
S3.2.2c [1/12] To encrypt its key share to that other guardian's public key K_l, guardian G_i
S3.2.2c [2/12] randomly-selects a nonce by sampling a CSRNG uniformly as 0 <= xi_{i,l} < q
S3.2.2c [3/12] computes alpha_{i,l} = g^{xi_{i,l}} mod p
S3.2.2c [4/12] computes beta_{i,l} = K_l^{xi_{i,l}} mod p
S3.2.2c [5/12] computes the secret key k_{i,l} = H(H_P; 0x11, i, l, K_l, alpha_{i,l}, beta_{i,l})
S3.2.2c [6/12] computes MAC key k_0(32 bytes) = HMAC(k_{i,l}, 0x01 || "share_enc_keys" (14 bytes) || 0x00 || "share_encrypt" (13 bytes) || i (4 bytes) || l (4 bytes) || 0x0200)
S3.2.2c [7/12] computes encryption key k_1(32 bytes) = HMAC(k_{i,l}, 0x02 || "share_enc_keys" (14 bytes) || 0x00 || "share_encrypt" (13 bytes) || i (4 bytes) || l (4 bytes) || 0x0200)
S3.2.2c [8/12] encodes P_i(l) as a 32 byte array per Section 5.1.2
S3.2.2c [9/12] computes C_{i,l,0}(512 bytes) = g^xi_{i,l} mod p
S3.2.2c [10/12] computes C_{i,l,1}(32 bytes) = P_i xor k_1
S3.2.2c [11/12] computes C_{i,l,2}(32 bytes) = HMAC(k_0, C_{i,l,0}(512 bytes) || C_{i,l,1}).
S3.2.2c [12/12] the encryption of P_i(l) is formed by E_l(P_i(l)) = (C_{i,l,0}, C_{i,l,1}, C_{i,l,2})


\paragraph{Share decryption.}
After receiving the ciphertext $(C_{i,\ell,0},C_{i,\ell,1},C_{i,\ell,2})$ from guardian $G_i$, guardian $G_\ell$ decrypts it by computing $\beta_{i,\ell} =(C_{i,\ell,0})^{s_\ell} \bmod p$, setting $\alpha_{i,\ell} = C_{i,\ell,0}$ and obtaining $k_{i,\ell} = H(\HH_P; \mathtt{0x11}, i, \ell, K_\ell,\alpha_{i,\ell}, \beta_{i,\ell})$. Now the \MAC key $k_0$ and the encryption key $k_1$ can be computed as above in Equations \eqref{eq:share_enc_MACkey} and \eqref{eq:share_enc_ENCkey}, which allows $G_\ell$ to verify the validity of the \MAC, namely that $C_{i,\ell,2} = \HMAC(k_0, \bytes(C_{i,\ell,0},512) \parallel C_{i,\ell,1})$. If the \MAC verifies, $G_\ell$ decrypts 
\begin{equation}
  \bytes(P_i(\ell),32) = C_{i,\ell,1}\oplus k_1.
\end{equation}



S3.2.2d Every guardian G_l must reject any received key share having a bad MAC value
S3.2.2d [1/9] Every guardian G_l can decrypt a correctly encrypted-and-MAC'd key share received from every other guardian G_i by
S3.2.2d [2/9] computes beta_{i,l} = (C_{i,l,0})^{s_l} mod p
S3.2.2d [3/9] computes alpha_{i,l} = C_{i,l,0}
S3.2.2d [4/9] computes k_{i,l} = H(H_P; 0x11, i, l, K_l, alpha_{i,l}, beta_{i,l})
S3.2.2c [5/9] computes MAC key k_0(32 bytes) = HMAC(k_{i,l}, 0x01 || "share_enc_keys" (14 bytes) || 0x00 || "share_encrypt" (13 bytes) || i (4 bytes) || l (4 bytes) || 0x0200)
S3.2.2c [6/9] computes encryption key k_1(32 bytes) = HMAC(k_{i,l}, 0x02 || "share_enc_keys" (14 bytes) || 0x00 || "share_encrypt" (13 bytes) || i (4 bytes) || l (4 bytes) || 0x0200)
S3.2.2d [7/9] uses a constant time method to compare received MAC C_{i,l,2} with HMAC(k_0, C_{i,l,0}(512 bytes) || C_{i,l,1})
S3.2.2d [8/9] rejects any received key share if the comparison determines they are not identical
S3.2.2d [9/9] computes P_i(l)(32 bytes) = C_{i,l,1} xor k_1



\paragraph{Share verification.}
Having decrypted each $P_i(\ell)$, guardian $G_\ell$ can now verify its validity against the commitments $K_{i,0},K_{i,1},\dots,K_{i,k-1}$ made by $G_i$ to its coefficients by confirming that the following equation holds:
\begin{equation}
g^{P_i(\ell)} \bmod p = \prod_{j=0}^{k-1}(K_{i,j})^{\ell^j} \bmod p.
\end{equation}
Guardians then publicly report having confirmed or failed to confirm this computation. If the recipient guardian $G_\ell$ reports not receiving a suitable value $P_i(\ell)$, it becomes incumbent on the sending guardian $G_i$ to publish this $P_i(\ell)$ together with the nonce $\xi_{i,\ell}$ it used to encrypt $P_i(\ell)$ under the public key $K_\ell$ of recipient guardian $G_\ell$. If guardian $G_i$ fails to produce a suitable $P_i(\ell)$ and nonce $\xi_{i,\ell}$ that match both the published encryption and the above equation, it should be excluded from the election and the key generation process should be restarted with an alternate guardian. If, however, the published $P_i(\ell)$ and $\xi_{i,\ell}$ satisfy both the published encryption and the equation above, the claim of malfeasance is dismissed, and the key generation process continues undeterred.\footnote{It is also permissible to dismiss any guardian that makes a false claim of malfeasance. However, this is not required as the sensitive information that is released as a result of the claim could have been released by the claimant in any case.} 

\EGverifExtended{\veriftitleElectionPublicKeyValidation}{\label{verif:electionPK}
\veriftextElectionPublicKeyValidation}


Each guardian $G_i$ will also need to compute the value
\begin{equation}
P(i) = \left(\sum_{j = 1}^n P_j(i)\right) \bmod q = \left(P_1(i) + P_2(i) + \dots + P_n(i)\right) \bmod q.
\end{equation}
for later use in decryption as will be described in Section~\ref{sec:decrypt_missing}.

At a minimum, guardian $G_i$ should retain the values $s_i$ and $P(i)$.
*** this is changing

S3.2.2e [1/4] Every guardian G_l, after having received and decrypted every key share from another guardian G_i,
S3.2.2e [2/4] verifies the k commitments K_{i, 0 <= j < k} made by G_i by
S3.2.2e [3/4] computing (g^{P_i(l)} mod p) [equality -> (confirmed|failed)] (\prod_{j=0}^{k-1}(K_{i,j})^{l^j} mod p)
S3.2.2e [4/4] publicly reports i, l, and ('confirmed' or 'failed').
S3.2.2e Every guardian G_i, in response to G_l reporting not receiving a suitable value P_i(l), can publish the P_i(l) and nonce xi_{i,l} they used to compute the key share to G_l
S3.2.2e [1/4] RI provides a utility to determine whether the published P_i(l) and xi_{i,l} match both the published encryption and the above equation.
S3.2.2e [2/4] This utility may also advise to
S3.2.2e [3/4] (if not matching) evict guardian G_i from the election on suspicion of malfeasance and restart the key generation process again with a different guardian, or
S3.2.2e [4/4] (if matching) absovle guardian G_i of suspicion of malfeasance and continue the key ceremony, optionally with suspicion on guardian G_l for having made a false claim of malfeasance.
S3.2.2e Every guardian G_i computes its share of the implicit secret key, P(i) = (sum_{j = 1}^n P_j(i)) mod q = (P_1(i) + P_2(i) + ... + P_n(i) mod q
S3.2.2e Every guardian G_i saves for later use its share of the implicit secret key, P(i)
S3.2.2e ***changed*** Every guardian G_i saves for later use its random integer secret s_i
S3.2.2e Every guardian G_i discards s_i at the end of the key generation ceremony

---- S3.2.3
\subsubsection{Extended base hash}\label{sec:extendedhash}
Once the baseline parameters have been produced and confirmed, the base hash $\HH_B$ is hashed with the election public key $K$  to form an extended base hash 
\begin{equation}\label{eq:extbasehash}
  \HH_E = H(\HH_B; \mathtt{0x12}, K)
\end{equation}
that will form the basis of subsequent hash computations.

\EGverif{\veriftitleExtendedBaseHashValidation}{\label{verif:extendedBaseHash}
\veriftextExtendedBaseHashValidation}

S3.2.3 The extended base hash is computed as H_E = H(H_B; 0x12, K) (reminder: K is election public key)

---- S3.3
\subsection{Ballot Encryption}\label{sec:ballotencryption}

Although there are some exceptions, an \EG ballot is typically 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 vote encryption.

---- S3.3.1
\subsubsection{Selection encryption}\label{sec:selectionencryption}
To encrypt a ballot entry $\sigma$, a random value $\xi$ is selected such that $0\leq \xi<q$, and $\sigma$ is encrypted as
\begin{equation}\label{eqn:encryptvote}
\Enc(\sigma,\xi) = (\alpha, \beta) = (g^\xi \bmod p,\ K^\sigma\cdot K^\xi \bmod p) = (g^\xi \bmod p,\ K^{\sigma+\xi} \bmod p).
\end{equation}
Specifically, for the typical case of $\sigma\in\{0,1\}$, one of the following two computations is performed.
\begin{itemize}
\item Zero (not selected, $\sigma=0$) is encrypted as $\Enc(0,\xi) = (g^\xi \bmod p,\ K^\xi \bmod p)$.  
\item One (selected, $\sigma=1$) is encrypted as $\Enc(1,\xi) = (g^\xi \bmod p,\ K^{1+\xi} \bmod p)$.
\end{itemize}
The notation $\Enc(\sigma,\xi)$ for this homomorphically additive encryption includes the encryption nonce $\xi$. In cases, where the nonce does not need to be referenced, $\Enc(\sigma)$ is sometimes used for clarity.

Note that if multiple encrypted votes $(g^{\xi_i} \bmod p,\ K^{\sigma_i+\xi_i} \bmod p)$ are formed, their component-wise product $(g^{\sum_i \xi_i} \bmod p,\ K^{\sum_i \sigma_i + \sum_i \xi_i} \bmod p)$ serves as an encryption of $\sum_i \sigma_i$---which is the tally of those votes.\footnote{The initial decryption actually forms the value $g^{\sum_i \sigma_i} \bmod p$. However, since $\sum_i \sigma_i$ is a relatively small value, it can be effectively computed from $g^{\sum_i \sigma_i} \bmod p$ by means of an exhaustive search or similar methods.}

Some cardinal voting methods like cumulative voting, score voting, STAR-voting, and Borda count may require the encryption of small positive integers $\sigma$ greater than $1$ that represent multiple allowed votes or weighted votes. In all these cases, encryption is done as shown in Equation~\eqref{eqn:encryptvote}.

TODO QUESTION: Should the addition sigma plus xi_i,j be mod p? Seems unlikely, but wrapping at some fixed width would be bad.

S3.3.1 [1/7] RI allows to encrypt a ballot entry 'sigma' by
S3.3.1 [2/7] generating a random value xi by sampling a PRF (described in 3.3.2) uniformly as 0 <= xi < q
S3.3.1 [3/7] computing alpha = g^xi mod p
S3.3.1 [4/7] computing beta = (K^sigma * K^xi) mod p = K^{sigma + xi} mod p
S3.3.1 [5/7] Note that in the common case of sigma = 0, beta = K^xi mod p
S3.3.1 [6/7] and       in the common case of sigma = 1, beta = K^{1 + xi} mod p
S3.3.1 [7/7] Finally, Enc(sigma, xi) = (alpha, beta).

---- S3.3.2
\subsubsection{Generation of encryption nonces}\label{sec:noncegen}
The “random” nonces used for vote encryption on a single ballot $B$ are all derived from a single 256-bit \emph{ballot nonce} $\xi_B$. It is assumed that each contest has a label $\Lambda$ and that within each contest each possible option has a label $\lambda$, which are specified in the election manifest. The manifest also specifies a unique sequence order of contests and options within contests. Within the $i$-th contest, which has contest label $\Lambda_i$, the nonce $\xi_{i,j}$ used to encrypt the selection for the $j$-th option, which has option label $\lambda_j$, is derived as
\begin{equation}\label{eq:noncegen}
  \xi_{i,j} = H(\HH_E; \mathtt{0x20},\xi_B,\indc(\Lambda_i),\indo(\lambda_j)).
\end{equation}

Ballot nonces may be independent across different ballots, and only the nonces used to encrypt ballot selections need to be derived from the ballot nonce.\footnote{As will be seen below, in addition to encryption of voter selections, an \EG ballot contains additional encryptions that enable independent verification of a ballot's correctness.  The nonces used for these additional encryptions do not need to be derived from the ballot nonce $\xi_B$.}  The use of a single ballot nonce for each ballot allows the entire ballot encryption to be re-derived from the contents of a ballot and the ballot nonce. It also allows the encrypted ballot to be fully decrypted with the single ballot nonce.

Since access to a ballot nonce $\xi_B$ enables decryption of the ballot which it encrypted, ballot nonces must be protected carefully.  Typically, ballot nonces will be destroyed immediately after they are used.  But there are several scenarios which warrant the preservation of ballot nonces---sometimes only briefly, but sometimes for an extended period.

To accommodate preservation of ballot nonces, an \EG manifest may optionally provide a public key to be used for encryption of ballot nonces. This public key may be the same as the election key used to encrypt voter selections, but some scenarios warrant the use of an independent public key.  If such a key is provided, \EG uses that key to encrypt each ballot's ballot nonce $\xi_B$ and return this encryption together with the encrypted ballot.  There are also some scenarios in which ballot nonces are encrypted with symmetric keys. Any such symmetric key should never be published, and the process for managing these symmetric keys is outside of the scope of this specification.



S3.3.2 RI allows to "encrypt a voted plaintext ballot" `BallotSate::CompletedPlaintext` comprised of an election manifest label, a ballot style label, and a set of voter-assigned contest option selections (sigma).
S3.3.2 [1/5] RI can process any `BallotSate::CompletedPlaintext` ballot:
S3.3.2 [2/5] generate ballot nonce xi_B by sampling a CSRNG uniformly as 0 <= xi_B < 2^(len(q))
S3.3.2 [3/5] impose contest and option selection limits to voter-assigned fields
S3.3.2 [4/5] assign appropriate values to system-assigned fields (e.g. overvote, undervote, write-ins, etc.)
S3.3.2 [5/5] for each contest i and field ("option") j, generate xi_{i,j} = H(H_E; 0x20, xi_B, i (4 bytes), j (4 bytes))
S3.3.2 RI allows to save xi_B
S3.3.2 RI allows to destroy xi_B immediately after it is used
S3.3.2 RI allows to encrypt xi_B to the election public key K
S3.3.2 RI allows to encrypt xi_B to a public key specified in the election manifest
S3.3.2 RI allows to use a private key to decrypt an xi_B encrypted to a public key
S3.3.2 RI allows to encrypt xi_B to a symmetric key TBD
S3.3.2 RI allows to store an encryption of xi_B
S3.3.2 RI allows ballot nonces that are independent across different ballots
S3.3.2 RI requires the nonces used to encrypt ballot selections be derived from the ballot nonce
S3.3.2 RI the single ballot nonce can be used to fully decrypt the encrypted ballot selections
S3.3.2 OI may use additional nonces (not necessarily derived from the ballot nonce) to encrypt additional encryptions (not ballot selections)
S3.3.2 OI all of any additional nonces can be used to decrypt any additional encryptions
S3.3.2 RI allows ballot nonces to be protected carefully
S3.3.2 RI allows ballot nonces to be destroyed immediately after they are used
S3.3.2 RI allows ballot nonces to be preserved briefly or for an extended period
S3.3.2 manifest may provide an optional public key used for encryption of ballot nonces
S3.3.2 any optional public key used for encryption of ballot nonces may be the same as the election key used to encrypt voter selections
S3.3.2 any optional public key used for encryption of ballot nonces may be an independent public key
S3.3.2 any optional public key used for encryption of ballot nonces is used to encrypt each ballot's ballot nonce xi_B
S3.3.2 if the manifest provides any optional public key for encryption of ballot nonces, each ballot's ballot nonce xi_B encryption is returned with the encrypted ballot

S3.3.2 a symmetric key may be used for encryption of ballot nonces
S3.3.2 if a symmetric key is used for encryption of ballot nonces, RI allows to keep it secret

---- S3.3.3
\subsubsection{Ballot well-formedness}

\paragraph{Contest selection limits.} 
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 \EG, but it may be enabled in a future version.\footnote{Benaloh J., Moran. T, Naish L., Ramchen K., and Teague V. (2009) \emph{Shuffle-Sum:  Coercion-Resistant Verifiable Tallying for STV Voting} in Transactions of Information Forensics and Security.} 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\footnote{Chaum D. (1981) \emph{Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms} Communications of the ACM.} design.

S3.3.3a RI allows approval voting by setting the selection limit to the total number of options in a contest
S3.3.3a Ranked choice voting may be enabled in a future version.

\paragraph{Undervotes.}
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, in previous versions of \EG (up to v1.1), the internal representation of a contest was augmented with “placeholder” options equal in number to the selection limit. Placeholder options were 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, \EG used a single placeholder option that can be thought of as a “none of the above” option. The current version of \EG adopts a different approach to accomodate undervotes and allows the total number of selected options to lie in a range between $0$ and the selection limit. This has lower computational cost and leads to smaller election records.

S3.3.3b RI allows the total number of selected options to lie in a range between 0 and the selection limit

\paragraph{Overvotes.}
When the number of selections made by the voter exceeds the selection limit for a specific contest, the votes in the contest become invalid as an overvote. To not affect the election tallies, all selectable options in the contest are set to zero (unselected). To record that an overvote has occurred and what specific selections were made by the voter in this contest, this information is encoded into a contest data field, together with other data such as write-in text. This data is then encrypted with the election public key using the hashed ElGamal encryption described in Section~\ref{sec:encrypt_ext_data}.

S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, the votes in the contest become invalid as an overvote.
S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, all selectable options in the contest are set to zero (unselected)
S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, all selectable options in the contest do not affect the election tallies
S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, the fact that an overvote has occurred is encoded into a contest data field and encrypted to the election public key using the hashed ElGamal encryption
S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, the voter's specific selections in this contest is encoded into a contest data field and encrypted to the election public key using the hashed ElGamal encryption
S3.3.3c When the number of selections made by the voter exceeds the selection limit for a specific contest, other data such as write-in text is encoded into a contest data field and encrypted to the election public key using the hashed ElGamal encryption

\paragraph{Ballot well-formedness}.
Two things must now be proven about the encryption of each vote to ensure a ballot is well-formed.
\begin{enumerate}
\item The encryption associated with each option is an encryption of a legitimate value---usually either an encryption of zero or an encryption of one.
\item The sum of all encrypted selections in each contest lies in the range between $0$ and the selection limit $L$ for that contest (usually $L=1$), i.e. it is an encryption of one of the values $0,1, \dots, L$.
\end{enumerate}
The use of DPP vote encryption enables efficient zero-knowledge proofs of these requirements, and the Fiat-Shamir heuristic can be used to make these proofs non-interactive. Chaum-Pedersen 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---usually 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 a non-negative value that is at most the contest's selection limit---again using Chaum-Pedersen proofs combined with the Cramer-Damgård-Schoenmakers technique.

S3.3.3d RI allows to prove the encryption associated with each option is an encryption of a legitimate value (e.g., either an encryption of zero or an encryption of one.)
S3.3.3d RI allows to prove the sum of all encrypted selections in each contest lies in the range between $0$ and the selection limit $L$ for that contest (usually $L=1$), i.e. it is an encryption of one of the values $0,1, \dots, L$.
S3.3.3d RI uses DPP vote encryption to enable efficient zero-knowledge proofs
S3.3.3d RI uses the Fiat-Shamir heuristic can be used to make these proofs non-interactive
S3.3.3d RI uses Chaum-Pedersen proofs combined with the Cramer-Damgård-Schoenmakers technique to show the result of homomorphically combining the encryptions of selections in a contest are an encryption of a non-negative value that is at most the contest's selection limit.


\paragraph{Cardinal voting methods.}
A range proof, i.e. a proof that a ciphertext is an encryption of one of the values $0,1,\dots,L$ is a generalization of the proof that a ciphertext is an encryption of zero or one. It can be used to prove well-formedness of an individual selection when it is allowed for options to receive multiple votes in a contest by a single voter. Using range proofs with a range up to a certain option selection limit for the individual option as well as the contest selection sum therefore enables cardinal voting methods such as cumulative voting, score voting, STAR-voting, and Borda count in \EG.


S3.3.3e Range proofs can be used to prove well-formedness of an individual selection when it is allowed for options to receive multiple votes in a contest by a single voter
S3.3.3e Range proofs can be used for individual options
S3.3.3e Range proofs can be used for the contest selection sum
S3.3.3e Range proofs enable cumulative voting
S3.3.3e Range proofs enable score voting
S3.3.3e Range proofs enable STAR-voting
S3.3.3e Range proofs enable Borda count



---- S3.3.4
\subsubsection{Outline for proofs of ballot correctness}
This section provides the outlines for different types of encryption proofs that aim to give an understanding of how they work. It starts with the proof that a given ciphertext is an encryption of the value $0$. Based on that, it explains how it can be proved that a ciphertext is an encryption of the value $1$. It then combines those to arrive at the base case used in \EG, namely that a ciphertext is an encryption of $0$ or $1$. Finally, it shows how the latter is generalized to generate range proofs, i.e. proofs that a ciphertext encrypts a value in a range $0,1,\dots,L$.

S3.3.4a none


\paragraph{NIZK Proof that $(\alpha,\beta)$ is an encryption of zero.}
To prove that ciphertext $(\alpha,\beta)$ is an encryption of zero, the Chaum-Pedersen protocol proceeds as follows.
This proof assumes knowledge of the secret encryption nonce $\xi$. The prover selects a random value $u$ in $\Z_q$ and commits to the pair $(a,b)= (g^u \bmod p,\ K^u \bmod p)$. A hash computation is then performed (using the Fiat-Shamir heuristic) to create a pseudo-random challenge value $c = H(\HH_E,K,\alpha,\beta,a,b)$, and the prover responds with $v = (u-c\xi) \bmod q$. A verifier can now confirm the claim by checking that both $g^v\cdot \alpha^c \equiv_p a$ and $K^v\cdot \beta^c \equiv_p b$ are true.

TODO revisit this section if we need it
S3.3.4b


\paragraph{NIZK Proof that $(\alpha,\beta)$ is an encryption of one.}
To prove that $(\alpha,\beta)$ is an encryption of one, $\beta/K \bmod p$ is substituted for $\beta$ in the above. The verifier can be relieved of the need to perform a modular division by computing $\beta K^{q-1} \bmod p$ rather than $\beta/K \bmod p$. As an alternative, the verifier can confirm that $K^{(v-c) \bmod q}\cdot \beta^c \equiv_p b$ instead of $K^v\cdot (\beta/K)^c \equiv_p b$.

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 particular challenge $c$ is known to be forthcoming, a prover can generate a random $v\in\Z_q$ and commit to $(a,b) = (g^v\alpha^c \bmod p,\ K^v\beta^c \bmod p)$.  This selection will satisfy the required checks for $(\alpha,\beta)$ to appear as an encryption of zero regardless of the values of $(\alpha,\beta)$. Similarly, setting $(a,b) = (g^v\alpha^c \bmod p,\ K^{(v-c)\bmod q}\beta^c \bmod p)$ will satisfy the required checks for $(\alpha,\beta)$ to appear as an encryption of one regardless of the values of $(\alpha,\beta)$. This quirk is what enables the Cramer-Damgård-Schoenmakers technique to prove a disjunction of two predicates.

TODO revisit this section if we need it
S3.3.4c


\paragraph{Sketch of NIZK Proof that $(\alpha,\beta)$ is an encryption of zero or one.}
The prover starts with whichever statement is \emph{not} true, generates a random challenge for it, and then derives the commitment from it to be able to produce a false proof, as described in the previous paragraph. For example, if $(\alpha, \beta)$ is an encryption of one, the prover chooses a challenge $c_0$ and a response at random, then derives values for $(a_0,b_0)$ so that the `response' satisfies the `challenge'; if $(\alpha, \beta)$ is an encryption of zero, the prover chooses $c_1$ and a response at random and derives satisfying values for $(a_1,b_1)$. The prover then works on the true part. It generates a truthful commitment $(a_0,b_0)$ like the first part of a proof of an encryption of zero (or a truthful commitment $(a_1,b_1)$ like the first part of a proof of an encryption of one, whichever is true). A single challenge value $c$ is selected by hashing all commitments and baseline parameters. The prover must produce challenge values $c_0$ and $c_1$ s.t. $c = c_0 + c_1 \bmod q$. It answers its false claim with the challenge it chose in the beginning ($c_0$ if $(\alpha,\beta)$ is an encryption of one, $c_1$ if it is an encryption of zero), then derives the other challenge by subtraction ($c_1 = c - c_0 \bmod q$ or $c_0 = c - c_1 \bmod q$ as needed). It then finishes the proof of the true part as usual, using this challenge. An observer can see that one of the claims must be true but cannot tell which.

TODO revisit this section if we need it
S3.3.4d


\paragraph{Sketch of NIZK Proof that $(\alpha,\beta)$ is an encryption of an integer $\ell$ such that $0\leq \ell \leq R$.}
The above method to prove that $(\alpha,\beta)$ is an encryption of zero or one can be extended to more than two values in an analogous way. Now, the prover needs to produce false proofs that verify for all values that are not encrypted in the ciphertext. This means that for each $i$ with $0\leq i \leq R$ and $i\neq\ell$, the prover selects a challenge value $c_i$ and a response at random and uses them to create commitments $(a_i, b_i)$ that make the response verify the challenge for the false claim that $(\alpha,\beta)$ is an encryption of the value $i \neq \ell$. For the true assertion that $(\alpha,\beta)$ is an encryption of $\ell$, the prover makes honest commitments $(a_\ell, b_\ell)$. At this point, there exist commitments $(a_i, b_i)$ for all $0\leq i \leq R$ and a single challenge value $c$ is selected by hashing all these commitments. The remaining challenge value $c_\ell$ is then uniquely determined by the constraint $c = (c_0 + \dots + c_\ell + \dots + c_R) \bmod q$ and can be computed by subtracting from $c$ all other challenge values that were chosen for the false proofs. The challenge $c_\ell$ must be used to answer the true assertion that $(\alpha,\beta)$ is an encryption of $\ell$. The proof now consists of all challenge and response pairs, including the honestly generated one for the true assertion and $R$ faked pairs for the false assertions.

TODO revisit this section if we need it
S3.3.4e


---- S3.3.5

\subsubsection{Details for proofs of ballot correctness}\label{sec:proofsballotcorrectness}
This subsection begins with the special but common case where a selection is either a $0$ or a $1$, which means that the range bound is $R=1$. Both cases---unselected (encryption of $0$) and selected (encryption of $1$) are spelled out in detail before the general case range proof is specified.  An \EG implementation can directly implement the general range proof and use it in the
special case $R=1$. There is no need to implement the case $R=1$ separately.

S3.3.5a none


\paragraph{Unselected option.}
To encrypt an “unselected” option on a ballot, a pseudo-random nonce $\xi\in\Z_q$ for the selection is derived from the ballot nonce $\xi_B$ as described in Section~\ref{sec:noncegen}, and an encryption of zero is formed as $(\alpha,\beta)=(g^\xi \bmod p,\ K^\xi \bmod p)$.


S3.3.5b RI encrypts an "unselected" option as a value of 0
S3.3.5b [dup S3.3.1 ?] [1/4] RI encrypts an "unselected" option as a value of 0 by
S3.3.5b [dup S3.3.1 ?] [2/4] deriving a pseudo-random nonce xi in Z_q from the ballot nonce xi_B as described in 3.3.2
S3.3.5b [dup S3.3.1 ?] [3/4] computing alpha = g^xi mod p
S3.3.5b [dup S3.3.1 ?] [4/4] computing beta = K^xi mod p


\paragraph{NIZK Proof:} Proves that $(\alpha,\beta)$ is an encryption of zero or one.\\
(Requires knowledge of encryption nonce $\xi$ for which $(\alpha,\beta)$ is an encryption of zero.)

\noindent To create the proof that $(\alpha,\beta)$ is an encryption of a zero or a one, randomly select $u_0$, $u_1$, and $c_1$ from $\Z_q$ and compute  
\begin{equation}
  (a_0,b_0 ) = (g^{u_0} \bmod p,\ K^{u_0} \bmod p)
\end{equation}
and 
\begin{equation}
  (a_1,b_1) = (g^{u_1} \bmod p,\ K^{u_1-c_1} \bmod p).
\end{equation}
A challenge value $c$ is formed by hashing the extended base hash $\HH_E$ together with $\alpha$, $\beta$, $a_0$, $b_0$, $a_1$ and $b_1$, namely

\begin{equation}\label{eq:encproof0_challenge}
  c = H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1).
\end{equation}
The proof consists of the four values $c_0$, $c_1$, $v_0$, and $v_1$ which are computed as follows.
\begin{align}
c_0 & = (c-c_1) \bmod q,\\
v_0 & = (u_0-c_0\cdot \xi) \bmod q,\\
v_1 & = (u_1-c_1\cdot \xi) \bmod q.
\end{align}
These computed values satisfy the proof equations as follows.
\begin{align}
c & = ((c-c_1)+c_1) \bmod q = (c_0+c_1) \bmod q,\\
(g^{v_0} \alpha^{c_0}, K^{v_0} \beta^{c_0}) & \equiv_p (g^{u_0-c_0 \xi} g^{c_0 \xi}, K^{u_0-c_0 \xi} K^{c_0 \xi}) 
\equiv_p (a_0, b_0),\\
(g^{v_1} \alpha^{c_1}, K^{v_1-c_1} \beta^{c_1}) & \equiv_p (g^{u_1-c_1 \xi} g^{c_1 \xi}, K^{u_1-c_1 \xi - c_1} K^{c_1 \xi}) \equiv_p (a_1, b_1).
\end{align}

vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv dup
\noindent To create the proof that $(\alpha,\beta)$ is an encryption of a zero or a one, randomly select $u_0$, $u_1$, and $c_1$ from $\Z_q$ and compute  
\begin{equation}
  (a_0,b_0 ) = (g^{u_0} \bmod p,\ K^{u_0} \bmod p)
\end{equation}
and 
\begin{equation}
  (a_1,b_1) = (g^{u_1} \bmod p,\ K^{u_1-c_1} \bmod p).
\end{equation}
A challenge value $c$ is formed by hashing the extended base hash $\HH_E$ together with $\alpha$, $\beta$, $a_0$, $b_0$, $a_1$ and $b_1$, namely

\begin{equation}\label{eq:encproof0_challenge}
  c = H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1).
\end{equation}
The proof consists of the four values $c_0$, $c_1$, $v_0$, and $v_1$ which are computed as follows.
\begin{align}
c_0 & = (c-c_1) \bmod q,\\
v_0 & = (u_0-c_0\cdot \xi) \bmod q,\\
v_1 & = (u_1-c_1\cdot \xi) \bmod q.
\end{align}
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ dup

S3.3.5c RI creates proof encrypted option value from S3.3.5b is an encryption of 0
S3.3.5c generate u_0 by sampling a CSRNG uniformly as 0 <= u_0 < Z_q
S3.3.5c generate u_1 by sampling a CSRNG uniformly as 0 <= u_1 < Z_q
S3.3.5c generate c_1 by sampling a CSRNG uniformly as 0 <= c_1 < Z_q
S3.3.5c compute a_0 = g^{u_0} mod p
S3.3.5c compute b_0 = K^{u_0} mod p
S3.3.5c compute a_0 = g^{u_0} mod p
S3.3.5c compute b_0 = K^{u_0} mod p
S3.3.5c compute c = H(H_E; 0x21, K, alpha, beta, a_0, b_0, a_1, b_1)
S3.3.5c c_0 & = (c-c_1) mod q
S3.3.5c v_0 & = (u_0 - c_0 cdot xi) mod q
S3.3.5c v_1 & = (u_1 - c_1 cdot xi) mod q

S3.3.5c 


\paragraph{Selected option.}
To encrypt a “selected” option on a ballot, a pseudo-random nonce $\xi\in\Z_q$ for the selection is derived from the ballot nonce $\xi_B$ as described in Section~\ref{sec:noncegen}, and an encryption of one is formed as $(\alpha,\beta) = (g^\xi  \bmod p,\ K^{\xi+1} \bmod p)$.

S3.3.5d RI encrypts an "selected" option as a value of 1
S3.3.5d [dup S3.3.1 ?] [1/4] RI encrypts a "selected" option as a value of 1 by
S3.3.5d [dup S3.3.1 ?] [2/4] deriving a pseudo-random nonce xi in Z_q from the ballot nonce xi_B as described in 3.3.2
S3.3.5d [dup S3.3.1 ?] [3/4] computing alpha = g^xi mod p
S3.3.5d [dup S3.3.1 ?] [4/4] computing beta = K^(xi + 1) mod p




\paragraph{NIZK Proof:} Proves that $(\alpha,\beta)$ is an encryption of zero or one.\\
(Requires knowledge of encryption nonce $\xi$ for which $(\alpha,\beta)$ is an encryption of one.)

\noindent To create the proof that $(\alpha,\beta)$ is an encryption of a zero or a one, randomly select $u_0$, $u_1$, and $c_0$ from $\Z_q$ and compute
and 
\begin{equation}
  (a_0,b_0) = (g^{u_0} \bmod p,\ K^{u_0+c_0}\bmod p)
\end{equation}
and
\begin{equation}
  (a_1,b_1) = (g^{u_1} \bmod p,\ K^{u_1} \bmod p).
\end{equation}
A challenge value $c$ is formed by hashing the extended base hash $\HH_E$ together with $\alpha$, $\beta$, $a_0$, $b_0$, $a_1$, and $b_1$, namely 

\begin{equation}\label{eq:encproof1_challenge}
  c = H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1).
\end{equation}
The proof consists of the four values $c_0$, $c_1$, $v_0$, and $v_1$ which are computed as follows.
\begin{align}
c_1 & =(c-c_0) \bmod q,\\
v_0 & =(u_0-c_0\cdot \xi) \bmod q,\\
v_1 & =(u_1-c_1\cdot \xi) \bmod q.
\end{align}
These computed values satisfy the proof equations as follows.
\begin{align}
c & =(c_0+(c-c_0)) \bmod q = (c_0+c_1 ) \bmod q,\\
(g^{v_0} \alpha^{c_0}, K^{v_0} \beta^{c_0}) & \equiv_p (g^{u_0-c_0 \xi} g^{c_0 \xi}, K^{u_0-c_0 \xi} (K^{\xi+1})^{c_0})
\equiv_p (g^{u_0}, K^{u_0+c_0}) \equiv_p (a_0, b_0),\\
(g^{v_1} \alpha^{c_1}, K^{v_1-c_1} \beta^{c_1}) & \equiv_p (g^{u_1-c_1 \xi} g^{c_1 \xi}, K^{u_1-c_1 \xi-c_1} (K^{\xi+1})^{c_1})
\equiv_p (a_1, b_1).
\end{align}

S3.3.5e



The remainder of this section specifies the general case of a range proof used for encrypting a selection. It is a straightforward generalization of the method for proofs of encryptions of $0$ or $1$ described above. Any zero-knowledge proof that asserts a ciphertext $(\alpha, \beta)$ encrypts an integer value $\sigma$ in the range $0, 1, \dots, R$ for some integer $R$ is computed in detail as follows.   
\paragraph{NIZK Proof:} Proves that $(\alpha,\beta)$ is an encryption of an integer in the range $0,1,\dots,R$.\\(Requires knowledge of encryption nonce $\xi$ for which $(\alpha,\beta)$ is an encryption of $\ell$.)

\noindent A disjunctive Chaum-Pedersen range proof of $(\alpha,\beta)$ being an encryption of an integer in the range $0,1,\dots,R$ is produced as follows. First, for each $0\leq j \leq R$, a random $u_j\in\Z_q$ is selected. The commitment 
\begin{equation}
  (a_\ell,b_\ell) = (g^{u_\ell} \bmod p,\ K^{u_\ell} \bmod p)
\end{equation}
for $j=\ell$ is computed from $u_\ell$ alone. In addition, for each $0\leq j \leq R$ with $j\neq \ell$, random $c_j\in\Z_q$ are selected and commitments are computed as
\begin{equation}
  (a_j,b_j) = (g^{u_j} \bmod p,\ K^{t_j} \bmod p),
\end{equation}
where $t_j = (u_j + (\ell-j)c_j) \bmod q$. Next, all the $a_j, b_j$ values are hashed together with the ciphertext and the election's extended base hash $\HH_E$ to form a pseudo-random challenge
\begin{equation}
  c = H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1,\dots,a_R,b_R).
\end{equation}
The remaining challenge value $c_\ell$ is determined as 
\begin{equation}
c_\ell = \left(c - \sum_{j\neq \ell} c_j\right) \bmod q = (c - (c_0 + \dots + c_{\ell-1} + c_{\ell + 1} + \dots + c_R)) \bmod q. 
\end{equation}
Finally, responses are computed for all $0\leq j \leq R$ as 
\begin{equation}
  v_j = (u_j-c_j\xi) \bmod q
\end{equation}
and the proof consists of the challenge values $c_0, c_1, \dots, c_R$ and the response values $v_0, v_1, \dots, v_R$.
Note that a range proof 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 nonce $\xi$ used for the selection encryption.

Specializing the general range proof with $R=1$ and $\ell=0$ is identical to the proof of the unselected option above, i.e. the ciphertext is an encryption of $0$ or $1$ given that it is an encryption of $0$. Likewise, setting $R=1$ and $\ell = 1$ is identical to the proof of the selected option. 

\EGnote{Because all the exponentiations required to encrypt and prove ballot components have a base of either $g$ or $K$, implementations can be optimized by pre-computing tables of powers of these two bases. These tables can be further optimized by computing and storing the table values in Montgomery form.}

\EGverif{\veriftitleCorrectnessOfSelectionEncryptions}{\label{verif:selection}
\veriftextCorrectnessOfSelectionEncryptions}

S3.3.5e


vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv dup
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ dup



---- S3.3.6
\subsubsection{Encryption of contest data}\label{sec:encrypt_ext_data}
For each contest, \EG maintains a contest data field. The information held in this field must be encoded in a byte array $D$ of a fixed length of $32\cdot b_D$ bytes, where $b_D$ is the smallest value large enough for $D$ to capture all additional information from the ballot that needs to be retained and stored in encrypted form as part of the encrypted ballot. This information consists of any text written into one or more write-in text fields, information about overvotes, undervotes, and null votes, and possibly other data about voter selections. This single data field containing all such data associated with the contest is encrypted with the election public key in a single hashed ElGamal encryption as follows.

Write the contest data field as a concatenation of blocks 
\begin{equation}
   D = D_{1}\parallel D_{2} \parallel \dots\parallel D_{b_D},
\end{equation}
where the $D_{i}$, $1\leq i \leq b_D$, consist of 32 bytes each. To encrypt it with the public election key $K$, a pseudo-random nonce $\xi$ is derived from the ballot nonce $\xi_B$ and the contest label $\Lambda$ as 
\begin{equation}\label{eq:noncegen_contestdata}
  \xi = H(\HH_E; \mathtt{0x20}, \xi_B, \indc(\Lambda), \mathtt{``contest\_data"})
\end{equation} 
to compute $(\alpha, \beta) = (g^\xi \bmod p, K^\xi \bmod p)$. A 256-bit secret key is derived as the hash 
\begin{equation}\label{eq:k_enc_contest}
  k = H(\HH_E; \mathtt{0x22},K ,\alpha, \beta).
\end{equation}

Next, a \KDF in counter mode\footnote{NIST (2022) \emph{Recommendation for Key Derivation Using Pseudorandom Functions}. In: SP 800-108r1 \url{https://csrc.nist.gov/publications/detail/sp/800-108/rev-1/final}. Note that the secret session key $k$ changes for every encryption because a fresh encryption nonce $\xi$ is pseudo-randomly generated every time. The second input to \HMAC consists of the byte encoding of the counter $i$, the UTF-8 encoding of the string $\Str{data\_enc\_keys}$ as the fixed \emph{Label} field specified in SP 800-108r1, the separating \texttt{00} byte, the UTF-8 encoding of the string $\Str{contest\_data}$ as the \textit{Context} field, and the 4-byte encoding of the length of the total key material output in bits.} based on \HMAC is used to generate a \MAC key $k_0$ and encryption keys  $k_1 \parallel k_2 \parallel \dots \parallel k_{b_D}$ by computing
\begin{equation}
  k_i = \HMAC(k,\bytes(i,4)\parallel\mathtt{Label}\parallel\mathtt{0x00}\parallel\mathtt{Context}\parallel \bytes((b_D+1)\cdot 256,4)),
\end{equation}
for $0 \leq i \leq b_D$. The label and context byte arrays are $\mathtt{Label} = \bytes(\mathtt{``data\_enc\_keys"}, 13)$ and $\mathtt{Context} = \bytes(\mathtt{``contest\_data"}, 12)\parallel \bytes(\indc(\Lambda), 4)$. Each $k_i$ is a 256-bit key, and $\bytes(i,4)$ and $\bytes((b_D+1)\cdot 256,4)$ are byte arrays of the fixed length of 4 bytes that encode the integers $i$ and $(b_D+1)\cdot 256$. Therefore, $i$ and $(b_D+1)\cdot 256$ must be less than $2^{32}$, i.e. $0 \leq i < 2^{32}$ and $1 \leq b_D+1 < 2^{24}$.

The ciphertext encrypting $D$ is $C_D = (C_0, C_1, C_2)$, where 
\begin{align}
  C_0 & = \alpha=g^\xi \bmod p,\\ 
  C_1 & = D_{1}\oplus k_1 \parallel D_{2}\oplus k_2 \parallel \dots \parallel D_{b_D}\oplus k_{b_D},\\
  C_2 & = \HMAC(k_0,C_0\parallel C_1).
\end{align}
The component $C_1$ is computed by bitwise XOR (here denoted by $\oplus$) of each data block $D_{i}$ with the corresponding key $k_i$. Component $C_2$ is a message authentication code.

---- S3.3.7
\subsubsection{Contest data}
The contest data can contain different kinds of information such as undervote, null vote, and overvote information together with the corresponding selections, the text captured for write-in options and other data associated to the contest.

\paragraph*{Overvote, undervote, and null vote information.}
The first part of the contest data field for a contest contains information on overvotes, undervotes, or null votes. 

If the number of selections in a contest exceeds the selection limit, an overvote has occurred and the votes in this contest are invalid. To not affect the tallies, \EG handles an overvote situation as follows.

\begin{enumerate}
\item All selectable options in the contest are set to zero, i.e. \EG generates encryptions of zero (unselected option) for all selectable options.
\item An indicator that an overvote has occurred and the list of selected options are added to the contest data field.
\end{enumerate}

An undervote occurs if the number of selections is less than the selection limit. A null vote occurs if no selection has been made. In both cases, an indicator for an undervote or a null vote is added to the contest data field, respectively.

\paragraph{Contest write-in data.}
For all write-in selections in a contest, \EG captures the text written into each write-in field. This text is collected in the contest data field for that contest, after any information about overvotes, undervotes or null votes.

\paragraph*{Padding to fixed length.}
The collected contest data is encoded as a byte array of length $32\cdot b_D$ bytes. If the encoded data is shorter, it is padded to the fixed length of $32\cdot b_D$ bytes with an array of \texttt{00} bytes of the appropriate length at the end. If it is longer it must be truncated to have exactly $32 \cdot b_D$ bytes.


---- S3.3.8
\subsubsection{Proof of satisfying the contest selection limit}\label{sec:selectionlimit}
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 $(\alpha_i,\beta_i)$ values for a contest by forming the aggregate contest encryption $(\bar\alpha,\bar\beta) = (\prod_i\alpha_i \bmod p,\ \prod_i\beta_i \bmod p)$ and proving that $(\bar\alpha,\bar\beta)$ is an encryption of a value that is not larger than the total number of votes allowed for that contest (usually one). The simplest way to complete this proof is to combine all of the pseudo-random nonces $\xi_i$ that were used to form each $(\alpha_i,\beta_i ) = (g^{\xi_i} \bmod p,\ K^{\xi_i+\sigma_i} \bmod p)$. The aggregate nonce $\xi = \sum_i \xi_i \bmod q$ matches the aggregate contest encryption as $(\bar\alpha,\bar\beta) = (\prod_i\alpha_i \bmod p, \prod_i\beta_i \bmod p) = (g^\xi \bmod p,\ K^{\xi+\ell} \bmod p)$ -- where $0 \leq \ell \leq L$ and $L$ is the selection limit for the contest.

\paragraph{NIZK Proof:} Proves that $(\bar\alpha,\bar\beta)$ is an encryption of an integer in the range $0,1,\dots,L$.\\(Requires knowledge of aggregate encryption nonce $\xi$ for which $(\bar\alpha,\bar\beta)$ is an encryption of $\ell$.)

This proof is a disjunctive Chaum-Pedersen range proof as described in detail in Section~\ref{sec:proofsballotcorrectness}. The range bound $L$ is equal to the contest selection limit and the ciphertext $(\alpha, \beta)$ from Section~\ref{sec:proofsballotcorrectness} is replaced by the aggregate contest encryption $(\bar\alpha,\bar\beta)$.

Commitments $(a_i, b_i)$ and challenge values $c_j$ fo $j\neq \ell$ are computed as shown in Section~\ref{sec:proofsballotcorrectness}. The challenge value then is computed as
\begin{equation}\label{eq:nizk_c_selection_limit}
  c = H(\HH_E;\mathtt{0x21},K,\bar\alpha,\bar\beta,a_0,b_0,a_1,b_1,\dots,a_L,b_L).
\end{equation}
The remaining challenge value $c_\ell$ can then be determined and the responses $v_i$ computed as shown in Section~\ref{sec:proofsballotcorrectness}. The proof consists of the challenge values $c_0, c_1, \dots, c_L$ and the response values $v_0, v_1, \dots, v_L$.
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 aggregate nonce $\xi$, i.e. the sum of the nonces $\xi_i$ used for the individual selection encryptions.

\EGverif{\veriftitleAdherenceToVoteLimits}{\label{verif:selectionlimit}
\veriftextAdherenceToVoteLimits}


---- S3.4
\subsection{Confirmation codes}\label{sec:confirmationcodes}
Upon completion of the encryption of each ballot, a \emph{confirmation code} is prepared for each voter. The code is a hash value (an output of the function $H$ as specified in detail in Section~\ref{sec:hashing}) whose inputs must include the encrypted ballot and the extended base hash code $\HH_E$. Inputs to the hash may optionally include other information such as an identifier for the voting device, the location of the voting device, as well as the date and time that the ballot was encrypted.

The data that constitutes the encrypted ballot for the purpose of computing its confirmation code consists of all encrypted selections on that ballot. I.e.\ it includes a ciphertext $(\alpha, \beta)$ for each selection in each contest on the ballot. In detail, a confirmation code for a given ballot $B$ is computed as follows. The number of contests on the ballot $B$ is denoted by $m_B$ and contests have a specified order defined in the election manifest file. Therefore, each contest has a unique sequence order $l$, where $1\leq l \leq m_B$.

---- S3.4.1
\subsubsection{Contest hash}\label{sec:contesthash}
For each contest, \EG computes a \emph{contest hash}, which is a hash value of an input that contains all selection option encryptions in the contest. The encryptions are hashed in order specified by the election manifest file.  
If $E_i = (\alpha_i, \beta_i)$ denotes the ciphertext encrypting the voter's choice for the $i$-th option ($1\leq i \leq m$) of the $l$-th contest ($1\leq l \leq m_B$), the contest hash value $\chi_l$ is computed from the contest label $\Lambda_l$, the election public key $K$, and the sequence of ciphertexts $E_1, E_2, \ldots, E_{m}$ as
\begin{equation}\label{eq:contesthash}
\chi_l = H(\HH_E; \mathtt{0x23}, \indc(\Lambda_l), K, \alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m).
\end{equation}

---- S3.4.2
\subsubsection{Confirmation code}\label{sec:confirmationcode}
The \emph{ballot confirmation code} is a \emph{ballot hash} $\HH(B)$ that is computed from all contest hashes as  
\begin{equation}\label{eq:confirmationcode}
\HH(B) = H(\HH_E; \mathtt{0x24}, \chi_1, \chi_2, \ldots, \chi_{m_B}, \B_{\mathrm{aux}}).
\end{equation}
The input contains the contest hashes in the order of the contests as specified in the election manifest file. Besides the contest hashes, there is an additional, auxiliary input byte array $\B_{\mathrm{aux}}$. Its composition is specified in the election manifest file depending on the desired properties for the confirmation codes. The byte array $\B_{\mathrm{aux}}$ can be used to include strings that encode the above mentioned optional information on the voting device such as a device identifier and its location, or the date and time that the ballot was encrypted. It can also contain the confirmation code of a previous ballot to enable ballot chaining as described below. If ballot chaining is not used, the manifest file may specify that this additional input is not used, in which case $\B_{\mathrm{aux}}$ can be omitted (or treated as the empty byte array).

---- S3.4.3
\subsubsection{Ballot chaining}\label{sec:ballotchaining}
For a fixed voting device, the additional input to the confirmation code $\HH_j = \HH(B_j)$ of the $j$-th ballot voted on this device can also include the confirmation code $\HH_{j-1} = \HH(B_{j-1})$ of the previous ballot $B_{j-1}$. When this is included, confirmation codes are part of a hash chain, which is initialized with 
\begin{equation}\label{eq:hashchain0}
  \HH_0 = H(\HH_E;\mathtt{0x24},\B_{\mathrm{aux},0}),
\end{equation}
where $B_{\mathrm{aux},0}$ must contain at least a unique voting device identifier and possibly other voting device information as described above and as specified in the election manifest file.\vspace{2pt}\\
The confirmation code for the $j$-th ballot when $j>0$ is then computed as above via
$\HH(B_j)=H(\HH_E; \mathtt{0x24}, \chi_1, \chi_2, \ldots, \chi_{m_B}, \B_{\mathrm{aux},j})$ and the additional byte array 
\begin{equation}
  \B_{\mathrm{aux},j} = \HH_{j-1}\parallel \B_{\mathrm{aux},0}
\end{equation}
now must contain the confirmation code $\HH_{j-1}$ of the previous ballot $B_{j-1}$ (or the initialization code $\HH_0$ when computing $\HH_1 = \HH(B_1)$) and the voting device information by including $\B_{\mathrm{aux},0}$.
If $\B_{\mathrm{aux},j}$ is allowed to contain more than one prior confirmation code, a tree of hash dependencies can be formed. The auxiliary byte array $\B_{\mathrm{aux},j}$ should be stored in the encrypted ballot.

The chain should be closed at the end of an election by forming and publishing 
\begin{equation}\label{eq:hashchainclose}
\overline{\HH} = H(\HH_E; \mathtt{0x24}, \overline\B_{\mathrm{aux}}),
\end{equation} 
using $\overline\B_{\mathrm{aux}} = \HH(B_\ell)\parallel \B_{\mathrm{aux},0} \parallel \bytes(\Str{CLOSE}, 5)$, where $\HH(\B_\ell)$ is the final confirmation code in the chain. The benefit of a chain is that it makes it more difficult for a malicious insider to selectively delete ballots and confirmation codes after an election without detection.

\EGverif{\veriftitleValidationOfTrackingCodes}{\label{verif:trackingcodes}
\veriftextValidationOfTrackingCodes}

\paragraph{Ballot casting or challenging.}
Once in possession of a confirmation code (\emph{and never before}), a voter is afforded an option to either cast the associated ballot or challenge 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 confirmation 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 challenged.  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.

---- S3.5
\subsection{Ballot Aggregation}\label{sec:ballotaggregation}
At the conclusion of voting, all of the ballot encryptions are published in the election record together with the proofs that the ballots are well-formed. Additionally, all of the encryptions of each option are homomorphically combined to form an encryption of the sum of the values that were individually encrypted. The encryptions $(\alpha_i, \beta_i)$ of each individual option are combined by forming the product 
\begin{equation}
  (A,B)=\left(\prod_i\alpha_i \bmod p,\ \prod_i\beta_i \bmod p\right).
\end{equation}
This aggregate encryption $(A,B)$, which represents an encryption of the tally of that option, is published in the election record for each option.

\EGverif{\veriftitleCorrectnessOfBallotAggregation}{\label{verif:aggregation}
\veriftextCorrectnessOfBallotAggregation}


---- S3.6
\subsection{Verifiable Decryption}\label{sec:verifiable_decrypt}
To decrypt an aggregate encryption $(A,B)$ (or an individual encryption such as one on a challenged ballot), guardians work together in a protocol, where each guardian produces a partial decryption and contributes to an accumulated Chaum-Pederson proof of correct decryption.
 
As long as at least $k$ guardians are present for decryption, the partial decryptions produced by the guardians are used to compute the value
\begin{equation}
M = A^s \bmod p,
\end{equation}
without ever computing the secret key $s$. This value is then used to obtain
\begin{equation}
T = B\cdot M^{-1} \bmod p.
\end{equation}
This $T$ has the property that $T=K^t \bmod p$ where $t$ is the tally of the associated option.

In general, computation of this tally value $t$ is computationally intractable. However, in this application, $t$ is relatively small---usually bounded by the number of votes cast. This tally value $t$ can be determined from $T$ by exhaustive search, by precomputing a table of all possible $T$ values in the allowable range and then performing a single look-up, or by a combination in which some exponentiations are precomputed and a small search is used to find the value of $t$ (e.g., a partial table consisting of $K^{100} \bmod p$, $K^{200} \bmod p$, $K^{300} \bmod p$, \dots is precomputed and the value $T$ is repeatedly divided (or multiplied) by $K$ until a value is found that is in the partial table). The value $t$ is published in the election record, and verifiers should check both that $T = K^t \bmod p$ and that $B = T\cdot M \bmod p$.

---- S3.6.1
\subsubsection{Partial decryption by available guardians}\label{sec:decrypt_missing}

During the key generation process (as described in Section~\ref{sec:keygendetails}), each guardian $G_i$ receives from each other guardian $G_j$ a share $P_j(i)$ of $G_j$'s secret key $s_j$ ($1\leq i,j \leq n$ and $i \neq j$). Guardian $G_i$ also computes its own share $P_i(i)$ and is therefore in possession of all shares $P_j(i)$ for $1 \leq j \leq n$. Either at that time or at a later time but before $G_i$ participates in any joint decryption process, $G_i$ computes 
\begin{equation}
P(i) = \left(\sum_{j = 1}^n P_j(i)\right) \bmod q = \left(P_1(i) + P_2(i) + \dots + P_n(i)\right) \bmod q.
\end{equation}
The value $P(i)$ is $G_i$'s share of the implicit secret key $s = (s_1 + s_2 + \dots + s_n) \bmod q$.\footnote{Guardian $G_i$'s secret key $s_i$ is the constant coefficient of the polynomial $P_i(x)$ and therefore the implicit secret key $s = (s_1 + s_2 + \dots + s_n) \bmod q$ is the constant coefficient of the polynomial $P(x) = (P_1(x) + P_2(x) + \dots + P_n(x)) \bmod q$. The collection of the $P(i)$ are the shares for a $k$-out-of-$n$ sharing of the secret key $s$. It is important to note that this secret key $s$ is never actually computed; instead each guardian uses its share of the implicit secret key $s$ to form a share of any decryption that needs to be performed.}

Each guardian $G_i$ available for decryption uses the share $P(i)$ to compute the partial decryption
\begin{equation}
M_{i} = A^{P(i)} \bmod p
\end{equation}
that contributes to computing the value $M = A^s \bmod p$.

---- S3.6.2
\subsubsection{Combination of partial decryptions.}
The partial decryptions are combined to obtain $M$ with the help of the Lagrange coefficients that correspond to the available guardians. Let $U \subseteq \{1,2,\dots,n\}$ be the set of indices such that $\{G_i : i\in U\}$ is the set of available guardians. For decryption to succeed, a quorum of at least $k$ guardians is needed, i.e. $|U| = h \geq k$. All available guardians participate in the reconstruction even if $h>k$, i.e., there are more guardians available than strictly necessary for having a quorum. 

The Lagrange coefficients corresponding to $U$ are computed as
\begin{equation}
w_i = \left(\prod_{\ell\in(U\setminus\{i\})} \frac{\ell}{\ell-i}\right) \bmod q.
\end{equation}
These coefficients are used to combine the $M_i$ for $i\in U$ provided by the available guardians to obtain
\begin{equation}\label{eqn:threshold_decrypt}
    M = \prod_{i\in U}(M_{i})^{w_i} \bmod p.
\end{equation}

\EGnote{The decryption $M = A^s \bmod p$ can be computed as shown in Equation~\eqref{eqn:threshold_decrypt} because $s = (\sum_{i\in U} w_i P(i)) \bmod q$. Likewise, a missing secret $s_j$ could be computed directly as $s_j = (\sum_{i\in U} w_i P_j(i)) \bmod q$.
However, it is preferable to not release the secret $s$ (or any of the missing secrets) and instead only release the partial decryptions that the secret would have produced. This prevents the secret from being used for additional decryptions without the cooperation of at least $k$ guardians.\vspace{2pt}\\
As an example, consider an election with five guardians and a threshold of three. If two guardians are missing at the time of decryption, the remaining three can perform any required decryptions as described in the text above. If, instead, they take the shortcut of simply reconstructing and then using the two missing secrets, then any of the three could, at a later time, use these missing secrets together with its own secret to perform additional decryptions without the cooperation of any other guardian.}

---- S3.6.3
\subsubsection{Proof of correctness}\label{sec:verifiable_decrypt_proof}
The available guardians work together to produce a Chaum-Pedersen proof that $M$ was computed correctly, which means that $M= A^s \bmod p$. The proof is computed as follows.

\paragraph{NIZK Proof:} The available guardians jointly prove that they have shared knowledge of $s\in \Z_q$ such that $M = A^{s} \bmod p$ and $K = g^{s} \bmod p$.

\noindent Each available guardian $G_i$, $i \in U$, selects a random value $u_i$ in $\Z_q$ and commits to the pair 
\begin{equation}
(a_i,b_i) = (g^{u_i} \bmod p,\ A^{u_i} \bmod p).
\end{equation}
The $a_i$ and $b_i$ obtained from each guardian are used to compute the accumulated commitments as
\begin{equation}
a = \left(\prod_{i\in U} a_i\right) \bmod p,\ b = \left(\prod_{i\in U} b_i\right) \bmod p.
\end{equation}
This means $a = g^u \bmod p$ and $b = A^u \bmod p$, where $u = (\sum_{i \in U} u_i) \bmod q$ and $u$ is not computed explicitly.

The ciphertext $(A,B)$, the commitments $(a,b)$, and the combined value $M$ are then hashed together with the extended base hash value $\HH_E$ to form a challenge
\begin{equation}\label{eq:nizk_c_dec}
c = H(\HH_E;\mathtt{0x30},K,A,B,a,b,M). 
\end{equation}
The challenge $c$ is adjusted by the $i$-th Lagrange coefficient to produce a challenge $c_i$ for available guardian $G_i$ ($i\in U$) as 
\begin{equation}
c_i = (c\cdot w_i) \bmod q.
\end{equation}
Next, each available guardian $G_i$ responds to the challenge $c_i$ with
\begin{equation}
v_i = (u_i-c_i P(i)) \bmod q.
\end{equation}
All individual responses $v_i$ are verified by recomputing the commitments from the responses, the individual challenge values $c_i$, the guardians' commitments $K_{j,m}$ to the coefficients $a_{j,m}$ of their secret sharing polynomials $P_j$ (see \ref{sec:keygendetails}), the ciphertext value $A$ and the partial decryptions $M_i$ as 
\begin{align}
  a_i' & = g^{v_i} \left(\prod_{j=1}^n\prod_{m=0}^{k-1}K_{j,m}^{i^m}\right)^{c_i} \bmod p,\\
  b_i' & = A^{v_i} M_i^{c_i} \bmod p
\end{align}
and checking that $a_i' = a_i$ and $b_i' = b_i$. If these equations are all satisfied, an accumulated response
\begin{equation}
v = \left(\sum_{i \in U} v_i\right) \bmod q
\end{equation}
is computed and the decrypted value $T = B\cdot M^{-1} \bmod p$ is published along with the proof $(c,v)$ in the election record. Note that $v = (u - c\cdot s) \bmod q$.

\EGverif{\veriftitleCorrectnessOfDecryptions}{\label{verif:decryption}
\veriftextCorrectnessOfDecryptions}

\paragraph{Tally verification.}
The final step is to verify the tallies themselves.

\EGverif{\veriftitleValidationOfCorrectDecryptionOfTallies}{\label{verif:tallies}
\veriftextValidationOfCorrectDecryptionOfTallies}

---- S3.6.4
\subsubsection{Decryption of contest data}\label{sec:decrypt_contest_data}
For each contest, an encrypted ballot contains a ciphertext $C_E = (C_0, C_1, C_2)$ encrypting contest data such as overvote, undervote, and null vote information and write-in text fields. The ciphertext has been generated as described in Section \ref{sec:encrypt_ext_data}. Such data may need to be decrypted if the tallies record a significant number of votes in write-in selections. Also, all contest data fields on each challenged ballot are decrypted.

Decryption can be done by a quorum of guardians similarly to the decryption of tallies explained above. Each available guardian $G_i$, $i \in U$, computes a partial decryption
\begin{equation}
  m_i = C_0^{P(i)} \bmod p
\end{equation}
using its precomputed share $P(i) = \sum_{j=1}^n P_j(i) \bmod q$. The partial decryptions are combined using the Lagrange coefficients for the set $U$ of available guardians to obtain
\begin{equation}
\beta = \left(\prod_{i\in U} m_i^{w_i}\right) \bmod p
\end{equation}
Again, the available guardians work together to produce and publish the following proof.

\paragraph{NIZK Proof:} The available guardians jointly prove that they have shared knowledge of $s\in \Z_q$ such that $\beta = C_0^{s} \bmod p$ and $K = g^{s} \bmod p$.

\noindent This proof is exactly the same as the one in Section~\ref{sec:verifiable_decrypt_proof}, where the ciphertext $(A,B)$ is replaced by the contest data ciphertext $(C_0, C_1, C_2)$ as follows.
Guardian $G_i$ selects a random value $u_i$ in $\Z_q$ and commits to the pair 
\begin{equation}
(a_i,b_i) = (g^{u_i} \bmod p,\ C_0^{u_i} \bmod p).
\end{equation}
The values $a_i$ and $b_i$ are accumulated into 
\begin{equation}
  a = \left(\prod_{i\in U} a_i\right) \bmod p,\ b = \left(\prod_{i\in U} b_i\right) \bmod p
  \end{equation}
and the joint challenge value $c$ is obtained as
\begin{equation}\label{eq:nizk_c_dec_cont}
c = H(\HH_E;\mathtt{0x31},K,C_0,C_1,C_2,a,b,\beta). 
\end{equation}
Each available guardian $G_i$ responds to its challenge $c_i = (c\cdot w_i) \bmod q$ with 
\begin{equation}
v_i = (u_i-c_i P(i)) \bmod q.
\end{equation}
As above, all proof parts $v_i$ are verified by recomputing commitments
\begin{align}
  a_i' & = g^{v_i} \left(\prod_{j=1}^n\prod_{m=0}^{k-1}K_{j,m}^{i^m}\right)^{c_i} \bmod p,\\
  b_i' & = C_0^{v_i} m_i^{c_i} \bmod p.
\end{align}
If $a_i' = a_i$ and $b_i' = b_i$, an accumulated response  
\begin{equation}
v = \left(\sum_{i \in U} v_i\right) \bmod q
\end{equation}
is computed and the decryption value $\beta$ is published along with the proof $(c,v)$.

Then decryption proceeds by computing the key $k = H(\HH_E; \mathtt{0x22}, K, C_0, \beta)$ and the MAC key 
\begin{equation}
  k_0 = \HMAC(k,\bytes(0,4)\parallel\mathtt{Label}\parallel\mathtt{0x00}\parallel\mathtt{Context}\parallel \bytes((b_D+1)\cdot 256,4)) 
\end{equation}
with $\mathtt{Label} = \bytes(\mathtt{``data\_enc\_keys"}, 13)$ and $\mathtt{Context} = \bytes(\mathtt{``contest\_data"}, 12)\parallel \bytes(\indc(\Lambda), 4)$.
When it is the case that $C_2 = \HMAC(k_0, C_0\parallel C_1)$, the encryption keys $k_1, k_2, \dots, k_{b_D}$ are computed as
\begin{equation}
  k_i = \HMAC(k,\bytes(i,4)\parallel\mathtt{Label}\parallel\mathtt{0x00}\parallel\mathtt{Context}\parallel \bytes((b_D+1)\cdot 256,4))
\end{equation}
and the byte array $D$ representing the contest data string is decrypted by parsing $C_1$ in 32-byte blocks as
\begin{equation}
C_1 = C_{1,1} \parallel C_{1,2} \parallel \dots \parallel C_{1,b_D}
\end{equation}
and obtaining
\begin{equation} 
  D = C_{1,1}\oplus k_1 \parallel C_{1,2}\oplus k_2 \parallel \dots \parallel C_{1,b_D}\oplus k_{b_D}.
\end{equation}
The byte array $D$ can now be parsed to reveal the captured overvote, undervote, and null vote data and write-in text fields.


\EGverif{\veriftitleCorrectnessOfDecryptionsOfContestData}{\label{verif:extdecryption}
\veriftextCorrectnessOfDecryptionsOfContestData}


---- S3.6.5
\subsubsection{Decryption of challenged ballots}\label{sec:decrypt_challenged}
Each and every challenged ballot must be verifiably decrypted.  \EG supports two methods of decrypting challenged ballots.  The first is for the guardians to use their secret keys in precisely the way they do to decrypt election tallies.  The second is to simply publish the primary nonce used to encrypt each challenged ballot.  Whether these nonces are available depends on how \EG is used.

\paragraph{Standard decryption with guardian keys.}
Every ballot challenged in an election is individually verifiably decrypted in exactly the same way that the aggregate ballot of tallies is decrypted. Each individual selection encryption $(\alpha, \beta)$ in each contest on the challenged ballot is jointly decrypted by the available guardians as shown at the beginning of Section~\ref{sec:verifiable_decrypt} with $(A,B)$ replaced by $(\alpha, \beta)$. This includes the generation of the appropriate NIZK proofs to prove correctness of these decryptions $M$. The corresponding encrypted selection is then decrypted by combining the partial decryptions as shown above for tallies by computing
\begin{equation}
S = \beta\cdot M^{-1}\bmod p.
\end{equation}
This $S$ encrypts a vote $\sigma$ as $S = K^\sigma \bmod p$ from which $\sigma$ can be determined as described at the beginning of Section~\ref{sec:verifiable_decrypt}.\footnote{When, as is usually the case, $\sigma$ is known to be in the set $\{0,1\}$, the decryption can be completed simply by checking whether $S = 1$ or $S = K$.}

In addition, all contest data fields on a challenged ballot are decrypted as shown in the previous Subsection~\ref{sec:decrypt_contest_data}. 

An election verifier must confirm the correct decryption of each challenged ballot using the same process that was used to confirm the election tallies. In particular, this means that Verification~\ref{verif:decryption} must be confirmed.
In order to assign unique verification steps for challenged ballots, the relevant verification steps for tallies are adjusted and listed here again.

In addition to all selection and contest data decryptions, election verifiers should confirm that a ballot is well-formed. Overall, casual observers should be able to simply view the decryptions and confirm that they match their expectations.

\EGverifBallot{\veriftitleCorrectnessOfDecryptionsChallenged}{\label{verif:challengedDecrypt}
\veriftextCorrectnessOfDecryptionsChallenged}

\EGverifBallot{\veriftitleValidationOfCorrectDecryptionOfChallengedBallots}{\label{verif:challengedballots}
\veriftextValidationOfCorrectDecryptionOfChallengedBallots}

Finally, the following verification steps are carried out for each challenged ballot to confirm the correct decryption of contest data. 

\EGverifBallot{\veriftitleCorrectnessOfDecryptionsOfContestDataChallenged}{\label{verif:challengedDecryptContest}
\veriftextCorrectnessOfDecryptionsOfContestDataChallenged}

\paragraph{Verifying decryption with nonces.}
When the primary nonce $\xi_B$ that was used to encrypt a ballot $B$ is available, a verifiable decryption can be produced by simply publishing this nonce.  This can drastically reduce the amount of computation required of both guardians and verifiers.

There are several scenarios in which this nonce may be available.  For instance, if a ballot is challenged immediately after encryption, the device that performed the encryption may be able to provide the nonce as soon as the challenge is issued.  Alternatively, the device that encrypted the ballot might encrypt the ballot's primary nonce with the election key or with another key and provide this with the encrypted ballot.

Publishing a ballot's primary nonce in an election record enables a decryption to be confirmed by simply repeating the encryption and checking for a match.  The same steps could also be taken by a voter equipped with a suitable application immediately upon receiving this nonce to verify a challenge ballot without having to wait for the election record to be published.\footnote{It is likely that a voter would only have access to a ballot's confirmation code --- not its full encryption --- if a verification is to be performed prior to the publication of the election record.  Thus, the voter's application would need to regenerate the encrypted ballot from the primary nonce and the voter's selections and then recompute the confirmation code in order to verify its accuracy.}

Specifically, with possession of a primary ballot nonce $\xi_B$ and the selections made on the ballot, a verification application can repeat the vote encryption process as described in \S\ref{sec:ballotencryption} as follows.
\begin{itemize} 
  \item It derives the selection encryption nonce for each contest and each selection in the  contest. The nonce for the $i$-th contest, which has label $\Lambda_i$, and the $j$-th selection in the contest, which has label $\lambda_j$ is $\xi_{i,j}$ and is derived by a hash computation as shown in Equation~\eqref{eq:noncegen} in Section~\ref{sec:noncegen}. 
  \item Using the encryption nonces $\xi_{i,j}$, it recomputes the selection encryptions as shown in Equation~\eqref{eqn:encryptvote} of Section~\ref{sec:selectionencryption}.
  \item Finally, it recomputes the confirmation code $\HH(B)$ as described in Section~\ref{sec:confirmationcodes} via its contest hashes. 
\end{itemize}
If the resulting confirmation code matches the confirmation code provided to the voter, then this is verification that the confirmation code corresponds to a ballot with votes for the indicated selections.

Note that confirmation codes {\em do not} include any of the zero-knowledge proofs of ballot correctness.  So a verifier does not need to reproduce these zero-knowledge proofs.  Only the actual encryptions of the selections must be regenerated and confirmed.

---- S3.7
\subsection{The Election Record}
The record of an election should be a full accounting of all of the election artifacts.  Specifically, it should contain the following.
\begin{itemize}
	\item Information sufficient to uniquely identify and describe the election, such as date, location, election type, etc. (not otherwise included in the election manifest).
	\item The election manifest file.
	\item The baseline parameters:
  \begin{itemize}
    \item primes $p$ and $q$ and integer $r$ such that $p=qr+1$ and $r$ is not a multiple of $q$,
    \item a generator $g$ of the order $q$ multiplicative subgroup $\Z_p^*$,
    \item the number $n$ of election guardians,
    \item the quorum threshold $k$ of guardians required to complete verification.
  \end{itemize}
  \item The parameter base hash $\HH_P$ computed from the parameters.
	\item The base hash value $\HH_B$ computed from the above.
	\item The commitments from each election guardian to each of their polynomial coefficients.
	\item The proofs from each guardian of possession of each of the associated coefficients.
	\item The election public key.
	\item The extended base hash value $\HH_E$ computed from the above.
	\item Every encrypted ballot prepared in the election (whether cast or challenged):
	\begin{itemize}
    \item All of the encrypted selections on each ballot,
    \item the proofs that each such value is an encryption of either zero or one,
    \item the selection limit for each contest,
    \item the proof that the number of selections made matches the selection limit,
    \item the ballot style,
    \item the device information for the device that encrypted the ballot,
    \item the date and time of the ballot encryption,
    \item the confirmation code produced for the ballot.
  \end{itemize}
  \item The decryption of each challenged ballot:
  \begin{itemize}
    \item The selections made on the ballot,
    \item the plaintext representation of the selections,
    \item proofs of each decryption.
  \end{itemize}
	\item Tallies of each option in an election:
  \begin{itemize}
    \item The encrypted tally of each option,
    \item full decryptions of each encrypted tally,
    \item plaintext representations of each tally,
    \item proofs of correct decryption of each tally.
  \end{itemize}
	\item Ordered lists of the ballots encrypted by each device.
\end{itemize}
An election record should be digitally signed by election administrators together with the date of the signature. The entire election record and its digital signature should be published and made available for full download by any interested individuals. Tools should also be provided for easy look up of confirmation codes by voters.

The exact organizational structure of the election record will be specified in a separate document.




\pagebreak

-------- Section 4

\section{Pre-Encrypted Ballots}\label{sec:pre-encrypted}

In typical use, \EG ballots are encrypted after the voter selections are known.  However, there are several common scenarios in which it is desirable to perform the encryption before the selections of a voter are known.  These include Vote-by-Mail, pre-printed ballots for use in precincts with central count or minimal in-precinct equipment, and back-ups for precincts which ordinarily perform encryption on demand.

With pre-encrypted ballots, each possible selection on a ballot is individually encrypted in advance; and the selections made by the voter indicate which encryptions are used.

\EG requires two applications to support pre-encrypted ballots: a \emph{ballot encrypting tool} to provide data to enable printing of blank ballots and a companion \emph{ballot recording tool} to receive information about selections made on pre-printed ballots and produce data compatible with the \EG election record.

---- S4.1
\subsection{Format of Pre-Encrypted Ballots}
Each selectable option within each contest is associated with a vector $\Psi$ of encryptions $E_j$ --- with one encryption for each selectable option within the contest. Selectable options in a contest have a unique order determined by their option indices in increasing order. Let $i$ be the position of the  selectable option in this ordering (not necessarily identical to its option index).
In its \emph{normal} form and for a contest with $m$ selection options, this vector 
\begin{equation}\label{eq:encvector}
\Psi_{i,m}=\langle E_1,E_2,\ldots,E_m\rangle
\end{equation}
includes an encryption $E_i=(\alpha_i,\beta_i) = \Enc(1; \xi_i)$ of one in the vector position $i$ associated with the selection made and encryptions $E_j=(\alpha_j,\beta_j) = \Enc(0, \xi_j)$ of zero in every other position $1\leq j \leq m$, $j\neq i$, where the $\xi_j$ are (pseudo-)random encryption nonces. For example, the vector $\Psi_{2,4}$ associated with selecting the second option in a contest with a total of $m=4$ selection options is $\Psi_{2,4} = \langle \Enc(0; \xi_1), \Enc(1; \xi_2), \Enc(0; \xi_3), \Enc(0; \xi_4)\rangle$. This corresponds precisely to the standard \EG encryption of a vote for the same option. There is also a \emph{null} form $\Psi_{0,m} = \langle \Enc(0; \xi_1), \Enc(0; \xi_2), \dots, \Enc(0; \xi_m)\rangle$ which is the same form except that all values are encryptions of zero.

The principal difference between a pre-encrypted ballot and a standard \EG ballot is that while standard \EG has a single vector of encryptions for each contest, here we have a vector of encryptions for each selectable option in each contest (generally including the possibility of an undervote in which no selections are made). Another difference is that while a standard \EG contest encryption can contain multiple selections, each vector of pre-encryptions represents at most one selection.  However, in a contest where a voter is allowed to make multiple selections, multiple pre-encryption vectors can be combined to form a single contest encryption vector with multiple encryptions of one that precisely matches the standard \EG format.

---- S4.1.1
\subsubsection{Selection hash}\label{sec:selectionhash_pre}
Each pre-encrypted vector of a pre-encrypted ballot is hashed using the \EG hash function $H$ (specified in detail in Section~\ref{sec:hashing}) to form a \emph{selection hash}. For all selectable options, i.e. for each option at position $i$ in the contest with $1\leq i \leq m$, the hash value $\psi_i$ of the selection vector $\Psi_{i,m} = \langle E_1,E_2,\ldots,E_m\rangle$ is computed as 
\begin{equation}\label{eq:selectionhash_pre}
\psi_i = H(\HH_E; \mathtt{0x40}, K, \alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m),
\end{equation}
where $E_i = (\alpha_i, \beta_i)$ is an encryption of one and $E_j = (\alpha_j, \beta_j)$ is an encryption of zero for $j \neq i$.

In a contest with a selection limit of $L$, an additional $L$ null vectors are hashed to obtain
\begin{equation}\label{eq:nullhash_pre}
\psi_{m+\ell}=H(\HH_E; \mathtt{0x40}, K, \alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m),
\end{equation}
where all $E_i = (\alpha_i, \beta_i)$ are encyptions of zero and $1\leq \ell \leq L$.

---- S4.1.2
\subsubsection{Contest hash}\label{sec:contesthash_pre}
% Copyright (C) Microsoft Corporation. All rights reserved.
All of the selection hashes within each contest will ultimately be hashed {\em in sorted order} to form the \emph{contest hash} of that contest. Each contest on a ballot has a unique position determined by the position of its contest index in the list of contest indices in increasing order. The contest hash for the $l$-th contest (with label $\Lambda_l$) on the ballot is computed as 
\begin{equation}\label{eq:contesthash_pre}
\chi_l = H(\HH_E; \mathtt{0x41}, \indc(\Lambda_l), K,\psi_{\sigma(1)},\psi_{\sigma(2)},\ldots,\psi_{\sigma(m+L)}),
\end{equation}
where $\sigma$ is a permutation that represents the sorting of the selection hashes. This means that contests are \emph{not} hashed in the order given by the contest indices, but instead $\sigma(i)<\sigma(j)$ implies that $\psi_{\sigma(i)}<\psi_{\sigma(j)}$ (when hash values are interpreted as integers in big endian byte order). 
The sorting is required so that the order of the selection hashes $\psi_1,\psi_2,\ldots,\psi_m$ does not reveal the contents of the encryptions that are used to generate the hashes.

---- S4.1.3
\subsubsection{Confirmation code}\label{sec:confirmationcode_pre}
While contest hashes for pre-encrypted ballots are computed from selection hashes, which differs from the standard scenario for \EG described in Section~\ref{sec:confirmationcodes}, the computation of confirmation codes aligns with the previous case. The \emph{confirmation code} $\HH(B)$ of a pre-encrypted ballot $B$ is generated as the hash of all the contest hashes on the ballot in sequential order. If there are $m_B$ contests on the ballot (in sequential order specified by their contest indices in the election manifest file), its confirmation code is computed as 
\begin{equation}\label{eq:ballothash_pre}
\HH(B)=H(\HH_E; \mathtt{0x42}, \chi_1,\chi_2,\ldots, \chi_{m_B}, \B_{\mathrm{aux}}).
\end{equation}
Use of the auxiliary input byte array $\B_{\mathrm{aux}}$ is the same as described in Sections~\ref{sec:confirmationcode} and \ref{sec:ballotchaining} to enable the input of specific information of the device generating pre-encrypted ballots.

A ballot's hash will be printed directly on the ballot.
Ideally, two copies of the ballot hash will be included on each ballot with one remaining permanently with the ballot and the other in an immediately adjacent location on a removable tab. These removable ballot codes are intended to be retained by voters and can be used as an identifier to allow voters to look up their (encrypted) ballots in the election record and confirm that they include the proper \emph{short codes} as described below.


---- S4.1.4
\subsubsection{Short Codes}\label{sec:shortcodes_pre}
In any instantiation of pre-encrypted ballots, an additional \emph{hash trimming function} $\Omega$ must be provided.  The hash trimming function takes as its input a selection hash, and its output is a \emph{short code}.  As an example, $\Omega$ could produce the last byte of its input in a specified form. 
 For instance, a short code representation could be a pair of hex characters, a pair of letters from a 16-letter alphabet, a letter followed by a digit, or a three-digit number.  The size of a short code does not need to be a single byte, but this is a convenient choice.  Different vendors or jurisdictions might choose to distinguish themselves by using their own preferred short code formats, so the details of the short code format are intentionally left open.  However, $\Omega$ must be completely specified in the election manifest so that a verifier can match its functionality.

The hash trimming function $\Omega$ associates each selection on a ballot with a short code.  \emph{The short codes on a ballot need not be unique.}  However, it is required that the short codes within a contest be unique.  If there is a collision of short codes within a contest, the randomness should be changed to generate a new ballot.  When a pre-encrypted ballot is presented to a voter, the short codes associated with each selection should be displayed beside the selection.  If the ballot is cast by a voter, the short codes associated with selections made by the voter will be published as part of the election record.

\paragraph{Undervotes.}
In addition to the short codes for each possible selection, short codes are provided to indicate undervotes.  (It may not be necessary to print undervote short codes on ballots.)  A short code for a null vote is generated from a vector of encryptions of zero.  In a contest in which the voter may select only one option there will be a single pre-encrypted null vote and associated short code to indicate that the voter did not make a selection in that contest.  In general, the number of null votes and short codes for a contest should match the selection limit of the contest.  So, for example, a contest in which a voter may make three selections should have three null short codes.  Since the short codes corresponding to the selections made by each voter will be published in the election record, the use of null short codes allows the election record to not reveal undervotes.

---- S4.2
\subsection{The Ballot Encrypting Tool}
The encrypting tool for pre-encrypted ballots takes as input parameters
\begin{itemize}
    \item the election manifest,
    \item a ballot style index,
    \item and an optional nonce encryption key (this may be the election encryption key).
\end{itemize}
The tool produces the following outputs -- which can be used to construct a single pre-encrypted ballot.  (Note that it will likely be desirable to construct a wrapper that can be called to produce data for a specified number of pre-encrypted ballots.)
\begin{itemize}
    \item An (optional) encryption of the primary nonce used to encrypt the ballot,
    \item a selection hash value for each possible selection in the ballot style,
    \item for each contest, additional null hash values corresponding in number to the contest selection limit,
    \item a contest hash for each contest computed from the sorted list of selection hashes and null hashes for that contest,
    \item and a confirmation code consisting of a hash of all of the contest hashes on the ballot.
\end{itemize}

The encrypting tool operates as follows.

First, it generates a 256-bit primary nonce $\xi$ for the ballot and, if a nonce encryption key is provided, encrypts this primary nonce with the nonce encryption key provided.

Next, for each contest on the indicated ballot style, an encryption vector is produced for each selection within the contest (see Equation~\eqref{eq:encvector}).  This encryption vector is deterministically derived from the primary nonce $\xi$ and consists of an encryption of one in the position corresponding to the selection and an encryption of zero in all other positions in the contest (see Equation~\eqref{eq:selectionhash_pre}).  Additionally, one or more null vectors consisting entirely of encryptions of zeros are produced (again deterministically from the primary nonce) as in Equation~\eqref{eq:nullhash_pre}.  The number of null vectors should match the selection limit $L$ of the contest.  The selection hashes and null hashes (computed as described in Section~\ref{sec:selectionhash_pre}) are then sorted numerically and hashed together (in sorted order) to produce the contest hash as shown in Equation~\eqref{eq:contesthash_pre} in Section~\ref{sec:contesthash_pre}.

Finally, the contest hashes are themselves hashed sequentially to form the ballot’s confirmation code according to Equation~\eqref{eq:ballothash_pre} in Section~\ref{sec:confirmationcode_pre}.

---- S4.2.1
\subsubsection{Deterministic nonce derivation}\label{sec:noncegen_pre}
The process of deterministic encryption is guided by a primary nonce $\xi$.  It is assumed that each contest has a label $\Lambda$ and that within each contest each possible selection has a label $\lambda$.  The nonce used within the $i^\text{th}$ contest and within that the $j^\text{th}$ selection vector to form the $k^\text{th}$ encryption is 
\begin{equation}\label{eq:noncegen_pre}
  \xi_{i,j,k}=H(\HH_E; \mathtt{0x43},\xi,\indc(\Lambda_i),\indo(\lambda_j),\indo(\lambda_k)).
\end{equation}
Note that the nonce $\xi_{i,j,k}$ will be used to encrypt a one whenever $j=k$ and a zero whenever $j \neq k$.  Note also that some of the selection labels will represent null votes.  If labels for null votes are not included within the manifest file, the labels ``null1'', ``null2'', ... should be used within each contest as needed.

The output of the encryption tool includes the (optionally encrypted) primary nonce, the selection hash corresponding to each selection on the ballot (including nulls), the contest hashes, and the confirmation code.


---- S4.2.2
\subsubsection{Using the Ballot Encrypting Tool}
It is the responsibility of the entity that calls the encryption tool to produce short codes from selection hashes.  This must be done in a deterministic, repeatable fashion using a hash trimming function $\Omega$.  As suggested above, one option is to use a human-friendly representation of the final byte (or bytes) of each selection hash.  Another would be to use an ordinal integer to indicate where in the sorted order of selection hashes within each contest each selection falls.  (For example, if a contest has four possible selections, the integers 1, 2, 3, 4, 5 could be placed beside each selection – including “none” to indicate the sorted position of each of the five selection hashes.)  This flexibility allows vendors to distinguish themselves with different ballot presentations and for vendors and jurisdictions to choose presentations that best accommodate their voters.

Unless the short codes in a particular instantiation are quite long, it is likely that there will be occasional collisions of short codes within a contest.  It is the responsibility of the entity that calls the ballot encryption tool to ensure that no ballot is printed with a short code that is repeated within a contest.  If a collision is found, the caller simply discards this ballot data and calls the ballot encryption tool again.  The caller may also choose to discard ballot data if a short code is repeated anywhere within a ballot or if two short codes -- within a contest or across a ballot – meet some definition of similarity.  The caller is free to discard data and obtain a new ballot pre-encryption as often as it likes.  (Note that a malicious encryption wrapper could bias the printed ballots by, for instance, only using encryptions in which a particular selection’s hash is always numerically first within a contest.  However, a malicious wrapper already knows the associations between the selection hashes, the short codes, and the actual selections, so it is not clear how a malicious wrapper could benefit from creating a bias.)

---- S4.3
\subsection{The Ballot Recording Tool}
The ballot recording tool receives an election manifest, an identifier for a ballot style, the decrypted primary nonce $\xi$ and, for a cast ballot, all the selections made by the voter.  The recording tool uses the primary nonce $\xi$ to regenerate all of the encryptions on the ballot.  For a cast ballot, the tool then isolates the pre-encryptions corresponding to the selections made by the voter and, using the encryption nonces derived from the primary nonce, generates proofs of ballot-correctness as in standard \EG section~\ref{sec:proofsballotcorrectness}.

Note that if a contest selection limit is greater than one, the recording tool homomorphically combines the selected pre-encryption vectors corresponding to the selections made to produce a single vector of encrypted selections.  The selected pre-encryption vectors are combined by componentwise multiplication (modulo $p$), and the derived encryption nonces are added (modulo $q$) to create suitable nonces for this combined pre-encryption vector.  These derived nonces will be necessary to form zero-knowledge proofs that the associated encryption vectors are well-formed.

For each uncast (implicitly or explicitly challenged) ballot, the recording tool returns the primary nonce that enables the encryptions to be opened and checked.

---- S4.3.1
\subsubsection{Using the Recording Tool}
A wrapper for the recording tool takes one or more encrypted nonces and obtains the decryption(s) by interacting with guardians, an administrator, or a local database and then calls the recording tool with each decrypted nonce and ballot style – and for a cast ballot, the voter selections.

If the ballot is a cast ballot, the wrapper then uses the hash trimming function $\Omega$ to compute the short codes for the selections made by the voter and posts in the election record the full set of selection hashes generated from \emph{all} pre-encryption vectors (whether or not selected by the voter), the full pre-encryption vectors corresponding to the voter selections, the proofs that these selected pre-encryption vectors are well-formed, and the short codes for the selections made by the voter.

For an uncast ballot, the wrapper computes the short codes for all possible selections and posts in the election record the full set of pre-encryption vectors, selection hashes, and short codes for each possible selection.

---- S4.4
\subsection{The Election Record}
Selection vectors generated from pre-encrypted ballots are indistinguishable from those produced by standard \EG.  However, the election record for each pre-encrypted ballot includes a significant amount of additional information.  Specifically, for each cast ballot, the election record should contain
\begin{itemize}
    \item the standard \EG encrypted ballot data consisting of selection vectors for each contest together with all the standard associated zero-knowledge proofs that the ballot is well-formed,
    \item the selection hashes for every option on the ballot (including null options) – sorted numerically within each contest, and
    \item the short codes and pre-encryption selection vectors associated with all selectable options (including null options) on the ballot made by the voter.
\end{itemize}
Note that in a contest with a selection limit of one, the selection vector will be identical to one of the pre-encryption selection vectors.  However, when a contest has a selection limit greater than one, the resulting selection vector will be a product of multiple pre-encryption selection vectors.

For each uncast ballot, the primary nonce for that ballot is published in the encryption record.

While the basic pre-encrypted ballots are identical to standard \EG ballots, the confirmation codes are computed differently.  Unlike standard \EG ballots, pre-encrypted ballot confirmation codes are computed before any selections are made.  The confirmation codes on pre-encrypted ballots are computed from the full set of pre-encryptions.  This is the same whether the pre-encrypted ballot is cast or spoiled.

---- S4.4.1
\subsubsection{Election Record Presentation}
The presentation of data in the election record should be cognizant of the fact that there are two very different uses that may be made of this record.  Individual voters will want to look up their own cast and uncast ballots and to easily review that they match their expectations.  Election verifiers will want to verify the cryptographic artifacts associated with individual cast and uncast ballots and check their consistency as well as the consistency of the reported tallies.

It should therefore be possible for voters to see, in as clean a presentation as is feasible, the short codes associated with selections made on their cast ballots and the short codes associated with all possible selections on uncast ballots.  The presentation of uncast ballots should match, as closely as feasible, the appearance of the physical uncast ballot as this presentation would facilitate comparison between the two.

For election verifiers, all of the cryptographic artifacts should be made available for verification.  Verifiers should not only confirm the consistency of this additional data but also that this additional data is consistent with the cleaner data views made available to individual voters.

---- S4.5
\subsection{Verification of Pre-Encrypted Ballots}
Every step of verification that applies to traditional \EG ballots also applies to pre-encrypted ballots – with the exception of the process for computing confirmation codes.  However, there are some additional verification steps that must be applied to pre-encrypted ballots.  Specifically, the following verifications should be done for every pre-encrypted cast ballot contained in the election record.
\begin{itemize}
    \item The ballot confirmation code correctly matches the hash of all contest hashes on the ballot (listed sequentially).
    \item Each contest hash correctly matches the hash of all selection hashes (including null selection hashes) within that contest (sorted within each contest).
    \item All short codes shown to voters are correctly computed from selection hashes in the election record which are, in turn, correctly computed from the pre-encryption vectors published in the election record.
    \item For contests with selection limit greater than 1, the selection vectors published in the election record match the product of the pre-encryptions associated with the short codes listed as selected.
\end{itemize}

The following verifications should be done for every pre-encrypted ballot listed in the election record as uncast.
\begin{itemize}
    \item The ballot confirmation code correctly matches the hash of all contest hashes on the ballot (listed sequentially).
    \item Each contest hash correctly matches the hash of all selection hashes (including null selection hashes) within that contest (sorted within each contest).
    \item All short codes on the ballot are correctly computed from the selection hashes in the election record which are, in turn, correctly computed from the pre-encryption vectors published in the election record.
    \item The decryptions of all pre-encryptions correspond to the plaintext values indicated in the election manifest.
\end{itemize}

\EGverif{\veriftitlePreEncryptedBallotsCorrectnessOfSelectionEncryptions}{\label{verif:PreEncryptedBallotsCorrectnessOfSelectionEncryptions}
\veriftextPreEncryptedBallotsCorrectnessOfSelectionEncryptions}

\EGverif{\veriftitlePreEncryptedBallotsAdherenceToVoteLimits}{\label{verif:PreEncryptedBallotsAdherenceToVoteLimits}
\veriftextPreEncryptedBallotsAdherenceToVoteLimits}

\EGverif{\veriftitlePreEncryptedValidationOfTrackingCodes}{\label{verif:PreEncryptedValidationOfTrackingCodes}
\veriftextPreEncryptedValidationOfTrackingCodes}

\EGverifBallot{\veriftitlePreEncryptedValidationOfShortCodes}{\label{verif:PreEncryptedValidationOfShortCodes}
\veriftextPreEncryptedValidationOfShortCodes}


---- S4.6
\subsection{Hash-Trimming Functions}
To allow vendors and jurisdictions to present distinct formats to their voters, the details of the hash-trimming function that produces short codes from full-sized hashes are not explicitly provided.  However, to facilitate verification, a variety of possible hash-trimming functions are pre-specified here.

\begin{itemize}
\item \hbox to 3in{\bf Two Hex Characters\hfil} $\Omega_1(x)=$ final byte of $x$ expressed as two hexadecimal characters
\item \hbox to 3in{\bf Four Hex Characters\hfil} $\Omega_2(x)=$ final two bytes of $x$ expressed as four hexadecimal characters
\item \hbox to 3in{\bf Letter-Digit\hfil} $\Omega_3(x)=$ final byte of $x$ expressed as a letter followed by a digit with $0,1,\ldots,255$ mapping to A0,A1,...,A9,B0,B1,...B9,...,Z0,Z1,...,Z5
\item \hbox to 3in{\bf Digit-Letter\hfil} $\Omega_4(x)=$ final byte of $x$ expressed as a digit followed by a letter with $0,1,\ldots,255$ mapping to 0A,0B,...,0Z,1A,1B,...1Z,...,9A,9B,...,9V
\item \hbox to 3in{\bf Number: 0-255\hfil} $\Omega_5(x)=$ final byte of $x$ expressed as a number with $0,1,\ldots,255$ mapping to $0,1,\ldots,255$ using the identity function
\item \hbox to 3in{\bf Number: 1-256\hfil} $\Omega_6(x)=$ final byte of $x$ expressed as a number with $0,1,\ldots,255$ mapping to $1,2,\ldots,256$ by adding 1
\item \hbox to 3in{\bf Number: 100-355\hfil} $\Omega_7(x)=$ final byte of $x$ expressed as a number with $0,1,\ldots,255$ mapping to $100,101,\ldots,355$ by adding 100
\item \hbox to 3in{\bf Number: 101-356\hfil} $\Omega_8(x)=$ final byte of $x$ expressed as a number with $0,1,\ldots,255$ mapping to $101,102,\ldots,355$ by adding 101
\end{itemize}

\pagebreak


-------- Section 5

\section{Hash Computation}\label{sec:hashing}
The function $H$ that is used throughout \EG is instantiated based on the hashed message authentication code \HMAC. This section defines how to evaluate $H$. It first defines how inputs are represented as byte arrays and then how these inputs are used to compute hash values.   

S5.1
\subsection{Input data representation}\label{sec:hashinputdata}

All inputs to the function $H$ are byte arrays. A \emph{byte} is a non-negative integer less than $2^8$, i.e. an integer in the set $\Bcal = \{0,1,\dots,255\}$. Its binary form consists of at most $8$ bits. Its hexadecimal form consists of at most two hexadecimal characters. Here, the leading 0 characters are written out such that a byte always has exactly two hexadecimal characters.  Therefore, $\Bcal$ is represented as $\{\mathtt{0x00}, \mathtt{0x01}, \mathtt{0x02},\dots \mathtt{0xFE}, \mathtt{0xFF}\}$. 

A \emph{byte array} $\mathrm{B}$ of length $m$ is an array of $m$ bytes $\mathrm{b}_0, \mathrm{b}_1, \dots, \mathrm{b}_m \in \Bcal$. It is represented by the concatenation\footnote{The symbol $\parallel$ simply denotes concatenation and does not mean that this symbol is inserted as a separator into the array in any way.} of the byte values as $\mathrm{B} = \mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_m$. A byte array of length $m$ consists of $8m$ bits. For $0 \leq i < 8m$, the $i$-th bit of the byte array $\mathrm{B}$ is the $(i \bmod 8)$-th bit of the byte $\mathrm{b}_{\lfloor i/8 \rfloor}$.\footnote{Here, $\lfloor\cdot\rfloor$ denotes the floor function, which means that the result is obtained by rounding down. For a real number $x$, $\lfloor x \rfloor$ is the largest integer that is not larger than $x$.} The set of all byte arrays of length exactly $m$ is denoted by $\Bcal^m$ and the set of all byte arrays of any length is denoted by $\Bcal^*$.

Any byte array $\Bcal$ of length $m$ represents a non-negative (i.e. unsigned) integer less than $2^{8m}$ by interpreting the bytes of $\Bcal$ as the digits of the representation in base $2^8$ with the most significant bytes to the left, i.e. in big endian format. For example, the byte array $\Bcal = \mathtt{0x1F}\parallel \mathtt{0xFF}$ of length $2$ represents the integer $\mathtt{0x1FFF}$ in hexadecimal form, which corresponds to the integer $2^{13}-1 = 8191$. In general, let $\mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{m-1}$ be a byte array of length $m$, the integer 
\begin{equation}
  \mathrm{b}_0\cdot 2^{(m-1)\cdot 8} + \mathrm{b}_1\cdot 2^{(m-2)\cdot 8} + \dots + \mathrm{b}_{m-1}
\end{equation}
is a non-negative integer less than $2^{8m}$. Vice versa, if $0\leq a < 2^{8m}$, then the byte array of length $m$ representing $a$ is given as 
\begin{equation}
  \bytes(a, m) = \mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{m-1},\mbox{ where } \mathrm{b}_i = \lfloor a/ 2^{8(m-1-i)} \rfloor \bmod 2^8.
\end{equation}
In this document and if not specified otherwise, a byte array and big endian non-negative integers are used synonymously. However, byte arrays representing integer data types have a fixed length and must be padded with $\mathtt{0x00}$ bytes to the left. The byte array $\mathtt{0x00}\parallel\mathtt{0x1F}\parallel \mathtt{0xFF}$ represents the same integer as $\Bcal$, but has length $3$ instead of $2$. For the integer data types used in \EG, this is laid out in detail in the following sections.


S5.1.1
\subsubsection{Integers modulo the large prime $p$}
Most inputs to $H$ like public keys, vote encryptions and commitments for NIZK proofs consist of big integers modulo the large prime $p$, i.e. integers in the set $\Z_p = \{0,1,\dots, p-1\}$. Any such element is represented in big endian format by a fixed size byte array of length exactly $l_p$, the length of the byte array representing $p$. If $p$ has 4096 bits like the prime given in the standard parameters in Section~\ref{sec:parameters}, this length is exactly 512. The conversion from an integer to a byte array works explicitly as follows. For $a \in \Z_p$, the byte array $\bytes(a, l_p)$ of length $l_p$ representing $a$ is defined as
\begin{equation}
  \bytes(a, l_p)  = \mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{l_p-1},
\end{equation}
where 
\begin{equation}
  \mathrm{b}_{i} = \lfloor a/ 2^{8(l_p-1-i)} \rfloor \bmod 2^8 \in \Bcal \mbox{ for }  i \in \{0, 1, \dots, l_p-1\}.
\end{equation} 
The bytes $\mathrm{b}_i$ are the coefficients of $a$ when it is written in base $2^8$, i.e.
\begin{equation}
a = \sum_{i=0}^{l_p-1} \mathrm{b}_{i} 2^{8(l_p-1-i)} = \mathrm{b}_0\cdot 2^{(l_p-1)\cdot 8} + \mathrm{b}_1\cdot 2^{(l_p-2)\cdot 8} + \dots + \mathrm{b}_{l_p-1}.  
\end{equation}
Any byte array $\bytes(a, l_p)$ that represents an integer $a$ modulo $p$ always has length $l_p$.
%
This means that, for the standard parameters, where $l_p = 512$, we have $\bytes(a, 512) = \mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{511}$, where
\begin{equation*}
  \mathrm{b}_{i} = \lfloor a/ 2^{8(511-i)} \rfloor \bmod 2^8 \in \Bcal \mbox{ for } i \in \{0, 1, \dots, 511\}.
\end{equation*}
For example, $\bytes(0, 512) = \mathtt{0x0000\dots 000000000000}$ is a byte array of 512 00-bytes, $\bytes(15, 512) = \mathtt{0x0000\dots 00000000000F}$, $\bytes(8572345, 512)= \texttt{0x0000\dots 00000082CDB9}$, and $\bytes(p-1, 512)$ is the array shown in Section~\ref{sec:parameters} for $p$, but ending with \texttt{\dots FFFFFFFFFFFFFE}. 

S5.1.2
\subsubsection{Integers modulo the small prime $q$}\label{sec:intmodq}
Other inputs are integers modulo the smaller prime $q$, such as response values in NIZK proofs and encryption nonces. They are integers in the set $\Z_q = \{0,1,\dots,q-1\}$ and are represented by a fixed size byte array of length exactly $l_q$ in big endian format. For the standard parameters, $l_q=32$. The conversion from integer to byte array works as above. If $a\in \Z_q$, the byte array $\bytes(a,32)$ representing $a$ is defined as
\begin{equation}
  \bytes(a,32) = \mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{31},
\end{equation}
where
\begin{equation}
  \mathrm{b}_{i} = \lfloor a/ 2^{8(31-i)} \rfloor \bmod 2^8 \in \Bcal \mbox{ for } i \in \{0, 1, \dots, 31\}.
\end{equation}
Again, the bytes are coefficients of $a$ in its $2^8$-adic form, namely
\begin{equation}
  a = \sum_{i=0}^{31} \mathrm{b}_{i} 2^{8(31-i)} = \mathrm{b}_0\cdot 2^{31\cdot 8} + \mathrm{b}_1\cdot 2^{30\cdot 8} + \dots + \mathrm{b}_{31}.  
\end{equation}
All byte arrays that represent integers modulo q have length 32. For example,
\begin{align*}
  \bytes(0,32) & = \mathtt{0x0000000000000000000000000000000000000000000000000000000000000000},\\
  \bytes(16,32) & = \mathtt{0x0000000000000000000000000000000000000000000000000000000000000010},\\ 
  \bytes(q-1,32) & = \mathtt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF42}.
\end{align*}

S5.1.3
\subsubsection{Small integers}
Other integers such as \emph{indices} are much smaller and are encoded as fixed length byte arrays in big endian format in the same way, but have much smaller lengths. In \EG, all such small integers are assumed to be smaller than $2^{31}$. They can therefore be encoded with $4$ bytes, i.e. with $32$ bits and the most significant bit set to $0$.\footnote{Setting the most significant bit to $0$ is done in consideration of languages and runtimes that do not have full support for unsigned integers.}

The number of guardians $n$ and the quorum threshold value $k$ are examples of such small integers that require even less than 4 bytes for all reasonable use cases, i.e. they are represented as $\bytes(n, 4)$ and $\bytes(k, 4)$. For example, $\bytes(5,4) = \mathtt{0x00000005}$ and $\bytes(3,4) = \mathtt{0x00000003}$.

S5.1.4
\subsubsection{Strings}\label{sec:stringencoding}
When an input to the function $H$ is a string $s$, it is encoded as a byte array $\bytes(s, \len(s))$ using UTF-8 encoding. Here, $\len(s)$ is the length of the UTF-8 encoding of the string $s$ in bytes. For example, the string ``ElectionGuard" is encoded as $\bytes(\mathrm{``ElectionGuard"}, 13) = \mathtt{0x456C656374696F6E4775617264}$.
Some string inputs may be of variable length that cannot be specified in advance by this document. Therefore all encodings of strings that are input to the \EG hash function $H$ start with a $4$-byte encoding in big endian format of the byte length of the string encoding followed by the encoding itself.\footnote{The maximal length of strings that can be encoded for input to $H$ is therefore $2^{32}$ bytes.} For example, if the string ``ElectionGuard" is an input to $H$, the input byte array is $\bytes(13, 4)\parallel \bytes(\mathrm{``ElectionGuard"}, 13) = \mathtt{0x0000000D456C656374696F6E4775617264}$.

S5.1.5
\subsubsection{Files}
When an input to the function $H$ is a file \texttt{file}, it is parsed as input entirely, meaning that all bytes of the file are parsed to $H$ as a byte array $\bytes(\mathtt{file}, \len(\mathtt{file}))$ that is a concatenation of all the bytes of the file in order. As above for strings, file lengths are not specified in this document and file inputs to $H$ start with a $4$-byte encoding\footnote{Input files to $H$ are restricted to a length of $2^{32}$ bytes.} in big endian format of the file byte length $\len(\mathtt{file})$ followed by the file bytes, i.e. $\bytes(\len(\mathtt{file}), 4)\parallel \bytes(\mathtt{file}, \len(\mathtt{file}))$.

S5.2
\subsection{Hash function}
The hash function $H$ used in \EG is \HMAC-\SHA, i.e. \HMAC\footnote{NIST (2008) The Keyed-Hash Message Authentication Code (HMAC). In: FIPS 198-1. \url{https://csrc.nist.gov/publications/detail/fips/198/1/final}} instantiated with \SHA\footnote{NIST (2015) Secure Hash Standard (SHS). In: FIPS 180-4. \url{https://csrc.nist.gov/publications/detail/fips/180/4/final}}. Therefore, $H$ takes two byte arrays as inputs. 

The first input corresponds to the key in \HMAC. The \HMACSHA specification allows arbitrarily long keys, but preprocesses the key to make it exactly 64 bytes (512 bits) long, which is the block size for the input to the \SHA hash function. If the given key is smaller, \HMACSHA pads it with \texttt{00} bytes at the end, if it is longer, \HMACSHA hashes it first with \SHA and then pads it to 64 bytes. In \EG, all inputs that are used as the \HMAC key, i.e. all inputs to the first argument of $H$ have a fixed length of exactly 32 bytes.

The second input can have arbitrary length and is only restricted by the maximal input length for \SHA and \HMAC. Hence we view the function $H$ formally as follows (understanding that \HMAC implementations pad the $32$-byte keys to exactly $64$ bytes by appending $32$ $\mathtt{0x00}$ bytes): 

\begin{equation}
  H: \Bcal^{32}\times \Bcal^* \rightarrow \Bcal^{32},\ H(\mathrm{B}_0; \mathrm{B}_1) \mapsto \HMACSHA(\mathrm{B}_0,\mathrm{B}_1).
\end{equation}

\EG uses \HMAC not as a keyed hash function with a secret key or a message authentication code, but instead uses it as a general purpose hash function to implement a random oracle.\footnote{Dodis Y., Ristenpart T., Steinberger J., Tessaro S. (2012) \emph{To Hash or Not to Hash Again? (In)differentiability Results for $H^2$ and \HMAC.} This paper shows that \HMAC used as a general purpose hash function with keys of a fixed length shorter than $d-1$, where $d$ is the block length in bits of the underlying hash function is indifferentiable from a random oracle.}

The first input is used to bind hash values to a specific election by including the parameter base hash $\HH_P$, the election base hash $\HH_B$ or the extended base hash $\HH_E$. The second input consists of domain separation tags for different use cases and the actual data that is being hashed.

S5.3
\subsection{Hashing multiple inputs}
\EG often requires that multiple input elements are hashed together. In fact, the second input to the function $H$ specified in the previous section always consists of multiple parts. The input byte array $B_1$ is then simply the concatenation of the byte arrays that represent the multiple input elements as specified in Section~\ref{sec:hashinputdata} in the order specified in each case. As all byte arrays that represent input elements have a fixed length, there is no need for a separator byte or character. 

The notation in this document lists the multiple input elements in order separated by commas. The first input element forming the byte array $B_0$ and the list of elements forming the second byte array $B_1$ are separated by a semicolon.
To illustrate the notation, consider, for example, the challenge value for the proof of correctness in ballot encryption. It is computed as $H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1)$ (see Equation~\eqref{eq:encproof0_challenge}). This notation means that \HMACSHA is called as $\HMACSHA(\mathrm{B}_0, \mathrm{B}_1)$ with the byte arrays\footnote{The symbol $\parallel$ does not represent a separator symbol and is simply used to denote concatenation like for byte arrays as mentioned above.}
$$\mathrm{B}_0 = \HH_E,\ 
\mathrm{B}_1 = \mathtt{0x21}\parallel \bytes(K,l_p)\parallel \bytes(\alpha,l_p)\parallel\bytes(\beta,l_p)\parallel\bytes(a_0,l_p)\parallel\bytes(b_0,l_p)\parallel\bytes(a_1,l_p)\parallel\bytes(b_1,l_p)$$ 
as inputs.
The first argument is simply the extended base hash $\HH_E$. The second argument is the byte array that is the result of concatenating the domain separator byte $\mathtt{0x21}$ that identifies the use case and the byte arrays representing the public key $K$, the vote encryption components $\alpha$ and $\beta$ and the commitments to the Chaum-Pedersen proofs $a_0$, $b_0$, $a_1$, and $b_1$ in that order.

S5.4
\subsection{Hash function outputs}
The output of \SHA and therefore $H$ is a 256-bit string, which can be interpreted as a byte array of $32$ bytes. As such, outputs of $H$ are directly used as inputs to $H$ again without any modifications. 

When generating NIZK proofs, hash function outputs are involved in computations modulo $q$. Therefore they need to be interpreted as integers. The byte array $\mathrm{b}_0 \parallel \mathrm{b}_1 \parallel \dots \parallel \mathrm{b}_{31}$ is interpreted as a big endian base-$2^8$ representation of an integer $a$, which means that
\begin{equation}
  a = \sum_{i=0}^{31} \mathrm{b}_{i} 2^{8(31-i)} = \mathrm{b}_0\cdot 2^{31\cdot 8} + \mathrm{b}_1\cdot 2^{30\cdot 8} + \dots + \mathrm{b}_{31}.
\end{equation}
Therefore, hash function outputs correspond to integers in the interval $[0,2^{256}-1]$. Note that, although this byte representation is identical to the byte representation of integers modulo $q$ as described above, the integers corresponding to hash function outputs do not have to be smaller than $q= 2^{256} - 189$. However, in practice, it is highly unlikely that an integer in the interval $[2^{256}-189, 2^{256}-1]$ will occur. When picking a 256-bit integer uniformly at random, the probability that it is not smaller than $q$ is negligibly small, namely $189/2^{256} < 2^{-248}$.

Although hash function outputs are used in computations modulo $q$, they are not reduced modulo $q$ by default. Each hash function output, such as a challenge value $c$ in the computation of a NIZK proof, remains a byte array of length $32$ that can be interpreted as an integer in $[0,2^{256}-1]$. Only during the computation of response values does a reduction modulo $q$ occur.

S5.5
\subsection{Domain separation}
The tables below list every use of the hash function $H$ in this specification together with the specific domain separation input for the second argument. They explicitly provide the byte arrays $\mathrm{B}_0$ and $\mathrm{B}_1$ that are passed to \HMAC as inputs to evaluate $\HMACSHA(\mathrm{B}_0,\mathrm{B}_1)$ together with the length $\len(\B_1)$ of $\B_1$ in bytes (note that always $\len(\B_0)=32$). The tables use the standard parameters such that $l_p = 512$ and $l_q = 32$. For other parameters, the values $l_p$ and $l_q$ can be different.

S5.5.1
\subsubsection{Parameter base, manifest and base hashes}
\begin{center}
  \begin{tabularx}{\textwidth}{Xr}
  \toprule
  Computation of the parameter base hash $\HH_P$ & \S\ref{sec:parameterhash}\\
  $\HH_P = H(\mathtt{ver};\mathtt{0x00}, p, q, g)$ & \eqref{eq:parameterhash}\\
  $\mathrm{B}_0 = \mathtt{ver} = \mathtt{0x322E302E30} \parallel \bytes(0,27)$\\
  $\mathrm{B}_1 = \mathtt{0x00}\parallel \bytes(p,512)\parallel\bytes(q,32)\parallel \bytes(g,512)$\\
  $\len(\B_1) = 1057$\\
  \midrule
  Computation of the manifest hash $\HH_M$ & \S\ref{sec:manifest}\\
  $\HH_M = H(\HH_P;\mathtt{0x01}, \mathtt{manifest})$ & \eqref{eq:manifesthash}\\
  $B_0 = \HH_P$ & \\
  $B_1 = \mathtt{0x01} \parallel \bytes(\len(\mathtt{manifest}), 4) \parallel \bytes(\mathtt{manifest}, \len(\mathtt{manifest}))$ & \\
  $\len(B_1) = 5 + \len(\mathtt{manifest})$ & \\
  \midrule
  Computation of the base hash $\HH_B$ & \S\ref{sec:basehash}\\
  $\HH_B = H(\HH_P; \mathtt{0x02}, \HH_M, n, k)$ & \eqref{eq:basehash}\\ 
  $\mathrm{B}_0 = \HH_P$\\
  $\mathrm{B}_1 = \mathtt{0x02} \parallel \HH_M\parallel \bytes(n,4) \parallel \bytes(k,4)$& \\
  $\len(\B_1) = 41$\\
  \bottomrule
  \end{tabularx}
\end{center}

S5.5.2
\subsubsection{Key generation and extended base hash}
\begin{center}
  %%%%%%%%%%%%%%%%%%%%%%
  \begin{tabularx}{\textwidth}{Xr}
  \toprule
  NIZK proof of knowledge of polynomial coefficients in key generation & \S\ref{sec:keygendetails}\\
  $c_{i,j} = H(\HH_P; \mathtt{0x10}, i, j, K_{i,j},h_{i,j})$ & \eqref{eq:hash_nizk_keygen}\\
  $\mathrm{B}_0 = \HH_P$\\
  $\mathrm{B}_1 = \mathtt{0x10}\parallel\bytes(i, 4)\parallel\bytes(j, 4)\parallel \bytes(K_{i,j},512)\parallel\bytes(h_{i,j},512)$ \\
  $\len(\B_1) = 1033$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Encryption of key shares in key generation & \S\ref{sec:keygendetails}\\
  $k_{i,\ell} = H(\HH_P; \mathtt{0x11}, i, \ell, K_\ell, \alpha_{i,\ell}, \beta_{i,\ell})$ & \eqref{eq:hash_shareenc}\\
  $\mathrm{B}_0 = \HH_P$\\
  $\mathrm{B}_1 = \mathtt{0x11}\parallel\bytes(i,4)\parallel\bytes(\ell,4)\parallel\bytes(K_\ell, 512)\parallel\bytes(\alpha_{i,\ell},512)\parallel\bytes(\beta_{i,\ell},512)$ \\
  $\len(\B_1) = 1545$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of the extended base hash $\HH_E$ & \S\ref{sec:keygendetails}\\
  $\HH_E = H(\HH_B; \mathtt{0x12}, K)$ & \eqref{eq:extbasehash}\\
  $\mathrm{B}_0 = \HH_B$\\
  $\mathrm{B}_1 = \mathtt{0x12} \parallel \bytes(K,512)$ \\
  $\len(\B_1) =  513$\\
  \bottomrule
  \end{tabularx}
\end{center}

S5.5.3
\subsubsection{Ballot encryption and confirmation codes}
\enlargethispage{1cm}
\begin{center}
  %%%%%%%%%%%%%%%%%%%%%%
  \begin{tabularx}{\textwidth}{Xr}
  \toprule
  Computation of encryption nonces & \$\ref{sec:noncegen}\\
  $\xi_{i,j} = H(\HH_E; \mathtt{0x20},\xi_B,\indc(\Lambda_i),\indo(\lambda_j))$ & \eqref{eq:noncegen}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x20} \parallel \xi_B \parallel \bytes(\indc(\Lambda_i), 4) \parallel \bytes(\indo(\lambda_j),4) $ \\
  $\len(\B_1) = 41$\\
  Computation of encryption nonces for contest data & \S\ref{sec:encrypt_ext_data}\\
  $\xi = H(\HH_E; \mathtt{0x20}, \xi_B, \indc(\Lambda), \mathtt{``contest\_data"})$ & \eqref{eq:noncegen_contestdata}\\
  $\B_0 = \HH_E$\\
  \multicolumn{2}{l}{
  $\B_1 = \mathtt{0x20} \parallel \xi_B \parallel \bytes(\indc(\Lambda), 4) \parallel \mathtt{0x0000000C636F6E746573745F64617461}$}\\
  $\len(\B_1) = 53$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Challenge computation for 0/1-range proofs & \S\ref{sec:proofsballotcorrectness}\\
  $c = H(\HH_E;\mathtt{0x21},K,\alpha,\beta,a_0,b_0,a_1,b_1)$ & \eqref{eq:encproof0_challenge}, \eqref{eq:encproof1_challenge}\\
  $\mathrm{B}_0 = \HH_E$\\
  \multicolumn{2}{l}{
  $\mathrm{B}_1 = \mathtt{0x21} \parallel \bytes(K,512)\parallel\bytes(\alpha,512)\parallel\bytes(\beta,512)\parallel\bytes(a_0,512)\parallel\bytes(b_0,512)\parallel\bytes(a_1,512)\parallel\bytes(b_1,512)$}\\
  $\len(\B_1) = 3585$\\
  Challenge computation for $L$-range proofs & \S\ref{sec:selectionlimit}\\
  $c = H(\HH_E;\mathtt{0x21},K,\bar\alpha,\bar\beta,a_0,b_0,a_1,b_1,\dots,a_L,b_L)$ & \eqref{eq:nizk_c_selection_limit}\\
  $\mathrm{B}_0 = \HH_E$\\
  \multicolumn{2}{l}{
  $\mathrm{B}_1 = \mathtt{0x21} \parallel \bytes(K,512)\parallel\bytes(\alpha,512)\parallel\bytes(\beta,512)\parallel\bytes(a_0,512)\parallel\bytes(b_0,512)\parallel\dots\parallel\bytes(a_L,512)\parallel\bytes(b_L,512)$}\\
  $\len(\B_1) = 1+(2L+5)\cdot 512$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Key derivation for contest data encryption & \S\ref{sec:encrypt_ext_data}\\
  $k = H(\HH_E; \mathtt{0x22}, K, \alpha, \beta)$ & \eqref{eq:k_enc_contest}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x22} \parallel \bytes(K,512)\parallel\bytes(\alpha,512)\parallel\bytes(\beta,512)$\\
  $\len(\B_1) = 1537$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of contest hashes & \S\ref{sec:contesthash}\\
  $\chi_l = H(\HH_E; \mathtt{0x23}, \indc(\Lambda_l), K, \alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m)$ & \eqref{eq:contesthash}\\
  $\mathrm{B}_0 = \HH_E$\\
  \multicolumn{2}{l}{
  $\mathrm{B}_1 = \mathtt{0x23} \parallel \bytes(\indc(\Lambda_l), 4) \parallel \bytes(K,512)\parallel\bytes(\alpha_1,512)\parallel\bytes(\beta_1,512)\parallel\bytes(\alpha_2,512)\parallel\ldots$}\\
  \quad\qquad$\parallel\bytes(\alpha_m,512)\parallel\bytes(\beta_m,512)$ & \\
  $\len(\B_1) = 5 + (2m+1)\cdot 512$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of confirmation codes & \S\ref{sec:confirmationcode}\\
  $\HH(B) = H(\HH_E; \mathtt{0x24}, \chi_1, \chi_2, \ldots, \chi_{m_B}, \B_{\mathrm{aux}})$ & \eqref{eq:confirmationcode}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x24} \parallel \chi_1\parallel \chi_2\parallel \ldots\parallel \chi_{m_B}\parallel \bytes(\len(\B_{\mathrm{aux}}), 4) \parallel \B_{\mathrm{aux}}$\\
  $\len(\B_1) = 5 + m_B\cdot 32 + \len(\B_{\mathrm{aux}})$\\
  Hash chain initialization for ballot chaining & \\
  $\HH_0 = H(\HH_E;\mathtt{0x24},\B_{\mathrm{aux},0})$ & \eqref{eq:hashchain0}\\
  $\B_1 = \mathtt{0x24}\parallel \bytes(\len(\B_{\mathrm{aux},0}), 4)\parallel \B_{\mathrm{aux},0}$, $\len(\B_1) = 5 + \len(\B_{\mathrm{aux},0})$ \\
  Hash chain closing for ballot chaining & \\
  $\overline{\HH} = H(\HH_E; \mathtt{0x24}, \overline\B_{\mathrm{aux}})$ & \eqref{eq:hashchainclose}\\
  \multicolumn{2}{l}{
  $\B_1 = \mathtt{0x24}\parallel\overline\B_{\mathrm{aux}} = \mathtt{0x24}\parallel\HH(B_\ell)\parallel \bytes(\len(\B_{\mathrm{aux},0}), 4)\parallel \B_{\mathrm{aux},0} \parallel \mathtt{0x00000005434C4F5345}$}\\
  $\len(\B_1) = 46 + \len(\B_{\mathrm{aux},0})$ & \\
  \bottomrule
  \end{tabularx}
  %%%%%%%%%%%%%%%%%%%%%%
\end{center}

S5.5.4
\subsubsection{Verifiable decryption}
\begin{center}
\begin{tabularx}{\textwidth}{Xr}
  \toprule
  Challenge computation for proofs of correct decryption & \S\ref{sec:verifiable_decrypt_proof}\\
  $c = H(\HH_E;\mathtt{0x30},K,A,B,a,b,M)$ & \eqref{eq:nizk_c_dec}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x30} \parallel \bytes(K,512)\parallel\bytes(A,512)\parallel\bytes(B,512)\parallel\bytes(a,512)\parallel\bytes(b,512)\parallel\bytes(M,512)$\\
  $\len(\B_1) = 3073$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Challenge computation for proofs of correct decryption of contest data & \S\ref{sec:decrypt_contest_data}\\
  $c = H(\HH_E;\mathtt{0x31},K,C_0,C_1,C_2,a,b,\beta)$ & \eqref{eq:nizk_c_dec_cont}\\
  $\mathrm{B}_0 = \HH_E$\\
  \multicolumn{2}{l}{$\mathrm{B}_1 = \mathtt{0x31} \parallel \bytes(K,512)\parallel\bytes(C_0,512)\parallel\bytes(C_1,512)\parallel\bytes(C_2,512)\parallel\bytes(a,512)\parallel\bytes(b,512)\parallel\bytes(\beta,512)$}\\
  $\len(\B_1) = 3585$ & \\
  \bottomrule
\end{tabularx}
\end{center}

S5.5.5
\subsubsection{Pre-encrypted ballots}
\begin{center}
  %%%%%%%%%%%%%%%%%%%%%%
  \begin{tabularx}{\textwidth}{Xr}
  \toprule
  Computation of selection hashes for pre-encrypted ballots & \S\ref{sec:selectionhash_pre}\\
  $\psi_i = H(\HH_E; \mathtt{0x40}, K,\alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m)$ & \eqref{eq:selectionhash_pre}\\
  $\psi_{m+\ell}=H(\HH_E; \mathtt{0x40}, K,\alpha_1, \beta_1, \alpha_2, \beta_2\ldots,\alpha_m, \beta_m)$ & \eqref{eq:nullhash_pre}\\
  $\mathrm{B}_0 = \HH_E$\\
  \multicolumn{2}{l}{$\mathrm{B}_1 = \mathtt{0x40} \parallel \bytes(K,512)\parallel\bytes(\alpha_1,512)\parallel\bytes(\beta_1,512)\parallel\bytes(\alpha_2,512)\parallel\ldots\parallel\bytes(\alpha_m,512)\parallel\bytes(\beta_m,512)$}\\
  $\len(\B_1) = 1 + (2m+1)\cdot 512$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of contest hashes for pre-encrypted ballots & \S\ref{sec:contesthash_pre}\\
  $\chi_l = H(\HH_E; \mathtt{0x41}, \indc(\Lambda_l), K,\psi_{\sigma(1)},\psi_{\sigma(2)},\ldots,\psi_{\sigma(m+L)})$ & \eqref{eq:contesthash_pre}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x41} \parallel \bytes(\indc(\Lambda_l), 4) \parallel \bytes(K,512)\parallel \psi_{\sigma(1)}\parallel\psi_{\sigma(2)}\parallel\ldots\parallel\psi_{\sigma(m+L)}$\\
  $\len(\B_1) = 517 + (m+L)\cdot 32$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of ballot hashes for pre-encrypted ballots & \S\ref{sec:confirmationcode_pre}\\
  $\HH(B)=H(\HH_E; \mathtt{0x42}, K,\chi_1,\chi_2,\ldots, \chi_{m_B})$ & \eqref{eq:ballothash_pre}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x42} \parallel \bytes(K,512)\parallel \chi_{1}\parallel\chi_{2}\parallel\ldots\parallel\chi_{m_B}$\\ 
  $\len(\B_1) = 513 + m_B\cdot 32$\\
  \midrule
  %%%%%%%%%%%%%%%%%%%%%%
  Computation of encryption nonces & \$\ref{sec:noncegen_pre}\\
  $\xi_{i,j,k}=H(\HH_E; \mathtt{0x43},\xi,\indc(\Lambda_i),\indo(\lambda_j),\indo(\lambda_k))$ & \eqref{eq:noncegen_pre}\\
  $\mathrm{B}_0 = \HH_E$\\
  $\mathrm{B}_1 = \mathtt{0x43} \parallel \xi \parallel \bytes(\indc(\Lambda_i), 4) \parallel \bytes(\indo(\lambda_j), 4) \parallel \bytes(\indo(\lambda_k), 4) $ \\
  $\len(\B_1) = 45 $\\
  \bottomrule 
  \end{tabularx}
  \end{center}

-------- Section 6 Verifier Construction

\pagebreak
\section{Verifier Construction}
While it is desirable for anyone who may construct an \EG verifier to have as complete an understanding as possible of the \EG 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.

---- S6.1
\subsection{Implementation Details}

---- S6.1a
There are four operations which must be performed -- all on very large integer values: modular addition, modular multiplication, modular exponentiation, and hash computations, i.e. evaluations of the hash function $H$. 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.

---- S6.1b
\subsubsection*{Modular addition}
To compute $(a+b) \bmod n$, one can compute $((a \bmod n)+(b \bmod n)) \bmod n$.  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 $(a+b) \bmod n = a+b$ (if $a+b<n$) or $a+b-n$ (if $a+b\geq n$).

---- S6.1c
\subsubsection*{Modular multiplication}
To compute $(a\cdot b) \bmod n$, one can compute $((a \bmod n)\cdot (b \bmod n)) \bmod n$. 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.

---- S6.1d
\subsubsection*{Modular exponentiation}
To compute $a^b \bmod n$, one can compute $(a \bmod n)^b \bmod n$, but one should not perform a modular reduction on the exponent.\footnote{In general, if $n$ is prime, one can compute $a^b \bmod n$ as $(a \bmod n)^{(b \bmod (n-1))} \bmod n$. In the particular instance of this specification, if $a\in \Z_p^r$, then one can compute $a^b \bmod p$ as $a^{(b \bmod q)} \bmod p$.}  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 special-purpose modular exponentiation method such as a repeated square-and-multiply algorithm 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.


\pagebreak
---- S6.2
\subsection{Validation Steps}

---- S6.2.1
\subsubsection{Parameter verification}

\pagebreak

---- S6.2.2
\subsubsection{Key ceremony verification}

\EGverifExtendedrepeat{verif:guardiansPK}{\veriftitleGuardianPublicKeyValidation}{\veriftextGuardianPublicKeyValidation}
    
\pagebreak
    

\EGverifExtendedrepeat{verif:electionPK}{\veriftitleElectionPublicKeyValidation}{\veriftextElectionPublicKeyValidation}

---- S6.2.3
\subsubsection{Extended base hash verification}
\pagebreak

---- S6.2.4
\subsubsection{Ballot verification}

\EGverifrepeat{verif:selection}{\veriftitleCorrectnessOfSelectionEncryptions}{\veriftextCorrectnessOfSelectionEncryptions}

    
\pagebreak
\vspace{.5in}
\EGverifrepeat{verif:selectionlimit}{\veriftitleAdherenceToVoteLimits}{\veriftextAdherenceToVoteLimits}

    
\pagebreak
\vspace{.5in}
\EGverifrepeat{verif:trackingcodes}{\veriftitleValidationOfTrackingCodes}{\veriftextValidationOfTrackingCodes}



\pagebreak
---- S6.2.5
\subsubsection{Tally verification}
\EGverifrepeat{verif:aggregation}{\veriftitleCorrectnessOfBallotAggregation}{\veriftextCorrectnessOfBallotAggregation}

\pagebreak

\vspace{.5in}
\EGverifrepeat{verif:decryption}{\veriftitleCorrectnessOfDecryptions}{
\veriftextCorrectnessOfDecryptions}


\pagebreak
\vspace{.5in}
\EGverifrepeat{verif:tallies}{\veriftitleValidationOfCorrectDecryptionOfTallies}{
\veriftextValidationOfCorrectDecryptionOfTallies}


\pagebreak

---- S6.2.6
\subsubsection{Verification of correct contest data decryption}
\EGverifrepeat{verif:extdecryption}{\veriftitleCorrectnessOfDecryptionsOfContestData\footnotemark}{\veriftextCorrectnessOfDecryptionsOfContestData}


\pagebreak


---- S6.2.7
\subsubsection{Verification of challenged ballots}
\EGverifBallotrepeat{verif:challengedDecrypt}{\veriftitleCorrectnessOfDecryptionsChallenged}{\veriftextCorrectnessOfDecryptionsChallenged}

\pagebreak

\EGverifBallotrepeat{verif:challengedballots}{\veriftitleValidationOfCorrectDecryptionOfChallengedBallots}{\veriftextValidationOfCorrectDecryptionOfChallengedBallots}

\pagebreak

\EGverifBallotrepeat{verif:challengedDecryptContest}{\veriftitleCorrectnessOfDecryptionsOfContestDataChallenged}{\veriftextCorrectnessOfDecryptionsOfContestDataChallenged}


\pagebreak

---- S6.2.8
\subsubsection{Verification of pre-encrypted ballots}


\EGverifrepeat{verif:PreEncryptedBallotsCorrectnessOfSelectionEncryptions}
{\veriftitlePreEncryptedBallotsCorrectnessOfSelectionEncryptions}
{\veriftextPreEncryptedBallotsCorrectnessOfSelectionEncryptions}

\pagebreak

\EGverifrepeat{verif:PreEncryptedBallotsAdherenceToVoteLimits}
{\veriftitlePreEncryptedBallotsAdherenceToVoteLimits}
{\veriftextPreEncryptedBallotsAdherenceToVoteLimits}


\pagebreak


\EGverifrepeat{verif:PreEncryptedValidationOfTrackingCodes}
{\veriftitlePreEncryptedValidationOfTrackingCodes}
{\veriftextPreEncryptedValidationOfTrackingCodes}



\pagebreak

\EGverifBallotrepeat{verif:PreEncryptedValidationOfShortCodes}
{\veriftitlePreEncryptedValidationOfShortCodes}
{\veriftextPreEncryptedValidationOfShortCodes}


\pagebreak

-------- Section 7 Applications to End-to-End Verifiability and Risk-Limiting Audits
    
---- S7
\section{Applications to End-to-End Verifiability and Risk-Limiting Audits}
The methods described in this specification can be used to enable either end-to-end (E2E) verifiability or enhanced risk-limiting audits (RLAs). In both cases, the ballots are individually encrypted and proofs are provided to allow observers to verify that the set of encrypted ballots is consistent with the announced tallies in an election.

In the case of E2E-verifiability, voters are given confirmation codes to enable them to confirm that their individual ballots are correctly recorded amongst the set of encrypted ballots.  In the case of RLAs, encrypted ballots are randomly selected and compared against physical ballots to obtain confidence that the physical records match the electronic records.

To support enhanced risk-limiting audits (RLAs), it may be desirable to encrypt the ballot nonce of each ballot with a simple administrative key rather than the “heavyweight” election encryption key. This streamlines the process for decrypting an encrypted ballot that has been selected for audit. It should be noted that the privacy risks of revealing decrypted ballots are substantially reduced in the RLA case since voters are not given confirmation codes that could be used to associate them with individual ballots.  The primary risk is a coercion threat (e.g., via pattern voting) that only manifests if the full set of ballots were to be decrypted.

While the administratively encrypted nonce can be stored in an electronic record alongside each encrypted ballot, one appealing RLA instantiation is for the administrative encryption of a ballot's nonce to be printed directly onto the physical ballot.  This allows an RLA to proceed by randomly selecting an encrypted ballot, fetching the associated physical ballot, extracting the nonce from its encryption on the physical ballot, using the nonce to decrypt the electronic record, and then comparing the physical ballot contents with those of the electronic record.  A malicious actor with an administrative decryption key would need to go to each individual physical ballot to obtain the nonces necessary to decrypt all of the encrypted ballots, and the access to do so would enable this malicious actor to obtain all of the open ballots without necessitating the administrative decryption key.

If E2E-verifiability and enhanced RLAs are both provided in the same election, there must be separate ballot encryptions (ideally, but not necessarily, using separate election encryption keys) of each ballot. The E2E-verifiable data set must be distinguished from the enhanced RLA data set.  Using the same data set for both applications would compromise voter privacy for voters whose ballots are selected for auditing.

-------- Section "8" Acknowledgments

\section*{Acknowledgments}
The authors are happy to thank Eion Blanchard, Nicholas Boucher, John Caron, Joey Dodds, Felix Doerre, Gerald Doussot, Aleks Essex, Keith Fung, Rainbow Huang, Chris Jeuell, Anunay Kulshrestha, Moses Liskov, Shreyas Minocha, Arash Mirzaei, Luke Myers, Karan Newatia, Olivier Pereira, John Ramsdell, Marsh Ray, Dan Shumow, Vanessa Teague, Aaron Tomb, Daniel Wagner, Jake Waksbaum, Dan Wallach, Matt Wilhelm, and Greg Zaverucha for many helpful comments and suggestions on earlier versions of this specification.

\pagebreak

-------- Section "9" Appendix: Other Parameters

\section*{Appendix: Other Parameters}

---- S9a
\subsubsection*{Reduced parameters -- using a 3072-bit prime}
Starting from the same 256-bit prime $q = 2^{256}-189$ for the group order, the procedure outlined in Section~\ref{sec:parameters} on the standard baseline parameters can be used to find a 3072-bit prime $p_{3072}$. This results in the following parameters that are provided here as an alternative. The parameters satisfy all the same requirements, but the smaller prime offers faster arithmetic in the base field and thus improved performance. This comes at the cost of a somewhat lower security level. The prime $p_{3072}$ is given as 
$p_{3072} = 2^{3072}-2^{2816}+2^{256} (\lfloor 2^{2560} \mathrm{ln}(2)\rfloor+\delta_{3072}) + 2^{256} - 1$
with 
{\small
$$
\delta_{3072}=298707407953437995876300625370749906325322663598036756391867662926569213935809577593.
$$
}
The hexadecimal representation of $p_{3072}$ is as follows.
{\allowdisplaybreaks
\begin{align*}
  p_{3072} \ = \ \mathtt{0x}
  & \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF}\\
  & \mathtt{B17217F7\ D1CF79AB\ C9E3B398\ 03F2F6AF\ 40F34326\ 7298B62D\ 8A0D175B\ 8BAAFA2B}\\
  & \mathtt{E7B87620\ 6DEBAC98\ 559552FB\ 4AFA1B10\ ED2EAE35\ C1382144\ 27573B29\ 1169B825}\\
  & \mathtt{3E96CA16\ 224AE8C5\ 1ACBDA11\ 317C387E\ B9EA9BC3\ B136603B\ 256FA0EC\ 7657F74B}\\
  & \mathtt{72CE87B1\ 9D6548CA\ F5DFA6BD\ 38303248\ 655FA187\ 2F20E3A2\ DA2D97C5\ 0F3FD5C6}\\
  & \mathtt{07F4CA11\ FB5BFB90\ 610D30F8\ 8FE551A2\ EE569D6D\ FC1EFA15\ 7D2E23DE\ 1400B396}\\
  & \mathtt{17460775\ DB8990E5\ C943E732\ B479CD33\ CCCC4E65\ 9393514C\ 4C1A1E0B\ D1D6095D}\\
  & \mathtt{25669B33\ 3564A337\ 6A9C7F8A\ 5E148E82\ 074DB601\ 5CFE7AA3\ 0C480A54\ 17350D2C}\\
  & \mathtt{955D5179\ B1E17B9D\ AE313CDB\ 6C606CB1\ 078F735D\ 1B2DB31B\ 5F50B518\ 5064C18B}\\
  & \mathtt{4D162DB3\ B365853D\ 7598A195\ 1AE273EE\ 5570B6C6\ 8F969834\ 96D4E6D3\ 30D6E582}\\
  & \mathtt{CAB40D66\ 550984EF\ 0C42A457\ 4280B378\ 45189610\ AE3E4BB2\ 2590A08F\ 6AD27BFB}\\
  & \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF}
\end{align*}
The hexadecimal representation of the cofactor $r_{3072} = (p_{3072}-1)/q$ is shown below.
\begin{align*}
  r_{3072}\ = \ \mathtt{0x01}\ 
  & \mathtt{00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 00000000\ 000000BC}\\
  & \mathtt{B17217F7\ D1CF79AB\ C9E3B398\ 03F2F6AF\ 40F34326\ 7298B62D\ 8A0D175B\ 8BAB857A}\\
  & \mathtt{E8F42816\ 5418806C\ 62B0EA36\ 355A3A73\ E0C74198\ 5BF6A0E3\ 130179BF\ 2F0B43E3}\\
  & \mathtt{3AD86292\ 3861B8C9\ F768C416\ 9519600B\ AD06093F\ 964B27E0\ 2D868312\ 31A9160D}\\
  & \mathtt{E48F4DA5\ 3D8AB5E6\ 9E386B69\ 4BEC1AE7\ 22D47579\ 249D5424\ 767C5C33\ B9151E07}\\
  & \mathtt{C5C11D10\ 6AC446D3\ 30B47DB5\ 9D352E47\ A53157DE\ 04461900\ F6FE360D\ B897DF53}\\
  & \mathtt{16D87C94\ AE71DAD0\ BE84B647\ C4BCF818\ C23A2D4E\ BB53C702\ A5C8062D\ 19F5E9B5}\\
  & \mathtt{033A94F7\ FF732F54\ 12971286\ 9D97B8C9\ 6C412921\ A9D86797\ 70F499A0\ 41C297CF}\\
  & \mathtt{F79D4C91\ 49EB6CAF\ 67B9EA3D\ C563D965\ F3AAD137\ 7FF22DE9\ C3E62068\ DD0ED615}\\
  & \mathtt{1C37B4F7\ 4634C2BD\ 09DA912F\ D599F433\ 3A8D2CC0\ 05627DCA\ 37BAD43E\ 64CAF318}\\
  & \mathtt{9FD4A7F5\ 29FD4A7F\ 529FD4A7\ F529FD4A\ 7F529FD4\ A7F529FD\ 4A7F529F\ D4A7F52A}
\end{align*}
And the generator $g_{3072}=2^{r_{3072}} \bmod p_{3072}$ has the following hexadecimal representation.
\begin{align*}
  g_{3072}\ = \ \mathtt{0x}
  & \mathtt{4A1523CB\ 0111B381\ 04EBCDE5\ 163F581E\ EEDD9163\ 7AC57544\ C1D22832\ 34272732}\\
  & \mathtt{FF0CD85F\ 38539544\ 3F573701\ 32A237FF\ 38702AB0\ 37F35E7C\ 7003669D\ 83697BA1}\\
  & \mathtt{3BED69B6\ 3C88BD61\ 0D33C6A8\ 9E4882EE\ 6F849F05\ 06A4A8F0\ B169E5CA\ 000A21DC}\\
  & \mathtt{16D7DCEC\ C69E593C\ 65967739\ 3B6CE260\ D3D6A578\ E74E42A1\ B2ADE1ED\ 8627050C}\\
  & \mathtt{FB59E604\ CAC389E9\ 9161DA6E\ 6E9407DF\ 94517864\ 01003A8B\ 7626AC5E\ 90B888EA}\\
  & \mathtt{BB5E07E9\ 96B18662\ 9B17165F\ D630E139\ 788F674D\ FF4978A6\ B74C6D02\ 0A6570CC}\\
  & \mathtt{7C7A9E38\ 21283571\ BA3FA1FC\ C6901A8C\ 28D02EF8\ B8C4B019\ F7DDADE5\ 1A089C57}\\
  & \mathtt{EF90C2CE\ 50761754\ D778BC9A\ BFD84809\ 5C4A0ED0\ FA7B7AE5\ 2CDA4BD6\ E2CB16F3}\\
  & \mathtt{8EDC033F\ 32F259C5\ 13DD9E0D\ 1F780886\ D71D7DB8\ 35F3F08D\ B11CC9CD\ 41EB0D5A}\\
  & \mathtt{37AC6DBA\ 1A1EBA55\ C378BC06\ 95B9D93A\ A59903EB\ A1CE5288\ 6A0BAAFB\ 15354863}\\
  & \mathtt{1BCEAC52\ 07B97205\ BE8FDF83\ 0F27348C\ 7AE852F9\ F8876887\ D23B8054\ A077DC8A}\\
  & \mathtt{EC0BF615\ A1FA74BC\ 727014CF\ AC40E20E\ A194489F\ 63A6C224\ 27CB999C\ 9D04AA61}
\end{align*}
}

---- S9b
\subsubsection*{Toy parameters for testing purposes only}
The following parameter sets are provided for testing purposes only and must not be used in any real-world scenario. The involved primes are too small to provide any security at all.

\begin{itemize}
\item 7-bit $q$, 16-bit $p$
\begin{align*}
  q & = 127 = \mathtt{0x007F},\\
  p & = 59183 = \mathtt{0xE72F},\\
  r & = 466 = \mathtt{0x01D2},\\
  g & = 32616 = \mathtt{0x7F68}
\end{align*}
\item 16-bit $q$, 32-bit $p$
\begin{align*}
  q & = 65521 = \mathtt{0xFFF1},\\
  p & = 4214179679 = \mathtt{0xFB2B\ 475F},\\
  r & = 64318 = \mathtt{0xFB3E},\\
  g & = 496451214 = \mathtt{0x1D97\ 3E8E}
\end{align*}
\item 16-bit $q$, 48-bit $p$
\begin{align*}
  q & = 65521 = \mathtt{0xFFF1},\\
  p & = 281010572049407 = \mathtt{0xFF93\ DF53\ 3BFF},\\
  r & = 4288862686 = \mathtt{0xFFA2\ D9DE},\\
  g & = 109132885510074 = \mathtt{0x6341\ 7ADF\ C7BA}
\end{align*}
\item 24-bit $q$, 64-bit $p$
\begin{align*}
  q & = 16777213 = \mathtt{0xFFFFFFFD},\\
  p & = 18444843247520538623 = \mathtt{0xFFF93F35\ 6A395FFF},\\
  r & = 1099398526294 = \mathtt{0x000000FF\ F9423556},\\
  g & = 14757355607624201864 = \mathtt{0xCCCCA8BC\ C08F3688}
\end{align*}
\item 32-bit $q$, 96-bit $p$
\begin{align*}
  q & = 4294967291 = \mathtt{0xFFFFFFFB},\\
  p & = 79227651399410325621583970303\\
    & = \mathtt{0xFFFF93C4\ 6882B6AA\ F57CFFFF},\\
  r & = 18446625091983808922\\
    & = \mathtt{0xFFFF93C9\ 6880999A},\\
  g & = 60786014689883675535506158858\\ 
    & = \mathtt{0xC469034B\ 2CE5EC6E\ 1970350A}
\end{align*}
\item 32-bit $q$, 128-bit $p$
\begin{align*}
  q & = 4294967291 = \mathtt{0xFFFFFFFB},\\
  p & = 340282366887442052436576802921059975167\\
    & = \mathtt{0xFFFFFFFF\ 93C46B0F\ B6C381D8\ FFFFFFFF},\\
  r & = 79228162598699067120922761626\\
    & = \mathtt{0x00000001\ 00000004\ 93C46B26\ 9999999A},\\
  g & = 55628101181055236817878380639043675517\\
    & = \mathtt{0x29D99524\ 0DFB12B3\ 6FD0F8CC E06B657D}
\end{align*}
\item 48-bit $q$, 192-bit $p$
\begin{align*}
  q & = \mathtt{0x0000FFFF\ FFFFFFC5},\\
  p & = \mathtt{0xFFFFFFFF\ FFFFFFFF\ 9ECB7796\ 49D9A82D\ FFFFFFFF\ FFFFFFFF},\\
  r & = \mathtt{0x00010000\ 0000003A\ FFFF9ECB\ 852F49C3\ 4115B1E6},\\
  g & = \mathtt{0x0B5DA090\ 0B367E3C\ 92A11019\ 54DB5E3C\ 873E929A\ 0E324F00}
\end{align*}
\item 64-bit $q$, 256-bit $p$
\begin{align*}
  q & = \mathtt{0xFFFFFFFF\ FFFFFFC5},\\
  p & = \mathtt{0xFFFFFFFF\ FFFFFFFF\ 93C467E3\ 7DB1212B\ 89995855\ 493FF059\ FFFFFFFF\ FFFFFFFF},\\
  r & = \mathtt{0x00000001\ 00000000\ 0000003A\ 93C467E3\ 7DB12EAB\ 97DD49C3\ 4115B1E6},\\
  g & = \mathtt{0x3B543166\ 9E3E4893\ DF745C67\ CDCFD95C\ CDDA2248\ 78A3CD5D\ 3226F75C\ C5A95638}
\end{align*}
\end{itemize}

\pagebreak

-------- Section "10" Glossary of typical variable usage

\section*{Glossary of typical variable usage}

{\centering
}

{\centering
}