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.
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.
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.
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.
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.
c[m,r] = g^m * r^n mod n2,
m = L( c[m,r]^s mod n2 ) / L( g^s mod n2 ) mod n, where L(x) = (x-1) / n,
There are φ(n) = (p-1)(q-1) distinct generators g = αn + 1, with φ(n) being Euler's totient function.
A plaintext message m must lie in the range 0...n-1.
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.
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.
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.
Choose two secret primes p and q from which the public modulus n = pq is computed.
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.
A non-interactive ZK proof can be obtained using the Fiat-Shamir heuristic.
© 2008-2009 by Andreas Steffen, HSR Hochschule fuer Technik Rapperswil