2454:. The naming originates from Sig, referring to the zig-zag symbolizing the three moves of the protocol, and MA, an abbreviation of "Merlin-Arthur". Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of
1412:
In order to define a specific proof of knowledge, one need not only define the language, but also the witnesses the verifier should know. In some cases proving membership in a language may be easy, while computing a specific witness may be hard. This is best explained using an example:
996:
35:
to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself (as is the case for
3110:
2971:
2413:
478:
2746:
846:
851:
2272:
199:
1392:
1519:
1565:
1440:
2795:
2184:
2085:
1946:
1750:
1252:
1223:
765:
736:
562:
533:
1304:
1070:
327:
1986:
1807:
1618:
1334:
687:
667:
242:
1899:
2861:
2830:
2656:
2629:
2602:
2560:
2533:
2506:
2479:
2135:
2036:
1668:
1018:
627:
122:
3127:
Proofs of knowledge are useful tool for the construction of identification protocols, and in their non-interactive variant, signature schemes. Such schemes are:
2433:
2108:
2006:
1860:
1837:
1774:
1708:
1688:
1585:
1539:
1464:
1272:
1194:
1174:
1150:
1130:
1110:
1090:
1038:
707:
647:
598:
504:
407:
387:
367:
347:
282:
262:
222:
93:
73:
40:) a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by
2982:
3306:
2870:
564:
in convincing the verifier. This property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier.
2281:
2976:
This is the intuition behind the following notation, which is commonly used to express what exactly is proven by a proof of knowledge.
1277:
This definition of the validity property is a combination of the validity and strong validity properties. For small knowledge errors
412:
2661:
770:
3254:, Efficient identification and signatures for smart cards, in G Brassard, ed. Advances in Cryptology – Crypto '89, 239–252,
3179:
3174:
1396:
480:, i.e. given the interaction between the prover P and the verifier V, the probability that the verifier is convinced is 1.
991:{\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}
2192:
127:
124:
the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation:
3164:
1401:
28:
31:
in which the prover succeeds in 'convincing' a verifier that the prover knows something. What it means for a
1339:
3169:
3154:
2566:
1473:
3311:
2833:
37:
1544:
1419:
44:
bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some
3159:
2439:
2751:
2450:
Protocols which have the above three-move structure (commitment, challenge and response) are called
2140:
2041:
1908:
1716:
1228:
1199:
741:
712:
538:
509:
3142:
1951:
We can see this is a valid proof of knowledge because it has an extractor that works as follows:
1636:
1467:
1280:
1046:
294:
3131:
1958:
1779:
1590:
1309:
672:
652:
227:
3251:
3197:
1869:
32:
2839:
2808:
2634:
2607:
2580:
2538:
2511:
2484:
2457:
2113:
2014:
1646:
1003:
3289:
3255:
3217:
3205:
3138:
603:
98:
49:
45:
41:
2418:
2093:
1991:
1845:
1822:
1759:
1693:
1673:
1570:
1524:
1449:
1257:
1179:
1159:
1153:
1135:
1115:
1095:
1075:
1023:
692:
632:
583:
489:
392:
372:
352:
332:
267:
247:
207:
78:
58:
3300:
3231:
3201:
1641:
1443:
20:
3105:{\displaystyle PK\{(x):y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}\},}
3235:
3209:
506:
in extracting the witness, given oracle access to a possibly malicious prover
486:: Validity requires that the success probability of a knowledge extractor
3239:
2966:{\displaystyle y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}}
2563:
1470:
problem is believed to be hard. Deciding membership of the language
535:, must be at least as high as the success probability of the prover
3267:
2408:{\displaystyle (s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})}
2442:, though that property is not required for a proof of knowledge.
1633:
One of the simplest and frequently used proofs of knowledge, the
3290:
Proof
Systems for General Statements about Discrete Logarithms
3280:
Modular Design of Secure yet
Practical Cryptographic Protocols
3278:
473:{\displaystyle \Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1}
1620:
holds corresponds to solving the discrete logarithm problem.
2741:{\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}
1756:
In the first round the prover commits himself to randomness
841:{\displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}
3214:
Proceedings of 17th
Symposium on the Theory of Computation
1112:, even though the prover does in fact not know a witness
1152:
is used to express what is meant by the knowledge of a
3210:
The knowledge complexity of interactive proof-systems
2985:
2873:
2842:
2811:
2754:
2664:
2637:
2610:
2583:
2541:
2514:
2487:
2460:
2421:
2284:
2195:
2143:
2116:
2096:
2044:
2017:
1994:
1961:
1911:
1872:
1848:
1825:
1782:
1762:
1752:, the prover interacts with the verifier as follows:
1719:
1696:
1676:
1649:
1593:
1573:
1547:
1527:
1476:
1452:
1422:
1342:
1312:
1283:
1260:
1231:
1202:
1182:
1162:
1138:
1118:
1098:
1078:
1049:
1026:
1006:
854:
773:
744:
715:
695:
675:
655:
635:
606:
586:
541:
512:
492:
415:
395:
375:
355:
335:
297:
270:
250:
230:
210:
130:
101:
81:
61:
1862:, the prover sends the third and last message (the
1640:, is due to Schnorr. The protocol is defined for a
3104:
2965:
2855:
2824:
2789:
2740:
2650:
2623:
2596:
2554:
2527:
2500:
2473:
2427:
2407:
2266:
2178:
2129:
2102:
2079:
2030:
2000:
1980:
1940:
1893:
1854:
1831:
1801:
1768:
1744:
1702:
1682:
1662:
1612:
1579:
1559:
1533:
1513:
1458:
1434:
1386:
1328:
1298:
1266:
1246:
1217:
1188:
1168:
1144:
1124:
1104:
1084:
1064:
1032:
1012:
990:
840:
759:
730:
701:
681:
661:
641:
621:
592:
556:
527:
498:
472:
401:
381:
361:
341:
321:
276:
256:
236:
216:
193:
116:
87:
67:
3258:, 1990. Lecture Notes in Computer Science, nr 435
2797:. Equality corresponds to the special case where
689:-valid if there exists a polynomial-time machine
919:
855:
416:
2267:{\displaystyle (s_{1}-s_{2})(c_{1}-c_{2})^{-1}}
2863:this is equivalent to proving knowledge of an
2604:, we say that the prover proves knowledge of
669:the knowledge error. A proof of knowledge is
8:
3096:
2992:
1554:
1548:
1508:
1483:
1429:
1423:
835:
829:
194:{\displaystyle R=\{(x,w):x\in L,w\in W(x)\}}
188:
137:
2415:, the output of the extractor is precisely
3137:They are also used in the construction of
1394:it can be seen as being stronger than the
1072:denotes the probability that the verifier
629:the set of all witnesses for public value
3216:, Providence, Rhode Island. 1985. Draft.
3090:
3085:
3075:
3065:
3060:
3052:
3042:
3029:
3024:
3011:
2984:
2957:
2952:
2942:
2932:
2927:
2919:
2909:
2896:
2891:
2878:
2872:
2847:
2841:
2816:
2810:
2775:
2759:
2753:
2730:
2725:
2720:
2707:
2692:
2687:
2682:
2669:
2663:
2642:
2636:
2615:
2609:
2588:
2582:
2546:
2540:
2519:
2513:
2492:
2486:
2465:
2459:
2420:
2396:
2383:
2358:
2330:
2305:
2292:
2283:
2255:
2245:
2232:
2216:
2203:
2194:
2167:
2148:
2142:
2121:
2115:
2095:
2068:
2049:
2043:
2022:
2016:
1993:
1972:
1960:
1932:
1916:
1910:
1871:
1847:
1824:
1793:
1781:
1761:
1730:
1718:
1695:
1675:
1654:
1648:
1598:
1592:
1572:
1546:
1526:
1496:
1475:
1451:
1421:
1376:
1368:
1351:
1346:
1341:
1317:
1311:
1282:
1259:
1233:
1232:
1230:
1204:
1203:
1201:
1181:
1161:
1137:
1117:
1097:
1077:
1048:
1025:
1005:
926:
925:
867:
866:
865:
853:
780:
779:
778:
772:
746:
745:
743:
717:
716:
714:
694:
674:
654:
634:
605:
585:
543:
542:
540:
514:
513:
511:
491:
414:
394:
374:
354:
334:
296:
269:
249:
229:
209:
129:
100:
80:
60:
2110:. Now generate a different random value
3190:
2038:and input it to the prover. It outputs
3227:
3225:
1901:reduced modulo the order of the group.
1408:Relation to general interactive proofs
1387:{\displaystyle 1/\mathrm {poly} (|x|)}
573:This is a more rigorous definition of
244:is a two party protocol with a prover
7:
389:succeeds in convincing the verifier
1514:{\displaystyle L=\{x\mid g^{w}=x\}}
284:with the following two properties:
3119:that fulfills the relation above.
2137:and input it to the prover to get
1361:
1358:
1355:
1352:
1020:signifies that the Turing machine
1007:
832:
204:A proof of knowledge for relation
14:
1560:{\displaystyle \langle g\rangle }
1435:{\displaystyle \langle g\rangle }
409:of his knowledge. More formally:
3115:states that the prover knows an
2562:are equal or fulfill some other
3307:Computational complexity theory
3236:On Defining Proofs of Knowledge
1713:In order to prove knowledge of
1567:. However, finding the witness
3071:
3053:
3001:
2995:
2938:
2920:
2790:{\displaystyle x_{2}=ax_{1}+b}
2402:
2376:
2367:
2345:
2339:
2317:
2311:
2285:
2252:
2225:
2222:
2196:
2179:{\displaystyle s_{2}=r+c_{2}x}
2080:{\displaystyle s_{1}=r+c_{1}x}
1955:Simulate the prover to output
1776:; therefore the first message
1381:
1377:
1369:
1365:
1293:
1287:
1238:
1209:
1059:
1053:
1040:did not come to a conclusion.
982:
976:
967:
961:
958:
952:
946:
943:
937:
931:
922:
913:
910:
904:
895:
889:
884:
878:
872:
858:
823:
817:
808:
802:
797:
791:
785:
751:
722:
616:
610:
548:
519:
461:
455:
452:
446:
440:
437:
425:
419:
310:
298:
185:
179:
152:
140:
111:
105:
1:
3180:Soundness (interactive proof)
3175:Zero-knowledge password proof
1988:. The prover is now in state
3143:anonymous digital credential
2438:This protocol happens to be
1941:{\displaystyle g^{s}=ty^{c}}
1816:The verifier replies with a
1745:{\displaystyle x=\log _{g}y}
1247:{\displaystyle {\tilde {P}}}
1218:{\displaystyle {\tilde {P}}}
760:{\displaystyle {\tilde {P}}}
731:{\displaystyle {\tilde {P}}}
557:{\displaystyle {\tilde {P}}}
528:{\displaystyle {\tilde {P}}}
2090:Rewind the prover to state
75:be a statement of language
3328:
1299:{\displaystyle \kappa (x)}
1132:. The knowledge extractor
1065:{\displaystyle \kappa (x)}
322:{\displaystyle (x,w)\in R}
16:Class of interactive proof
1905:The verifier accepts, if
709:, given oracle access to
569:Details on the definition
3165:Interactive proof system
1635:proof of knowledge of a
1981:{\displaystyle t=g^{r}}
1802:{\displaystyle t=g^{r}}
1613:{\displaystyle g^{w}=x}
1329:{\displaystyle 2^{-80}}
738:, such that for every
682:{\displaystyle \kappa }
662:{\displaystyle \kappa }
600:be a witness relation,
237:{\displaystyle \kappa }
3170:Topics in cryptography
3155:Cryptographic protocol
3106:
2967:
2857:
2826:
2791:
2742:
2652:
2625:
2598:
2556:
2529:
2508:with respect to bases
2502:
2475:
2429:
2409:
2268:
2180:
2131:
2104:
2081:
2032:
2011:Generate random value
2002:
1982:
1942:
1895:
1894:{\displaystyle s=r+cx}
1856:
1833:
1803:
1770:
1746:
1704:
1684:
1664:
1614:
1581:
1561:
1535:
1515:
1460:
1436:
1388:
1330:
1300:
1268:
1248:
1219:
1190:
1170:
1146:
1126:
1106:
1086:
1066:
1034:
1014:
992:
842:
767:, it is the case that
761:
732:
703:
683:
663:
643:
623:
594:
558:
529:
500:
474:
403:
383:
363:
343:
323:
278:
258:
238:
218:
195:
118:
89:
69:
3107:
2968:
2858:
2856:{\displaystyle x_{1}}
2827:
2825:{\displaystyle x_{2}}
2792:
2743:
2653:
2651:{\displaystyle x_{2}}
2626:
2624:{\displaystyle x_{1}}
2599:
2597:{\displaystyle Z_{q}}
2557:
2555:{\displaystyle g_{2}}
2530:
2528:{\displaystyle g_{1}}
2503:
2501:{\displaystyle y_{2}}
2476:
2474:{\displaystyle y_{1}}
2430:
2410:
2269:
2181:
2132:
2130:{\displaystyle c_{2}}
2105:
2082:
2033:
2031:{\displaystyle c_{1}}
2003:
1983:
1943:
1896:
1857:
1834:
1804:
1771:
1747:
1705:
1685:
1665:
1663:{\displaystyle G_{q}}
1615:
1582:
1562:
1536:
1521:is trivial, as every
1516:
1466:in which solving the
1461:
1437:
1389:
1331:
1301:
1269:
1249:
1220:
1191:
1171:
1147:
1127:
1107:
1087:
1067:
1035:
1015:
1013:{\displaystyle \bot }
993:
843:
762:
733:
704:
684:
664:
644:
624:
595:
559:
530:
501:
475:
404:
384:
364:
344:
324:
279:
259:
239:
224:with knowledge error
219:
196:
119:
90:
70:
38:zero-knowledge proofs
3160:Zero-knowledge proof
2983:
2871:
2840:
2809:
2752:
2662:
2635:
2608:
2581:
2539:
2512:
2485:
2458:
2419:
2282:
2193:
2141:
2114:
2094:
2042:
2015:
1992:
1959:
1909:
1870:
1846:
1823:
1780:
1760:
1717:
1694:
1674:
1647:
1591:
1571:
1545:
1525:
1474:
1450:
1420:
1340:
1310:
1281:
1258:
1229:
1200:
1180:
1160:
1136:
1116:
1096:
1076:
1047:
1043:The knowledge error
1024:
1004:
852:
771:
742:
713:
693:
673:
653:
633:
622:{\displaystyle W(x)}
604:
584:
539:
510:
490:
413:
393:
373:
353:
333:
295:
268:
248:
228:
208:
128:
117:{\displaystyle W(x)}
99:
79:
59:
3095:
3070:
3034:
2962:
2937:
2901:
2805: = 0. As
2801: = 1 and
2737:
2699:
1254:knows the value of
3269:On Sigma protocols
3234:, Oded Goldreich:
3102:
3081:
3056:
3020:
2963:
2948:
2923:
2887:
2853:
2822:
2787:
2738:
2716:
2678:
2648:
2621:
2594:
2552:
2525:
2498:
2471:
2425:
2405:
2264:
2176:
2127:
2100:
2077:
2028:
1998:
1978:
1938:
1891:
1852:
1829:
1799:
1766:
1742:
1700:
1680:
1660:
1637:discrete logarithm
1610:
1577:
1557:
1531:
1511:
1468:discrete logarithm
1456:
1432:
1402:interactive proofs
1384:
1326:
1296:
1264:
1244:
1215:
1186:
1166:
1142:
1122:
1102:
1082:
1062:
1030:
1010:
988:
838:
757:
728:
699:
679:
659:
639:
619:
590:
554:
525:
496:
470:
399:
379:
359:
349:who knows witness
339:
329:, then the prover
319:
274:
254:
234:
214:
191:
114:
85:
65:
25:proof of knowledge
3218:Extended abstract
3132:Schnorr signature
2428:{\displaystyle x}
2103:{\displaystyle Q}
2001:{\displaystyle Q}
1855:{\displaystyle c}
1839:chosen at random.
1832:{\displaystyle c}
1769:{\displaystyle r}
1703:{\displaystyle g}
1683:{\displaystyle q}
1580:{\displaystyle w}
1534:{\displaystyle x}
1459:{\displaystyle g}
1267:{\displaystyle w}
1241:
1212:
1189:{\displaystyle w}
1169:{\displaystyle E}
1145:{\displaystyle E}
1125:{\displaystyle w}
1105:{\displaystyle x}
1085:{\displaystyle V}
1033:{\displaystyle E}
934:
875:
788:
754:
725:
702:{\displaystyle E}
642:{\displaystyle x}
593:{\displaystyle R}
551:
522:
499:{\displaystyle E}
402:{\displaystyle V}
382:{\displaystyle x}
362:{\displaystyle w}
342:{\displaystyle P}
277:{\displaystyle V}
257:{\displaystyle P}
217:{\displaystyle R}
88:{\displaystyle L}
68:{\displaystyle x}
29:interactive proof
3319:
3292:
3287:
3281:
3276:
3270:
3265:
3259:
3249:
3243:
3229:
3220:
3198:Shafi Goldwasser
3195:
3111:
3109:
3108:
3103:
3094:
3089:
3080:
3079:
3074:
3069:
3064:
3047:
3046:
3033:
3028:
3016:
3015:
2972:
2970:
2969:
2964:
2961:
2956:
2947:
2946:
2941:
2936:
2931:
2914:
2913:
2900:
2895:
2883:
2882:
2862:
2860:
2859:
2854:
2852:
2851:
2831:
2829:
2828:
2823:
2821:
2820:
2796:
2794:
2793:
2788:
2780:
2779:
2764:
2763:
2747:
2745:
2744:
2739:
2736:
2735:
2734:
2724:
2712:
2711:
2698:
2697:
2696:
2686:
2674:
2673:
2657:
2655:
2654:
2649:
2647:
2646:
2630:
2628:
2627:
2622:
2620:
2619:
2603:
2601:
2600:
2595:
2593:
2592:
2561:
2559:
2558:
2553:
2551:
2550:
2534:
2532:
2531:
2526:
2524:
2523:
2507:
2505:
2504:
2499:
2497:
2496:
2480:
2478:
2477:
2472:
2470:
2469:
2434:
2432:
2431:
2426:
2414:
2412:
2411:
2406:
2401:
2400:
2388:
2387:
2363:
2362:
2335:
2334:
2310:
2309:
2297:
2296:
2273:
2271:
2270:
2265:
2263:
2262:
2250:
2249:
2237:
2236:
2221:
2220:
2208:
2207:
2185:
2183:
2182:
2177:
2172:
2171:
2153:
2152:
2136:
2134:
2133:
2128:
2126:
2125:
2109:
2107:
2106:
2101:
2086:
2084:
2083:
2078:
2073:
2072:
2054:
2053:
2037:
2035:
2034:
2029:
2027:
2026:
2007:
2005:
2004:
1999:
1987:
1985:
1984:
1979:
1977:
1976:
1947:
1945:
1944:
1939:
1937:
1936:
1921:
1920:
1900:
1898:
1897:
1892:
1861:
1859:
1858:
1853:
1842:After receiving
1838:
1836:
1835:
1830:
1808:
1806:
1805:
1800:
1798:
1797:
1775:
1773:
1772:
1767:
1751:
1749:
1748:
1743:
1735:
1734:
1709:
1707:
1706:
1701:
1689:
1687:
1686:
1681:
1669:
1667:
1666:
1661:
1659:
1658:
1629:Schnorr protocol
1619:
1617:
1616:
1611:
1603:
1602:
1586:
1584:
1583:
1578:
1566:
1564:
1563:
1558:
1540:
1538:
1537:
1532:
1520:
1518:
1517:
1512:
1501:
1500:
1465:
1463:
1462:
1457:
1441:
1439:
1438:
1433:
1393:
1391:
1390:
1385:
1380:
1372:
1364:
1350:
1335:
1333:
1332:
1327:
1325:
1324:
1305:
1303:
1302:
1297:
1273:
1271:
1270:
1265:
1253:
1251:
1250:
1245:
1243:
1242:
1234:
1224:
1222:
1221:
1216:
1214:
1213:
1205:
1195:
1193:
1192:
1187:
1175:
1173:
1172:
1167:
1151:
1149:
1148:
1143:
1131:
1129:
1128:
1123:
1111:
1109:
1108:
1103:
1091:
1089:
1088:
1083:
1071:
1069:
1068:
1063:
1039:
1037:
1036:
1031:
1019:
1017:
1016:
1011:
997:
995:
994:
989:
936:
935:
927:
888:
887:
877:
876:
868:
847:
845:
844:
839:
801:
800:
790:
789:
781:
766:
764:
763:
758:
756:
755:
747:
737:
735:
734:
729:
727:
726:
718:
708:
706:
705:
700:
688:
686:
685:
680:
668:
666:
665:
660:
648:
646:
645:
640:
628:
626:
625:
620:
599:
597:
596:
591:
563:
561:
560:
555:
553:
552:
544:
534:
532:
531:
526:
524:
523:
515:
505:
503:
502:
497:
479:
477:
476:
471:
408:
406:
405:
400:
388:
386:
385:
380:
368:
366:
365:
360:
348:
346:
345:
340:
328:
326:
325:
320:
283:
281:
280:
275:
263:
261:
260:
255:
243:
241:
240:
235:
223:
221:
220:
215:
200:
198:
197:
192:
123:
121:
120:
115:
94:
92:
91:
86:
74:
72:
71:
66:
3327:
3326:
3322:
3321:
3320:
3318:
3317:
3316:
3297:
3296:
3295:
3288:
3284:
3277:
3273:
3266:
3262:
3256:Springer-Verlag
3250:
3246:
3230:
3223:
3206:Charles Rackoff
3196:
3192:
3188:
3151:
3139:group signature
3125:
3051:
3038:
3007:
2981:
2980:
2918:
2905:
2874:
2869:
2868:
2843:
2838:
2837:
2812:
2807:
2806:
2771:
2755:
2750:
2749:
2726:
2703:
2688:
2665:
2660:
2659:
2638:
2633:
2632:
2611:
2606:
2605:
2584:
2579:
2578:
2542:
2537:
2536:
2515:
2510:
2509:
2488:
2483:
2482:
2461:
2456:
2455:
2452:sigma protocols
2448:
2446:Sigma protocols
2417:
2416:
2392:
2379:
2354:
2326:
2301:
2288:
2280:
2279:
2251:
2241:
2228:
2212:
2199:
2191:
2190:
2163:
2144:
2139:
2138:
2117:
2112:
2111:
2092:
2091:
2064:
2045:
2040:
2039:
2018:
2013:
2012:
1990:
1989:
1968:
1957:
1956:
1928:
1912:
1907:
1906:
1868:
1867:
1844:
1843:
1821:
1820:
1809:is also called
1789:
1778:
1777:
1758:
1757:
1726:
1715:
1714:
1692:
1691:
1690:with generator
1672:
1671:
1650:
1645:
1644:
1631:
1626:
1594:
1589:
1588:
1569:
1568:
1543:
1542:
1523:
1522:
1492:
1472:
1471:
1448:
1447:
1446:with generator
1418:
1417:
1410:
1338:
1337:
1313:
1308:
1307:
1306:, such as e.g.
1279:
1278:
1256:
1255:
1227:
1226:
1198:
1197:
1178:
1177:
1158:
1157:
1134:
1133:
1114:
1113:
1094:
1093:
1074:
1073:
1045:
1044:
1022:
1021:
1002:
1001:
861:
850:
849:
774:
769:
768:
740:
739:
711:
710:
691:
690:
671:
670:
651:
650:
631:
630:
602:
601:
582:
581:
571:
537:
536:
508:
507:
488:
487:
411:
410:
391:
390:
371:
370:
351:
350:
331:
330:
293:
292:
266:
265:
264:and a verifier
246:
245:
226:
225:
206:
205:
126:
125:
97:
96:
77:
76:
57:
56:
42:polynomial time
17:
12:
11:
5:
3325:
3323:
3315:
3314:
3309:
3299:
3298:
3294:
3293:
3282:
3271:
3260:
3244:
3221:
3189:
3187:
3184:
3183:
3182:
3177:
3172:
3167:
3162:
3157:
3150:
3147:
3135:
3134:
3124:
3121:
3113:
3112:
3101:
3098:
3093:
3088:
3084:
3078:
3073:
3068:
3063:
3059:
3055:
3050:
3045:
3041:
3037:
3032:
3027:
3023:
3019:
3014:
3010:
3006:
3003:
3000:
2997:
2994:
2991:
2988:
2960:
2955:
2951:
2945:
2940:
2935:
2930:
2926:
2922:
2917:
2912:
2908:
2904:
2899:
2894:
2890:
2886:
2881:
2877:
2850:
2846:
2836:computed from
2819:
2815:
2786:
2783:
2778:
2774:
2770:
2767:
2762:
2758:
2733:
2729:
2723:
2719:
2715:
2710:
2706:
2702:
2695:
2691:
2685:
2681:
2677:
2672:
2668:
2645:
2641:
2618:
2614:
2591:
2587:
2549:
2545:
2522:
2518:
2495:
2491:
2468:
2464:
2447:
2444:
2440:zero-knowledge
2424:
2404:
2399:
2395:
2391:
2386:
2382:
2378:
2375:
2372:
2369:
2366:
2361:
2357:
2353:
2350:
2347:
2344:
2341:
2338:
2333:
2329:
2325:
2322:
2319:
2316:
2313:
2308:
2304:
2300:
2295:
2291:
2287:
2276:
2275:
2261:
2258:
2254:
2248:
2244:
2240:
2235:
2231:
2227:
2224:
2219:
2215:
2211:
2206:
2202:
2198:
2187:
2175:
2170:
2166:
2162:
2159:
2156:
2151:
2147:
2124:
2120:
2099:
2088:
2076:
2071:
2067:
2063:
2060:
2057:
2052:
2048:
2025:
2021:
2009:
1997:
1975:
1971:
1967:
1964:
1935:
1931:
1927:
1924:
1919:
1915:
1903:
1902:
1890:
1887:
1884:
1881:
1878:
1875:
1851:
1840:
1828:
1814:
1796:
1792:
1788:
1785:
1765:
1741:
1738:
1733:
1729:
1725:
1722:
1699:
1679:
1657:
1653:
1630:
1627:
1625:
1622:
1609:
1606:
1601:
1597:
1576:
1556:
1553:
1550:
1530:
1510:
1507:
1504:
1499:
1495:
1491:
1488:
1485:
1482:
1479:
1455:
1431:
1428:
1425:
1409:
1406:
1383:
1379:
1375:
1371:
1367:
1363:
1360:
1357:
1354:
1349:
1345:
1323:
1320:
1316:
1295:
1292:
1289:
1286:
1263:
1240:
1237:
1225:, we say that
1211:
1208:
1185:
1165:
1154:Turing machine
1141:
1121:
1101:
1081:
1061:
1058:
1055:
1052:
1029:
1009:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
933:
930:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
886:
883:
880:
874:
871:
864:
860:
857:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
799:
796:
793:
787:
784:
777:
753:
750:
724:
721:
698:
678:
658:
638:
618:
615:
612:
609:
589:
570:
567:
566:
565:
550:
547:
521:
518:
495:
481:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
398:
378:
358:
338:
318:
315:
312:
309:
306:
303:
300:
273:
253:
233:
213:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
151:
148:
145:
142:
139:
136:
133:
113:
110:
107:
104:
84:
64:
15:
13:
10:
9:
6:
4:
3:
2:
3324:
3313:
3310:
3308:
3305:
3304:
3302:
3291:
3286:
3283:
3279:
3275:
3272:
3268:
3264:
3261:
3257:
3253:
3248:
3245:
3242:1992: 390–420
3241:
3237:
3233:
3232:Mihir Bellare
3228:
3226:
3222:
3219:
3215:
3211:
3207:
3203:
3202:Silvio Micali
3199:
3194:
3191:
3185:
3181:
3178:
3176:
3173:
3171:
3168:
3166:
3163:
3161:
3158:
3156:
3153:
3152:
3148:
3146:
3144:
3140:
3133:
3130:
3129:
3128:
3122:
3120:
3118:
3099:
3091:
3086:
3082:
3076:
3066:
3061:
3057:
3048:
3043:
3039:
3035:
3030:
3025:
3021:
3017:
3012:
3008:
3004:
2998:
2989:
2986:
2979:
2978:
2977:
2974:
2958:
2953:
2949:
2943:
2933:
2928:
2924:
2915:
2910:
2906:
2902:
2897:
2892:
2888:
2884:
2879:
2875:
2866:
2848:
2844:
2835:
2817:
2813:
2804:
2800:
2784:
2781:
2776:
2772:
2768:
2765:
2760:
2756:
2731:
2727:
2721:
2717:
2713:
2708:
2704:
2700:
2693:
2689:
2683:
2679:
2675:
2670:
2666:
2643:
2639:
2616:
2612:
2589:
2585:
2576:
2572:
2568:
2565:
2547:
2543:
2520:
2516:
2493:
2489:
2466:
2462:
2453:
2445:
2443:
2441:
2436:
2422:
2397:
2393:
2389:
2384:
2380:
2373:
2370:
2364:
2359:
2355:
2351:
2348:
2342:
2336:
2331:
2327:
2323:
2320:
2314:
2306:
2302:
2298:
2293:
2289:
2259:
2256:
2246:
2242:
2238:
2233:
2229:
2217:
2213:
2209:
2204:
2200:
2188:
2173:
2168:
2164:
2160:
2157:
2154:
2149:
2145:
2122:
2118:
2097:
2089:
2074:
2069:
2065:
2061:
2058:
2055:
2050:
2046:
2023:
2019:
2010:
1995:
1973:
1969:
1965:
1962:
1954:
1953:
1952:
1949:
1933:
1929:
1925:
1922:
1917:
1913:
1888:
1885:
1882:
1879:
1876:
1873:
1865:
1849:
1841:
1826:
1819:
1815:
1812:
1794:
1790:
1786:
1783:
1763:
1755:
1754:
1753:
1739:
1736:
1731:
1727:
1723:
1720:
1711:
1697:
1677:
1655:
1651:
1643:
1639:
1638:
1628:
1623:
1621:
1607:
1604:
1599:
1595:
1574:
1551:
1528:
1505:
1502:
1497:
1493:
1489:
1486:
1480:
1477:
1469:
1453:
1445:
1426:
1414:
1407:
1405:
1403:
1399:
1398:
1373:
1347:
1343:
1321:
1318:
1314:
1290:
1284:
1275:
1261:
1235:
1206:
1183:
1163:
1155:
1139:
1119:
1099:
1092:might accept
1079:
1056:
1050:
1041:
1027:
998:
985:
979:
973:
970:
964:
955:
949:
940:
928:
916:
907:
901:
898:
892:
881:
869:
862:
826:
820:
814:
811:
805:
794:
782:
775:
748:
719:
696:
676:
656:
636:
613:
607:
587:
578:
576:
568:
545:
516:
493:
485:
482:
467:
464:
458:
449:
443:
434:
431:
428:
422:
396:
376:
356:
336:
316:
313:
307:
304:
301:
290:
287:
286:
285:
271:
251:
231:
211:
202:
182:
176:
173:
170:
167:
164:
161:
158:
155:
149:
146:
143:
134:
131:
108:
102:
82:
62:
53:
51:
47:
43:
39:
34:
30:
26:
22:
3312:Cryptography
3285:
3274:
3263:
3247:
3213:
3193:
3136:
3126:
3123:Applications
3116:
3114:
2975:
2864:
2802:
2798:
2577:elements of
2574:
2570:
2451:
2449:
2437:
2277:
1950:
1904:
1863:
1817:
1810:
1712:
1642:cyclic group
1634:
1632:
1444:cyclic group
1415:
1411:
1400:of ordinary
1395:
1276:
1176:can extract
1042:
999:
579:
574:
572:
483:
289:Completeness
288:
203:
54:
24:
21:cryptography
18:
3252:C P Schnorr
1000:The result
95:in NP, and
3301:Categories
3186:References
2867:such that
2658:such that
1811:commitment
1587:such that
3145:systems.
3036:∧
2903:∧
2834:trivially
2701:∧
2390:−
2343:−
2299:−
2257:−
2239:−
2210:−
1818:challenge
1737:
1670:of order
1624:Protocols
1555:⟩
1549:⟨
1490:∣
1430:⟩
1424:⟨
1397:soundness
1319:−
1285:κ
1239:~
1210:~
1051:κ
1008:⊥
974:κ
971:−
962:→
947:↔
932:~
917:≥
899:∈
873:~
833:⊥
827:∪
812:∈
786:~
752:~
723:~
677:κ
657:κ
549:~
520:~
456:→
441:↔
314:∈
232:κ
174:∈
162:∈
3149:See also
2567:relation
1864:response
575:Validity
484:Validity
46:language
2832:can be
2189:Output
33:machine
3240:CRYPTO
3204:, and
2569:. For
2564:linear
2278:Since
1541:is in
649:, and
27:is an
1442:be a
1196:from
1156:. If
291:: If
3141:and
2748:and
2631:and
2573:and
2535:and
2481:and
1416:Let
848:and
580:Let
369:for
55:Let
23:, a
1728:log
1336:or
48:in
19:In
3303::
3238:.
3224:^
3212:.
3208:.
3200:,
2973:.
2435:.
1948:.
1866:)
1710:.
1404:.
1322:80
1274:.
920:Pr
856:Pr
577::
417:Pr
201:.
52:.
50:NP
3117:x
3100:,
3097:}
3092:b
3087:2
3083:g
3077:x
3072:)
3067:a
3062:2
3058:g
3054:(
3049:=
3044:2
3040:y
3031:x
3026:1
3022:g
3018:=
3013:1
3009:y
3005::
3002:)
2999:x
2996:(
2993:{
2990:K
2987:P
2959:b
2954:2
2950:g
2944:x
2939:)
2934:a
2929:2
2925:g
2921:(
2916:=
2911:2
2907:y
2898:x
2893:1
2889:g
2885:=
2880:1
2876:y
2865:x
2849:1
2845:x
2818:2
2814:x
2803:b
2799:a
2785:b
2782:+
2777:1
2773:x
2769:a
2766:=
2761:2
2757:x
2732:2
2728:x
2722:2
2718:g
2714:=
2709:2
2705:y
2694:1
2690:x
2684:1
2680:g
2676:=
2671:1
2667:y
2644:2
2640:x
2617:1
2613:x
2590:q
2586:Z
2575:b
2571:a
2548:2
2544:g
2521:1
2517:g
2494:2
2490:y
2467:1
2463:y
2423:x
2403:)
2398:2
2394:c
2385:1
2381:c
2377:(
2374:x
2371:=
2368:)
2365:x
2360:2
2356:c
2352:+
2349:r
2346:(
2340:)
2337:x
2332:1
2328:c
2324:+
2321:r
2318:(
2315:=
2312:)
2307:2
2303:s
2294:1
2290:s
2286:(
2274:.
2260:1
2253:)
2247:2
2243:c
2234:1
2230:c
2226:(
2223:)
2218:2
2214:s
2205:1
2201:s
2197:(
2186:.
2174:x
2169:2
2165:c
2161:+
2158:r
2155:=
2150:2
2146:s
2123:2
2119:c
2098:Q
2087:.
2075:x
2070:1
2066:c
2062:+
2059:r
2056:=
2051:1
2047:s
2024:1
2020:c
2008:.
1996:Q
1974:r
1970:g
1966:=
1963:t
1934:c
1930:y
1926:t
1923:=
1918:s
1914:g
1889:x
1886:c
1883:+
1880:r
1877:=
1874:s
1850:c
1827:c
1813:.
1795:r
1791:g
1787:=
1784:t
1764:r
1740:y
1732:g
1724:=
1721:x
1698:g
1678:q
1656:q
1652:G
1608:x
1605:=
1600:w
1596:g
1575:w
1552:g
1529:x
1509:}
1506:x
1503:=
1498:w
1494:g
1487:x
1484:{
1481:=
1478:L
1454:g
1427:g
1382:)
1378:|
1374:x
1370:|
1366:(
1362:y
1359:l
1356:o
1353:p
1348:/
1344:1
1315:2
1294:)
1291:x
1288:(
1262:w
1236:P
1207:P
1184:w
1164:E
1140:E
1120:w
1100:x
1080:V
1060:)
1057:x
1054:(
1028:E
986:.
983:)
980:x
977:(
968:)
965:1
959:)
956:x
953:(
950:V
944:)
941:x
938:(
929:P
923:(
914:)
911:)
908:x
905:(
902:W
896:)
893:x
890:(
885:)
882:x
879:(
870:P
863:E
859:(
836:}
830:{
824:)
821:x
818:(
815:W
809:)
806:x
803:(
798:)
795:x
792:(
783:P
776:E
749:P
720:P
697:E
637:x
617:)
614:x
611:(
608:W
588:R
546:P
517:P
494:E
468:1
465:=
462:)
459:1
453:)
450:x
447:(
444:V
438:)
435:w
432:,
429:x
426:(
423:P
420:(
397:V
377:x
357:w
337:P
317:R
311:)
308:w
305:,
302:x
299:(
272:V
252:P
212:R
189:}
186:)
183:x
180:(
177:W
171:w
168:,
165:L
159:x
156::
153:)
150:w
147:,
144:x
141:(
138:{
135:=
132:R
112:)
109:x
106:(
103:W
83:L
63:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.