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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
\\ zero knowledge proofs
read(group);
\\ Don't use in production code!
\\ This is a very stupid implementation only used in performance evaluation.
kdf(in:vec) =
{
prod(h=1,length(in),lift(in[h]))%q
}
zkp1_proof(G:intmod, x:int) =
{
local(V:intmod, z:int, A:intmod, c:int, r:int);
V = G^x;
z = random(q);
A = G^z;
c = kdf([G, V, A]);
r = (z+c*x)%q;
[G, r, A, V]
}
zkp1_check(P:vec) =
{
local(c:int, G:intmod, r:int, A:intmod, V:intmod);
if (length(P) < 4, error("Proof1 too short."));
if (type(P[1]) == "t_INTMOD", G = P[1], error("P[1] has wrong type."));
if (type(P[2]) == "t_INT", r = P[2], error("P[2] has wrong type."));
if (type(P[3]) == "t_INTMOD", A = P[3], error("P[3] has wrong type."));
if (type(P[4]) == "t_INTMOD", V = P[4], error("P[4] has wrong type."));
c = kdf([G, V, A]);
G^r == A*V^c
}
zkp2_proof(G1:intmod, G2:intmod, x:int) =
{
local(V:intmod, W:intmod, z:int, A:intmod, B:intmod, c:int, r:int);
V = G1^x;
W = G2^x;
z = random(q);
A = G1^z;
B = G2^z;
c = kdf([G1, G2, V, W, A, B]);
r = (z+c*x)%q;
[G1, G2, r, A, B, V, W]
}
zkp2_check(P:vec) =
{
local(c:int,
G1:intmod, G2:intmod, r:int, A:intmod, B:intmod, V:intmod, W:intmod);
if (length(P) < 7, error("Proof2 too short."));
if (type(P[1]) == "t_INTMOD", G1 = P[1], error("P[1] has wrong type."));
if (type(P[2]) == "t_INTMOD", G2 = P[2], error("P[2] has wrong type."));
if (type(P[3]) == "t_INT", r = P[3], error("P[3] has wrong type."));
if (type(P[4]) == "t_INTMOD", A = P[4], error("P[4] has wrong type."));
if (type(P[5]) == "t_INTMOD", B = P[5], error("P[5] has wrong type."));
if (type(P[6]) == "t_INTMOD", V = P[6], error("P[6] has wrong type."));
if (type(P[7]) == "t_INTMOD", W = P[7], error("P[7] has wrong type."));
c = kdf([G1, G2, V, W, A, B]);
G1^r == A*V^c && G2^r == B*W^c
}
zkp3_proof(G:intmod, Y:intmod, M:intmod) =
{
local(Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod,
d1:int, d2:int, r1:int, r2:int, w:int, r:int);
r = random(q);
Alpha = M*Y^r;
Beta = G^r;
if (M == Mod(1, p),
d1 = random(q);
r1 = random(q);
w = random(q);
A1 = G^r1 * Beta^d1;
B1 = Y^r1 * (Alpha / G)^d1;
A2 = G^w;
B2 = Y^w;
c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
d2 = (c - d1) % q;
r2 = (w - r*d2) % q;
,
if (M == G,
d2 = random(q);
r2 = random(q);
w = random(q);
A1 = G^w;
B1 = Y^w;
A2 = G^r2 * Beta^d2;
B2 = Y^r2 * Alpha^d2;
c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
d1 = (c - d2) % q;
r1 = (w - r*d1) % q;
, error("M is neither 1 nor G")
)
);
[G, Y, Alpha, Beta, A1, A2, B1, B2, d1, d2, r1, r2, r]
}
zkp3_check(P:vec) =
{
local(c:int,
G:intmod, Y:intmod, Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod,
d1:int, d2:int, r1:int, r2:int);
if (length(P) < 12, error("Proof3 too short."));
if (type(P[1] ) == "t_INTMOD", G = P[1], error("P[1] has wrong type."));
if (type(P[2] ) == "t_INTMOD", Y = P[2], error("P[2] has wrong type."));
if (type(P[3] ) == "t_INTMOD", Alpha = P[3], error("P[3] has wrong type."));
if (type(P[4] ) == "t_INTMOD", Beta = P[4], error("P[4] has wrong type."));
if (type(P[5] ) == "t_INTMOD", A1 = P[5], error("P[5] has wrong type."));
if (type(P[6] ) == "t_INTMOD", A2 = P[6], error("P[6] has wrong type."));
if (type(P[7] ) == "t_INTMOD", B1 = P[7], error("P[7] has wrong type."));
if (type(P[8] ) == "t_INTMOD", B2 = P[8], error("P[8] has wrong type."));
if (type(P[9] ) == "t_INT", d1 = P[9], error("P[9] has wrong type."));
if (type(P[10]) == "t_INT", d2 = P[10], error("P[10] has wrong type."));
if (type(P[11]) == "t_INT", r1 = P[11], error("P[11] has wrong type."));
if (type(P[12]) == "t_INT", r2 = P[12], error("P[12] has wrong type."));
c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
c == (d1 + d2) % q &&
A1 == G^r1 * Beta^d1 &&
A2 == G^r2 * Beta^d2 &&
B1 == Y^r1 * (Alpha / G)^d1 &&
B2 == Y^r2 * Alpha^d2
}
;
|
