Cryptographic Workflow

Voting Process and Cryptographic Maths

When an administrative user "freezes" an election (i.e. when the election configurations e.g. start and end dates etc. are set and become immutable), a key pair for the El Gamal algorithm is generated. This key pair consists of:

a public key with values
- p - a large prime number (2048 bits or more) that defines the group
- q - prime number that divides (p-1), often chosen as q = (p-1)/2
- g - generator of the multiplicative group modulo p
- y - public key with y = g^x mod p
and a secret key x, randomly chosen such that 1 < x < p.

El Gamal encryption

Encryption starts when the voter confirms their choices and before any information is sealed and sent to the server. The voter expresses their choices by encrypting 1 or 0 for each option, depending on whether they want to support that option or not. With the plaintext m (expected as a big integer) and a randomness r < q a ciphertext (alpha, beta) is generated for each option as follows:

alpha = g^r mod p
beta = m * y^r mod p.

The value of m is actually never 0, which would be not cryptographically secure. Instead, 0 and 1 are actually encoded as Enc(0) = g^0 and Enc(1) = g^1, which are two elements of the group generated by g, as needed for El Gamal encryption. It is called "exponential El Gamal" and makes ciphertexts additively homomorphic, i.e. the product of an encryption of g^i and an encryption of g^j is an encryption of g^(i+j).

At this point, an audit option is available to the voter. If this was done, the ciphertexts and the randomness used to create them are displayed, so the voter can verify, if the ballot system had encrypted the answers correctly. Then, the revealed randomness and its ciphertexts are discarded and a new randomness r < q is chosen to generate a new ciphertext (alpha, beta) for each option - like before.

Proof of correct encryption

Next, a disjunctive zero-knowledge proof is performed. Its core idea is the creation of multiple parallel proofs. There is one real proof for the actual vote cast (Enc(1)), and there is one simulated proof for each option that was not chosen by the voter (Enc(0)). These proofs are indistinguishable from each other by a verifier, but together they show:

In an election with multiple options, exactly one option was selected, without revealing which one.

Therefore, at first for the ciphertext (alpha, beta) of each unchosen option m an encryption proof is simulated as follows:

challenge - randomly chosen number with challenge < q
response - randomly chosen number with response < q
commitment = ( alpha^(-challenge) * g^response mod p, (beta / m)^(-challenge) * y^response mod p ).

Then, using a random value w < q, the real proof for the actual vote cast is calculated as follows:

commitment = ( g^w mod p, y^w mod p )
challenge - hash value over a list of all (simulated and real) commitments, reduced by subtracting all simulated challenges, modulo q
response = w + randomness * challenge mod q.

The value of randomness has to be the randomness r that was used in the previous section to create the ciphertexts with El Gamal algorithm. In the end, every plaintext and randomness is now discarded.

Only the list of ciphertexts [(alpha_1, beta_1), (alpha_2, beta_2), ..., (alpha_n, beta_n)] and the corresponding list of their proofs [proof_1, proof_2, ..., proof_n] are left and sent to the server side.

Verification of encryption proof

On the server side, at first it is checked if the incoming proofs are valid. Therefore, the following statements have to be true for every ciphertext (alpha, beta) and its proof {commitment, challenge, response}, with commitment consisting of (A, B):

A^q = 1 mod p and B^q = 1 mod p (A and B in the correct group)
g^response = A * alpha^challenge
y^response = B * (beta/m)^challenge.

Note that the plaintext m does not need to be decrypted from its ciphertext (alpha, beta). The server already knows every possible option the voter can chose (Enc(0) or Enc(1)). With one of these possible options the last statement must hold.

If all statements above hold for every ciphertext and its proof, then all the ciphertexts will be placed in the "ballot box".

Generalization for multi-section elections

The encryption and proof mechanisms described above can be generalized to support elections that consist of multiple sections, where each section allows for the selection of more than one option - up to a predefined maximum number of votes per section.

To ensure that the encryption remains verifiable and the zero-knowledge proofs applicable, a fixed number of ciphertexts is always generated per section. For each section, the number of encrypted values is equal to the maximum number allowed in that section. This holds regardless of how many options the voter actually selects.

For example, if a selection allows up to 3 selections, then exactly 3 votes will be encrypted and processed, whether the voter selects 0, 1, 2 or 3 options. The same applies independently to each section of the election.

In order to preserve the semantic meaning of the encrypted votes and allow for consistent proof generation, two implicit options are introduced:

An implicit no option-choice, which absorbs any unused votes if the voter selects fewer than the maximum allowed number of options.
An implicit invalid-choice, which replaces all actual votes in the case where the voter's input is flagged as invalid through client-side validation and the voter confirms submission regardless (see following section).

Each of these encrypted votes - whether for a selected option or one of the implicit options - is accompanied by a disjunctive zero-knowledge proof as described in the proof of correct encryption-section earlier. This ensures that, for each section, the encrypted ballots contain exactly the allowed number of selections, without revealing which options were chosen or how many valid selections were made.

This generalization maintains the privacy, integrity, and verifiability guarantees of the voting process, even in complex multi-section elections with variable numbers of allowable votes.

Client- and server-side ballot validation

Before encryption begins, the voting client performs a complete validation of the voter's selections against all election rules defined in the configurations. These rules include, but are not limited to, a maximum number of votes per candidate or a maximum number of votes per sections. If any violations are detected - such as selecting too many options - the client alerts the voter with a corresponding message.

The voter may then correct the input or, after acknowledging the warning, choose to submit the ballot as invalid. In this case, as described in the previous section, all votes on the ballot are replaced by encryptions of the implicit invalid-option. This approach ensures that even invalid ballots remains structurally consistent and provably formed, while being semantically marked as invalid.

After submission, the server independently revalidates all election constraints. This step is necessary, as neither the integrity of the client nor the communication channel can be fully guaranteed.

To verify that the ballot complies with all configured constraints, the server performs a homomorphic tallying of the encrypted votes (see following section). This enables detection of any violations of configured limits across sections, without decrypting individual votes. Additionally, the server verifies that the implicit invalid-option appears in one of the following two consistent patterns:

Either all encrypted votes are for the invalid-option (in case of a consciously submitted invalid ballot), or
none of the encrypted votes are for the invalid-option (in case od a valid submission).

Any deviation from these expectations, or failure of the accompanying zero-knowledge proofs, leads to rejection of the ballot. In this case, the voter is informed that the submitted ballot appears to be corrupted or malformed and has therefore been rejected. The voter is then offered the opportunity to complete and submit a new ballot.

This two-layered validation - first client-side, then independently server-side - ensures the integrity of the election process even in the presence of unreliable or potentially compromised environments.

Homomorphic vote tallying

When the election is over and closed, the tallying phase begins. At this point, it would be possible to shuffle all ciphertexts, decrypt them individually, and then count the votes - all accompanied by cryptographic proofs. In this case, however, the homomorphic property of the El Gamal encryption scheme is utilized. Instead of decrypting each individual ciphertext, all ciphertexts are multiplicatively combined.

Recap: The proof of correct encryption (see earlier section) showed for every voter that in an election with multiple options, exactly one option was selected, without revealing which one.

Now, in the "ballot box" there is a set of encrypted votes with each vote consisting of a list of ciphertexts [(alpha_1, beta_1), (alpha_2, beta_2), ..., (alpha_n, beta_n)] and each of these n ciphertexts containing the information whether or not the voter selected the corresponding option (Enc(1) or Enc(0)). With this in mind, for each ciphertext (alpha_i, beta_i) of all votes:

alpha = Product(alpha_i) mod p (product of all alpha_i of all votes)
beta = Product(beta_i) mod p (product of all beta_i of all votes).

The resulting ciphertext (alpha, beta) now contains the encrypted sum of votes for option i. Any information about each voter's selection is thus lost. Instead, there are only n ciphertexts left, each containing the encrypted sum of votes for the corresponding option.

Public verifiability

Before decryption takes place, public verifiability ensures that the set of encrypted votes used in the homomorphic tally is complete and unmodified. This includes two main components:

Individual verifiability: Each voter can verify that their encrypted vote was correctly included in the published set of ciphertexts, typically by checking a cryptographic hash or commitment computed over their submitted vote. These values are published on a public bulletin board or audit trail. If the commitment matches, the vote has not been altered or omitted.
Universal verifiability: All parties can verify that the homomorphic aggregation of the encrypted votes was performed correctly. Since all encrypted votes and their zero-knowledge proofs are public, anyone can independently recompute the aggregate ciphertexts for each option and verify that the combined results match the published tally ciphertexts.

This step does not reveal any vote content, but it guarantees that only valid, correctly encrypted votes were included in the tally and that the homomorphic computations were performed without manipulation. It is skipped if it was deselected in the election configuration.

Decryption

Recap: After the homomorphic vote tallying (see earlier section), there are only n ciphertexts left, each containing the encrypted sum of votes for the corresponding option.

To decrypt a ciphertext (alpha, beta), a decryption factor is computed as follows:

dec_factor = alpha^x = g^(y*x) mod p.

Then, the modular inverse of this factor is computed with dec_factor^(-1) mod p, before finally the plaintext m is recovered as follows:

m = beta * dec_factor^(-1) mod p.

With this, all n ciphertexts are decrypted and the election results can be published.

Proof of Decryption

The proof of decryption follows the Chaum-Pedersen protocol and is used to verify the correctness of the El Gamal decryption, without revealing the secret key x or randomness r used in the encryption process.

Therefore, the server needs to prove that it knows x such that:

y = g^x mod p
alpha^x = d = g^(xr).

This is a zero-knowledge proof of equality of discrete logs.

With a ciphertext (alpha, beta) and a random value w < q, the proof is calculated as follows:

commitment = ( g^w mod p, alpha^w mod p )
challenge - hash value over the commitment (Fiat-Shamir hash)
response = w + challenge * x mod q.

Verification of decryption proof

To verify the proof of decryption the following statements have to be true for the ciphertext (alpha, beta), its decryption m and the above proof {commitment, challenge, response}, with commitment consisting of (A, B):

g^response = A * y^challenge
alpha^response = B * (beta/m)^challenge.

If both equations hold the verifier can be convinced that the prover knows the secret x. Hence, the decryption is correct.