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