  # E-Voting Glossary

## ElGamal Cryptosystem

• ### ElGamal E-Voting Simulator

This interactive simulator demonstrates the principle of secret sharing and threshold decryption among multiple voting authorities. In our example five authorities contribute shares to the ElGamal public voting key and at least three authorities are required to be able to jointly decrypt the final tally.

The simulation example also shows the homomorphic property of the ElGamal cryptosystem. Multiplication of the encrypted ballots results in the encrypted tally thus guaranteeing anonymity and privacy. Unfortunately the multiplicative property of the homomorphism makes the mapping of the decrypted tally to the actual outcome even of a simple yes/no vote a non-trivial operation requiring a search over part of the generator space.

Zero-knowledge proofs establish the correctness of the ElGamla public key shares and the partial decryptions of the tally done by the voting authorities as well as the validity of the individual encrypted ballots.

• ### ElGamal Public Key

h = g^s mod p

with s being the private ElGamal key randomly selected from the range 0..q-1 and the modulus p being a prime of the form

p = 2q + 1

where q is also a prime.

• ### ElGamal Encryption

c[m,r] = ( x[r], y[m,r] ) = ( g^r, m * h^r ) mod p

with ciphertext c consisting of two components x and y, generator g, plaintext message m, random value r guaranteeing semantic security, and ElGamal public key h.

• ### ElGamal Decryption

m = y[m,r] / x[r]^s mod p = m * (g^s)^r / (g^r)^s = m * g^sr / g^rs

with plaintext m, ciphertext components x and y, and ElGamal private key s.

## Paillier Cryptosystem

• ### Paillier E-Voting Simulator

This interactive simulator demonstrates the homomorphic property of the Paillier cryptosystem. Addition of the encrypted ballots directly results in the encrypted tally, so that the final outcome of a poll is immediately available after the Paillier decryption.

The simulation example also shows how a simple election with a small number of candidates can be realized by assigning a fixed bit range for each candidate in the tally. A zero-knowledge proof establishes the validity of the encrypted ballots with a high probability.

• ### Paillier Encryption

c[m,r] = g^m * r^n mod n2,

with ciphertext c, generator g, plaintext message m, random value r guaranteeing semantic security, and RSA modulus n.

• ### Paillier Decryption

m = L( c[m,r]^s mod n2 ) / L( g^s mod n2 ) mod n,   where L(x) = (x-1) / n,

with plaintext message m, ciphertext c, private key s, generator g, and RSA modulus n.

• ### Paillier Generator

There are φ(n) = (p-1)(q-1) distinct generators g = αn + 1, with φ(n) being Euler's totient function.

• ### Paillier Message

A plaintext message m must lie in the range 0...n-1.

• ### Paillier Message Base

A voting message m is constructed with a base b as m = c1 + c2*b + c3*b^2 where c1, c2, and c3 are the number of votes for candidates 1, 2, and 3, respectively. The number of votes per candidate must not exceed b-1. Otherwise an overflow would occur.

• ### Paillier Private Key

s = λ(n) = lcm(p-1,q-1),

with λ(n) being the Carmichael function that cannot be computed without the knowledge of the RSA prime factors p and q.

## Random Number

• ### Random Seed

Both the ElGamal and Paillier cryptosystems require random numbers to achieve semantic security and zero-knowledge proofs need random challenges. In order to obtain repeatable results, our simulations use a pseudo random number generator initialized by a random seed.

## RSA Cryptosystem

• ### RSA Modulus

Choose two secret primes p and q from which the public modulus n = pq is computed.

## Zero-Knowledge Proof

• ### Interactive Proof

An interactive ZK proof usually consists of three moves:

1. P --> V: The prover sends a commitment to the verifier.
2. V <-- P: The verifier sends a random challenge to the prover.
3. P --> V: The prover sends a response to the verifier.

• ### Non-Interactive Proof

A non-interactive ZK proof can be obtained using the Fiat-Shamir heuristic.

© 2008-2009 by Andreas Steffen, HSR Hochschule fuer Technik Rapperswil