Paillier Cryptosystem

RSA Factors: p = q =

Voter Candidates Cheat
V1 None C1 C2 C3
V2 None C1 C2 C3
V3 None C1 C2 C3
V4 None C1 C2 C3
V5 None C1 C2 C3
V6 None C1 C2 C3
V7 None C1 C2 C3
V8 None C1 C2 C3
Tally 1 1 3 1 2
Hide details of:
Paillier Encryption / Decryption
Zero-Knowledge Proof
 
Generator g:
α fixed to 1
β fixed to 1
 
Message Base
Random Seed


p = 3, q = 11, n = pq = 33, n2 = 1089, φ(n) = (p-1)(q-1) = 20, λ(n) = lcm(p-1,q-1) = 10

Valid Voting Messages:     m = mi, None: m0 = 0, C1: m1 = 1, C2: m2 = b = 4, C3: m3 = b^2 = 16

Paillier Encryption:       c[m,r] = g^m * r^n mod n2, with generator g = (αn + 1)*β^n mod n2 = 911  (α = 1, β = 26)

               0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32  m
               1  911  103  179  808 1013  460  884  553  665  331  977  334  443  643  980  889  752   91  137  661 1043  565  707  478  947  229  620  718  698  991   20  796  g^m

   1    1      1  911  103  179  808 1013  460  884  553  665  331  977  334  443  643  980  889  752   91  137  661 1043  565  707  478  947  229  620  718  698  991   20  796
   2  602    602  655 1022 1036  722 1075  314  736  761  667 1064   94  692  970  491  811  479  769  332  799  437  622  362  904  260  547  644  802  992  931  899   61   32
   4  856    856   92 1048  764  133  284  631  938  742  782  196 1049  586  236  463  350  862  113  577  749  625  917  124  797  793  416    4  377  412  716 1054  785  751
   5  323    323  223  599  100  713  499  476  214   23  262  191  850   71  430  779  730  740   49 1079  691   59  388  632  760  845  961 1004  973 1046   31 1016 1015  104
   7  838    838   29  283  809  835  563 1063  272  589  791  772  887   19  974  868  134  106  734   28  461  706  656  844   50  901  794  238  107  556  131  640  425  580
   8  215    215  934  365  370  569 1084  890  574  194  316  380  967 1025  502 1031  523  560  508 1052   52  545 1000  596  634  404 1051  230  442  821  877  710 1033  167
  10  604    604  299  139  305  160  923  145  326  778  908  637  959  271  767  688  593   79   95  514 1073  670  530  403  140  127  263   13  953  250  149  703  101  535
  13  118    118  776  175  431  601  833  919  857 1003   62  943  941  208    2  733  206  358  527  937  920  679   17  241  662  865  668  886  197  871  689  415  182  274
  14  269    269   34  482  235  641  247  683  394  653  289  830  364  548  466  905   82  650  823  521  916  302  694  614  697   80 1006  617  163  389  454  863 1024  680
  16  928    928  344  841  584  592  257 1081  335  265  746   70  608  676  551 1021  125  619  896  595  812  301  872  511  518  361 1082  157  368  925  878  532   47  346
  17  161    161  745  248  505  497  832    8  754  824  343 1019  481  413  538   68  964  470  193  494  277  788  217  578  571  728    7  932  721  164  211  557 1042  743
  19  820    820 1055  607  854  448  842  406  695  436  800  259  725  541  623  184 1007  439  266  568  173  787  395  475  392 1009   83  472  926  700  635  226   65  409
  20  971    971  313  914  658  488  256  170  232   86 1027  146  148  881 1087  356  883  731  562  152  169  410 1072  848  427  224  421  203  892  218  400  674  907  815
  23  485    485  790  950  784  929  166  944  763  311  181  452  130  818  322  401  496 1010  994  575   16  419  559  686  949  962  826 1076  136  839  940  386  988  554
  25  874    874  155  724  719  520    5  199  515  895  773  709  122   64  587   58  566  529  581   37 1037  544   89  493  455  685   38  859  647  268  212  379   56  922
  26  251    251 1060  806  280  254  526   26  817  500  298  317  202 1070  115  221  955  983  355 1061  628  383  433  245 1039  188  295  851  982  533  958  449  664  509
  28  766    766  866  490  989  376  590  613  875 1066  827  898  239 1018  659  310  359  349 1040   10  398 1030  701  457  329  244  128   85  116   43 1058   73   74  985
  29  233    233  997   41  325  956  805  458  151  347  307  893   40  503  853  626  739  227  976  512  340  464  172  965  292  296  673 1085  712  677  373   35  304  338
  31  487    487  434   67   53  367   14  775  353  328  422   25  995  397  119  598  278  610  320  757  290  652  467  727  185  829  542  445  287   97  158  190 1028 1057
  32 1088   1088  178  986  910  281   76  629  205  536  424  758  112  755  646  446  109  200  337  998  952  428   46  524  382  611  142  860  469  371  391   98 1069  293
   r  r^n

Paillier Decryption I:    c[m,r]^s mod n2, with s = λ(n) = 10

   1           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   2           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   4           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   5           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   7           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   8           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  10           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  13           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  14           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  16           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  17           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  19           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  20           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  23           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  25           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  26           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  28           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  29           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  31           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
  32           1  331  661  991  232  562  892  133  463  793   34  364  694 1024  265  595  925  166  496  826   67  397  727 1057  298  628  958  199  529  859  100  430  760
   r

Paillier Decryption II:   L(c[m,r]^s mod n2), with L(x) = (x-1)/n

  any r        0   10   20   30    7   17   27    4   14   24    1   11   21   31    8   18   28    5   15   25    2   12   22   32    9   19   29    6   16   26    3   13   23

Paillier Decryption III:  L(c[m,r]^s mod n2) * μ mod n, with μ = 1/L(g^s mod n2) mod n = 10

  any r        0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32

Validity Proof of Ballot:      uk = c[m,r]/g^mk mod n2 must be an n-th power for k == i

P:        (k == i)         ω
P --> V:                   ai = ω^n mod n2
P:        (k != i)         zk, ek < 2^1
P --> V:                   ak = zk^n / uk^ek mod n2
V --> P:                   es < 2^1
P --> V:  (k == i)         ei = es - Σ(ek) mod 2, for all k != i
P --> V:                   zi = ω * r^ei mod n
P --> V:  (k != i)         ek
P --> V:                   zk
V:                         Σ(ek) == es mod 2
V:                         zk^n == ak * uk^ek mod n2

Voting and Tallying:       t = Π(c[m,r]) mod n2
  
Voter m r c u0 u1 u2 u3 a0 a1 a2 a3 es e0 e1 e2 e3 ω z0 z1 z2 z3 z0^n z1^n z2^n z3^n t tm C1 C2 C3
V1 1 10 299 299 604 557 494 743 604 233 980 0 1 0 0 1 10 1 10 29 10 1 604 233 604 299 1 1 0 0
V2 4 23 929 929 784 485 872 269 899 820 118 1 0 1 0 0 19 14 29 19 13 269 233 820 118 76 5 1 1 0
V3 4 19 448 448 854 820 172 604 161 838 251 0 0 0 0 0 7 10 17 7 26 604 161 838 251 289 9 1 2 0
V4 32 19 409 409 65 700 439 911 806 269 269 1 1 1 0 1 14 17 13 14 2 161 118 269 602 289 9 1 2 0
V5 4 14 641 641 235 269 917 928 703 215 766 0 0 1 1 0 8 16 28 13 28 928 766 118 766 119 13 1 3 0
V6 16 5 740 740 730 71 323 233 1088 838 766 0 0 0 0 0 28 29 32 7 28 233 1088 838 766 940 29 1 3 1
V7 2 14 482 482 34 785 749 785 766 604 604 0 1 1 0 0 28 31 29 10 10 487 233 604 604 940 29 1 3 1
V8 0 8 215 215 580 131 734 856 1060 367 161 0 0 1 1 0 4 4 10 17 17 856 604 161 161 635 29 1 3 1

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


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