1040:
789:
404:
23:(or AV-net) is a multi-party secure computation protocol to compute the boolean-OR function. It was first proposed by Feng Hao and Piotr Zieliński in 2006. This protocol presents an efficient solution to the
213:
721:
784:
664:
1035:{\displaystyle \scriptstyle x_{1}\cdot y_{1}\,+\,x_{1}\cdot y_{2}\,+\,x_{3}\cdot y_{3}\;=\;x_{1}\cdot (-x_{2}\,-\,x_{3})\,+\,x_{2}\cdot (x_{1}\,-\,x_{3})\,+\,x_{3}\cdot (x_{1}\,+\,x_{2})\;=\;0}
607:
555:
478:
249:
511:
282:
432:
160:
132:
106:
84:
62:
301:
1106:
165:
1101:
669:
734:
731:
The protocol is designed by combining random public keys in such a structured way to achieve a vanishing effect. In this case,
612:
1047:
24:
563:
516:
437:
218:
487:
258:
481:
252:
415:
143:
115:
89:
67:
45:
557:
if they want to send a "0" bit (no veto), or a random value if they want to send a "1" bit (veto).
31:
285:
1066:
1095:
109:
1084:
The Dining
Cryptographers Problem: Unconditional Sender and Recipient Untraceability
1043:
289:
1042:. A similar idea, though in a non-public-key context, can be traced back to
399:{\displaystyle g^{y_{i}}=\prod _{j<i}g^{x_{j}}/\prod _{j>i}g^{x_{j}}}
1083:
666:. On the other hand, if one or more participants vetoed, each will have
30:
A related protocol that securely computes a boolean-count function is
1071:
Proceedings of the 14th
International Workshop on Security Protocols
284:. A detailed description of a method for such proofs is found in
108:
in which the discrete logarithm problem is hard. For example, a
208:{\displaystyle \scriptstyle x_{i}\,\in _{R}\,\mathbb {Z} _{q}}
716:{\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;\neq \;1}
779:{\displaystyle \scriptstyle \sum {x_{i}\cdot y_{i}}\;=\;0}
659:{\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;=\;1}
1086:
Journal of
Cryptology, vol. 1, No, 1, pp. 65-75, 1988
793:
738:
673:
616:
567:
520:
491:
441:
419:
262:
222:
169:
147:
119:
93:
71:
49:
792:
786:. For example, if there are three participants, then
737:
672:
615:
566:
519:
490:
440:
418:
304:
261:
221:
168:
146:
118:
92:
70:
48:
134:participants, the protocol executes in two rounds.
1034:
778:
715:
658:
601:
549:
505:
472:
426:
398:
276:
243:
207:
154:
126:
100:
78:
56:
602:{\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}}
295:After this round, each participant computes:
8:
550:{\displaystyle \scriptstyle c_{i}\;=\;x_{i}}
473:{\displaystyle \scriptstyle g^{c_{i}y_{i}}}
1027:
1023:
877:
873:
771:
767:
708:
704:
651:
647:
535:
531:
1014:
1009:
1005:
999:
983:
978:
974:
965:
960:
956:
950:
934:
929:
925:
916:
911:
907:
901:
882:
867:
854:
849:
845:
839:
826:
821:
817:
811:
798:
791:
760:
747:
742:
736:
696:
686:
681:
671:
639:
629:
624:
614:
590:
580:
575:
565:
560:After round 2, each participant computes
540:
525:
518:
496:
489:
461:
451:
446:
439:
417:
388:
383:
367:
358:
350:
345:
329:
314:
309:
303:
267:
260:
232:
227:
220:
198:
194:
193:
191:
185:
180:
174:
167:
145:
117:
91:
69:
47:
1058:
215:and publishes the ephemeral public key
16:Multi-party secure computation protocol
244:{\displaystyle \scriptstyle g^{x_{i}}}
609:. If no one vetoed, each will obtain
7:
506:{\displaystyle \scriptstyle c_{i}}
277:{\displaystyle \scriptstyle x_{i}}
42:All participants agree on a group
14:
1067:A 2-round anonymous veto protocol
513:. Here, the participants chose
1020:
992:
971:
943:
922:
891:
484:for the proof of the exponent
427:{\displaystyle \scriptstyle i}
255:for the proof of the exponent
155:{\displaystyle \scriptstyle i}
127:{\displaystyle \scriptstyle n}
101:{\displaystyle \scriptstyle q}
79:{\displaystyle \scriptstyle g}
57:{\displaystyle \scriptstyle G}
1:
1048:Dining cryptographers problem
112:can be used. For a group of
25:Dining cryptographers problem
1046:'s original solution to the
1123:
1107:Zero-knowledge protocols
1102:Public-key cryptography
162:selects a random value
1065:F. Hao, P. Zieliński.
1036:
780:
717:
660:
603:
551:
507:
474:
428:
400:
278:
245:
209:
156:
128:
102:
80:
58:
21:anonymous veto network
1037:
781:
718:
661:
604:
552:
508:
475:
429:
401:
279:
246:
210:
157:
129:
103:
81:
59:
19:In cryptography, the
790:
735:
670:
613:
564:
517:
488:
482:zero-knowledge proof
438:
416:
302:
259:
253:zero-knowledge proof
219:
166:
144:
116:
90:
68:
46:
727:The protocol design
412:: each participant
140:: each participant
1032:
1031:
776:
775:
713:
712:
656:
655:
599:
598:
547:
546:
503:
502:
470:
469:
424:
423:
396:
378:
340:
274:
273:
241:
240:
205:
204:
152:
151:
124:
123:
98:
97:
76:
75:
54:
53:
363:
325:
64:with a generator
32:open vote network
1114:
1087:
1080:
1074:
1063:
1041:
1039:
1038:
1033:
1019:
1018:
1004:
1003:
988:
987:
970:
969:
955:
954:
939:
938:
921:
920:
906:
905:
887:
886:
872:
871:
859:
858:
844:
843:
831:
830:
816:
815:
803:
802:
785:
783:
782:
777:
766:
765:
764:
752:
751:
722:
720:
719:
714:
703:
702:
701:
700:
691:
690:
665:
663:
662:
657:
646:
645:
644:
643:
634:
633:
608:
606:
605:
600:
597:
596:
595:
594:
585:
584:
556:
554:
553:
548:
545:
544:
530:
529:
512:
510:
509:
504:
501:
500:
479:
477:
476:
471:
468:
467:
466:
465:
456:
455:
433:
431:
430:
425:
405:
403:
402:
397:
395:
394:
393:
392:
377:
362:
357:
356:
355:
354:
339:
321:
320:
319:
318:
283:
281:
280:
275:
272:
271:
251:together with a
250:
248:
247:
242:
239:
238:
237:
236:
214:
212:
211:
206:
203:
202:
197:
190:
189:
179:
178:
161:
159:
158:
153:
133:
131:
130:
125:
107:
105:
104:
99:
85:
83:
82:
77:
63:
61:
60:
55:
1122:
1121:
1117:
1116:
1115:
1113:
1112:
1111:
1092:
1091:
1090:
1081:
1077:
1064:
1060:
1056:
1010:
995:
979:
961:
946:
930:
912:
897:
878:
863:
850:
835:
822:
807:
794:
788:
787:
756:
743:
733:
732:
729:
692:
682:
677:
668:
667:
635:
625:
620:
611:
610:
586:
576:
571:
562:
561:
536:
521:
515:
514:
492:
486:
485:
457:
447:
442:
436:
435:
414:
413:
384:
379:
346:
341:
310:
305:
300:
299:
263:
257:
256:
228:
223:
217:
216:
192:
181:
170:
164:
163:
142:
141:
114:
113:
88:
87:
86:of prime order
66:
65:
44:
43:
40:
17:
12:
11:
5:
1120:
1118:
1110:
1109:
1104:
1094:
1093:
1089:
1088:
1075:
1057:
1055:
1052:
1030:
1026:
1022:
1017:
1013:
1008:
1002:
998:
994:
991:
986:
982:
977:
973:
968:
964:
959:
953:
949:
945:
942:
937:
933:
928:
924:
919:
915:
910:
904:
900:
896:
893:
890:
885:
881:
876:
870:
866:
862:
857:
853:
848:
842:
838:
834:
829:
825:
820:
814:
810:
806:
801:
797:
774:
770:
763:
759:
755:
750:
746:
741:
728:
725:
711:
707:
699:
695:
689:
685:
680:
676:
654:
650:
642:
638:
632:
628:
623:
619:
593:
589:
583:
579:
574:
570:
543:
539:
534:
528:
524:
499:
495:
464:
460:
454:
450:
445:
422:
407:
406:
391:
387:
382:
376:
373:
370:
366:
361:
353:
349:
344:
338:
335:
332:
328:
324:
317:
313:
308:
270:
266:
235:
231:
226:
201:
196:
188:
184:
177:
173:
150:
122:
96:
74:
52:
39:
36:
15:
13:
10:
9:
6:
4:
3:
2:
1119:
1108:
1105:
1103:
1100:
1099:
1097:
1085:
1082:David Chaum.
1079:
1076:
1072:
1068:
1062:
1059:
1053:
1051:
1049:
1045:
1028:
1024:
1015:
1011:
1006:
1000:
996:
989:
984:
980:
975:
966:
962:
957:
951:
947:
940:
935:
931:
926:
917:
913:
908:
902:
898:
894:
888:
883:
879:
874:
868:
864:
860:
855:
851:
846:
840:
836:
832:
827:
823:
818:
812:
808:
804:
799:
795:
772:
768:
761:
757:
753:
748:
744:
739:
726:
724:
709:
705:
697:
693:
687:
683:
678:
674:
652:
648:
640:
636:
630:
626:
621:
617:
591:
587:
581:
577:
572:
568:
558:
541:
537:
532:
526:
522:
497:
493:
483:
462:
458:
452:
448:
443:
420:
411:
389:
385:
380:
374:
371:
368:
364:
359:
351:
347:
342:
336:
333:
330:
326:
322:
315:
311:
306:
298:
297:
296:
293:
291:
287:
268:
264:
254:
233:
229:
224:
199:
186:
182:
175:
171:
148:
139:
135:
120:
111:
110:Schnorr group
94:
72:
50:
37:
35:
34:(or OV-net).
33:
28:
26:
22:
1078:
1070:
1061:
730:
559:
409:
408:
294:
137:
136:
41:
29:
20:
18:
1044:David Chaum
38:Description
1096:Categories
1054:References
434:publishes
990:⋅
958:−
941:⋅
909:−
895:−
889:⋅
861:⋅
833:⋅
805:⋅
754:⋅
740:∑
706:≠
675:∏
618:∏
569:∏
365:∏
327:∏
183:∈
1073:, 2006.
410:Round 2
138:Round 1
480:and a
288:
372:>
334:<
290:8235
286:RFC
1098::
1069:.
1050:.
723:.
292:.
27:.
1029:0
1025:=
1021:)
1016:2
1012:x
1007:+
1001:1
997:x
993:(
985:3
981:x
976:+
972:)
967:3
963:x
952:1
948:x
944:(
936:2
932:x
927:+
923:)
918:3
914:x
903:2
899:x
892:(
884:1
880:x
875:=
869:3
865:y
856:3
852:x
847:+
841:2
837:y
828:1
824:x
819:+
813:1
809:y
800:1
796:x
773:0
769:=
762:i
758:y
749:i
745:x
710:1
698:i
694:y
688:i
684:c
679:g
653:1
649:=
641:i
637:y
631:i
627:c
622:g
592:i
588:y
582:i
578:c
573:g
542:i
538:x
533:=
527:i
523:c
498:i
494:c
463:i
459:y
453:i
449:c
444:g
421:i
390:j
386:x
381:g
375:i
369:j
360:/
352:j
348:x
343:g
337:i
331:j
323:=
316:i
312:y
307:g
269:i
265:x
234:i
230:x
225:g
200:q
195:Z
187:R
176:i
172:x
149:i
121:n
95:q
73:g
51:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.