ElGamal Cryptosystem

Prime q =

Voter Vote Cheat
V1 Yes No
V2 Yes No
V3 Yes No
V4 Yes No
V5 Yes No
V6 Yes No
V7 Yes No
V8 Yes No
Tally 4 2 2
Hide details of:
Subgroup Members
Zero-Knowledge Proof
 
Random Seed

k = 2, q = 23, p = kq + 1 = 47

Subgroup of order q:   generated by g = 2

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  i
   1   2   4   8  16  32  17  34  21  42  37  27   7  14  28   9  18  36  25   3   6  12  24   1  g^i

Secret Sharing:          s(x) = a0 + a1*x +a2*x^2 mod q = Σ si(x), with N = 5 authorities and threshold T = 3

Public Values:           h(x) = g^s(x) mod p = h0 * h1^x * h2^(x^2) mod p, with h0 = g^a0, h1 = g^a1, and h2 = g^a2

Verification of Shares:  g^s(i) mod p == h(i)
  
i  a0  a1  a2  h0  h1  h2 s(1) s(2) s(3) s(4) s(5) h(1) h(2) h(3) h(4) h(5)
A1 16 7 20 18 34 6 20 18 10 19 22   25 37 3 24
A2 11 22 19 27 24 3 6 16 18 12 21 17   25 7 12
A3 13 11 9 14 27 42 10 2 12 17 17 37 4   36 36
A4 17 10 13 36 37 14 17 20 3 12 1 36 6 8   2
A5 7 14 14 34 28 28 12 22 14 11 13 7 24 28 27  
  Σ     Π Π Π Σ Σ Σ Σ Σ  
s= 18   h= 25 25 17 19 9 11 2 5 3 42 27 4 32
 
Langrange Interpolation: s = s(0) = Σ s(i) *λi
 
Authorities λ1 λ2 λ3 λ4 λ5 s  
A1 & A2 & A3 3 20 1     18
A3 & A4 & A5     10 8 6 18
A1 & A2 & A4 & A5 11 12   17 7 18
A1 & A2 & A3 & A4 & A5 5 13 10 18 1 18
 
Messages: yes:  m1 = 8;   no:   m0 = 1/m1 mod p = 6
 
ElGamal Encrypted Ballot: x[r] = g^r mod p,   y[m,r] = m * h^r mod p
 
Validity Proof of Ballot: log[g] x == log[h] (y/m)   with m = m0|m1
 
P: (m = m1) ω, r1, d1
P --> V: a1 = g^r1 * x^d1   mod p
P --> V: b1 = h^r1 * (y/m0)^d1   mod p
P --> V: a2 = g^ω   mod p
P --> V: b2 = h^ω   mod p
P: (m = m0) ω, r2, d2
P --> V: a1 = g^ω   mod p
P --> V: b1 = h^ω   mod p
P --> V: a2 = g^r2 * x^d2   mod p
P --> V: b2 = h^r2 * (y/m1)^d2   mod p
V --> P: c
P --> V: (m = m1) d1
P --> V: d2 = c - d1   mod q
P --> V: r1
P --> V: r2 = &omega - r * d2   mod q
P --> V: (m = m0) d1 = c - d2   mod q
P --> V: d2
P --> V: r1 = &omega - r * d1   mod q
P --> V: r2
V: c == d1 + d2   mod q
V: a1 == g^r1 * x^d1   mod p
V: b1 == h^r1 * (y/m0)^d1   mod p
V: a2 == g^r2 * x^d2   mod p
V: b2 == h^r2 * (y/m1)^d2   mod p
 
Voting and Tallying: tx = Π(x[r]),   ty = Π(y[m,r])
 
Voter m r x y a1 b1 a2 b2 c d1 d2 r1 r2 tx ty  
V1 8 19 3 1 37 28 18 7 1 3 21 22 8 3 1  
V2 6 21 12 34 14 16 32 27 15 21 17 9 16 36 34  
V3 8 17 36 37 12 42 14 16 1 19 5 20 20 27 36  
V4 17 20 6 12 18 18 34 27 14 3 11 2 17 27 36  
V5 8 3 8 27 1 24 2 25 12 19 16 12 22 28 32  
V6 6 19 3 36 27 28 8 14 20 17 3 10 15 37 24  
V7 27 7 34 24 7 42 12 7 17 11 6 4 2 37 24  
V8 8 14 28 4 12 24 28 24 18 2 16 16 20 2 2  
 
Partial Decryption of Tally: ωi = tx^s(i) mod p
 
  tx ty ω1 ω2 ω3 ω4 ω5  
  2 2 3 42 27 4 32
 
Zero-Knowledge Proof: s(i) = log[g] h(i) == log[tx] ωi
 
P: α 1 4 20 1 11  
P --> V: a = g^α mod p 2 16 6 2 27  
P --> V: b = tx^α mod p 2 16 6 2 27  
P <-- V: c 21 1 16 12 1  
P --> V: r = α + c*s(i) mod q 9 13 12 2 16  
V: g^r  == a * h(i)^c mod p 42 14 7 4 18  
V: tx^r == b * ωi^c mod p 42 14 7 4 18  
 
Interpolation of Tally: tx^s = Π(ωi^λi) mod p
 
Decryption of Tally Message: tm = ty / tx^s mod p
 
Authorities λ1 λ2 λ3 λ4 λ5 tx^s tm
A1 & A2 & A3 3 20 1     25 17
A3 & A4 & A5     10 8 6 25 17
A1 & A2 & A4 & A5 11 12   17 7 25 17
A1 & A2 & A3 & A4 & A5 5 13 10 18 1 25 17

Discrete Logarithm of Decrypted Tally Message via Linear Search:

 0  1  2  3  4  5  6  7  8 i
1 8 17 42 7 9 25 12 2 m1^i
1 6 36 28 27 21 32 4 24 m0^i

Result:   2 more yes than no votes!

The source code of the simulator is available under a GPLv2 license.


© 2008-2009 by Andreas Steffen, HSR Hochschule für Technik Rapperswil