diff options
author | Markus Teich <markus.teich@stusta.mhn.de> | 2017-01-04 17:43:24 +0100 |
---|---|---|
committer | Markus Teich <markus.teich@stusta.mhn.de> | 2017-01-04 17:43:24 +0100 |
commit | c50392f9df44b99263c3481b7b4dc7ae890dc4a8 (patch) | |
tree | 79a257aadd74f17555f37d0c539d03f756acc5d3 | |
parent | e66cbbe44f3708e6d6a30b216035bcccfc8e7207 (diff) | |
download | libbrandt-c50392f9df44b99263c3481b7b4dc7ae890dc4a8.tar.gz libbrandt-c50392f9df44b99263c3481b7b4dc7ae890dc4a8.zip |
gp-scripts: add zkp + test parameters
-rw-r--r-- | gp-scripts/firstPrice | 95 | ||||
-rw-r--r-- | gp-scripts/firstPrice.gp | 186 | ||||
-rw-r--r-- | gp-scripts/group.gp | 15 | ||||
-rw-r--r-- | gp-scripts/smc.gp | 16 | ||||
-rw-r--r-- | gp-scripts/zkp.gp | 129 |
5 files changed, 330 insertions, 111 deletions
diff --git a/gp-scripts/firstPrice b/gp-scripts/firstPrice deleted file mode 100644 index c638f4a..0000000 --- a/gp-scripts/firstPrice +++ /dev/null | |||
@@ -1,95 +0,0 @@ | |||
1 | \\ From: "How to obtain full privacy in auctions" (2006) by Felix Brandt pages 19-20 | ||
2 | |||
3 | |||
4 | \\\\\\\\\\\\ | ||
5 | \\ Adapt the following values to your needs | ||
6 | \\\\\\\\\\\\ | ||
7 | |||
8 | \\ amount of bidders | ||
9 | n = 4 | ||
10 | \\ amount of possible prices | ||
11 | k = 2^4 | ||
12 | \\ randomize bids (change to something static, if you like) | ||
13 | bid = vector(n,i,random(k)+1) | ||
14 | \\bid = vector(n,i,n-i+1) \\ first bidder wins | ||
15 | \\bid = vector(n,i,i) \\ last bidder wins | ||
16 | \\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties) | ||
17 | |||
18 | \\ prime finite field setup (result may be ambiguous if your prime is too small, 4*n*k seems to work fine) | ||
19 | \\q = prime(4*n*k) | ||
20 | \\ 2048bit prime: | ||
21 | \\q = 31905233907400964621684499856844075173802000556075101303613351426740101897961025481077892281365444367883091980681462491724119317344478120131982416132058173572772607966572720945691237876256074322291459510766147107539260048324345382562673904236506104922357079761457605045674628331006193183908801308817507027556440703972646885207099302085383887085776295396030033300833460743425162726394704256227108175491673135830378272029374848904772902525385997099641162537271298634032011458617811670193865244028195169383991286227040469186123958053863978710424421008752927011390777187889943940479064193231486057910586526439884046593027 | ||
22 | \\ 3072bit prime: | ||
23 | q = 5175054779340588353586849786144680366505563673837334790820581054294754700842534366479020240016540005621125885927641963390708863183739793208880756653713659686139600715884857385144475261507869935694699816011948585170171332029002674283854825650901258017026965486602158722052719421343475066067509485302858041368266332080773331946039572497794442067057597327877030322029413318847025776818839927761556478107499002213648377029201340152459685610920194363099878398871001275336711869213616313858200583491913270052111910410231060407633125816386053759634073500319223989240814564691163285769745840521560940666058800931070258886096469889796899266014106833050284032035948051974659796051419431527095503586817863043771919051402039741075037010264761045992285666560487072740505566408086913711094879155498223636912657852688296081316652278801546924079650897913388978423388839346058027184069633227966507908979049369500450630036982661231208087459099 | ||
24 | |||
25 | \\\\\\\\\\\\ | ||
26 | \\ SETUP | ||
27 | \\\\\\\\\\\\ | ||
28 | |||
29 | \\ p not needed? wat? | ||
30 | \\p = 47 | ||
31 | |||
32 | \\ get generator / primitive element for Z_q | ||
33 | \\ var = 'x \\ copy pasta from internet | ||
34 | \\ pe=ffgen(minpoly(ffprimroot(ffgen(ffinit(q,1))),var),var) \\ get primitive element | ||
35 | \\ 1/(fforder(pe) == q-1) \\ error out, if ord(pe) is wrong | ||
36 | \\ g = Mod(eval(Str(pe)), q) \\ dirty hack to convert t_FFELEM to t_INT | ||
37 | g = Mod(2, q) | ||
38 | |||
39 | \\\\\\\\\\\\ | ||
40 | \\ PROLOG | ||
41 | \\\\\\\\\\\\ | ||
42 | |||
43 | \\ private keys of agents | ||
44 | x = vector(n,i,random(q)) | ||
45 | \\ public keyshares of agents | ||
46 | yshares = vector(n,i,g^x[i]) | ||
47 | \\ shared public key | ||
48 | y = prod(X=1,n,yshares[X]) | ||
49 | |||
50 | \\ first index level = owning agent id (additive share) | ||
51 | \\ second index level = agent id, price id | ||
52 | m = vector(n,i,matrix(n,k,a,b,random(q))) | ||
53 | |||
54 | \\ index = owning agent id, price id | ||
55 | r = matrix(n,k,i,j,random(q)) | ||
56 | \\ bid matrix | ||
57 | b = matrix(n,k,i,j,g^(bid[i]==j)) | ||
58 | |||
59 | \\\\\\\\\\\\ | ||
60 | \\ ROUND1 | ||
61 | \\\\\\\\\\\\ | ||
62 | |||
63 | \\ encrypted bids | ||
64 | alpha = matrix(n,k,i,j, b[i,j]*y^r[i,j]) | ||
65 | beta = matrix(n,k,i,j, g^r[i,j]) | ||
66 | |||
67 | \\\\\\\\\\\\ | ||
68 | \\ ROUND2 | ||
69 | \\\\\\\\\\\\ | ||
70 | |||
71 | \\ multiplicative shares | ||
72 | \\ first index level = owning agent id (multiplicative share) | ||
73 | \\ second index level = agent id, price id | ||
74 | Gamma = vector(n,a,matrix(n,k,i,j, ( prod(h=1,n,prod(d=j+1,k,alpha[h,d])) * prod(d=1,j-1,alpha[i,d]) * prod(h=1,i-1,alpha[h,j]) )^m[a][i,j] )) | ||
75 | Delta = vector(n,a,matrix(n,k,i,j, ( prod(h=1,n,prod(d=j+1,k, beta[h,d])) * prod(d=1,j-1, beta[i,d]) * prod(h=1,i-1, beta[h,j]) )^m[a][i,j] )) | ||
76 | |||
77 | \\\\\\\\\\\\ | ||
78 | \\ ROUND3 | ||
79 | \\\\\\\\\\\\ | ||
80 | |||
81 | \\ multiplicative shares (decryption) | ||
82 | \\ first index level = owning agent id (multiplicative share) | ||
83 | \\ second index level = agent id, price id | ||
84 | Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j])^x[a] )) | ||
85 | |||
86 | \\\\\\\\\\\\ | ||
87 | \\ EPILOG | ||
88 | \\\\\\\\\\\\ | ||
89 | |||
90 | \\ winner matrix | ||
91 | v = matrix(n,k,a,j, prod(i=1,n,Gamma[i][a,j]) / prod(i=1,n,Phi[i][a,j]) ) | ||
92 | vi = lift(v) | ||
93 | |||
94 | print("bids are: ", bid) | ||
95 | for(X=1,n, if(vecmin(vi[X,])==1, print("And the winner is ", X) )) | ||
diff --git a/gp-scripts/firstPrice.gp b/gp-scripts/firstPrice.gp new file mode 100644 index 0000000..5642fa0 --- /dev/null +++ b/gp-scripts/firstPrice.gp | |||
@@ -0,0 +1,186 @@ | |||
1 | \\ From: "How to obtain full privacy in auctions" (2006) by Felix Brandt pages 19-20 | ||
2 | |||
3 | |||
4 | \\\\\\\\\\\\ | ||
5 | \\ Adapt the following values to your needs | ||
6 | \\\\\\\\\\\\ | ||
7 | |||
8 | \\ amount of bidders | ||
9 | n = 3 | ||
10 | \\ amount of possible prices | ||
11 | k = 2^2 | ||
12 | \\ randomize bids (change to something static, if you like) | ||
13 | bid = vector(n,i,random(k)+1) | ||
14 | \\bid = vector(n,i,n-i+1) \\ first bidder wins | ||
15 | \\bid = vector(n,i,i) \\ last bidder wins | ||
16 | \\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties) | ||
17 | |||
18 | \\\\\\\\\\\\ | ||
19 | \\ SETUP | ||
20 | \\\\\\\\\\\\ | ||
21 | |||
22 | read(group) | ||
23 | read(zkp) | ||
24 | |||
25 | \\\\\\\\\\\\ | ||
26 | \\ PROLOG | ||
27 | \\\\\\\\\\\\ | ||
28 | |||
29 | \\ private keys of agents | ||
30 | x = vector(n,i,random(q)) | ||
31 | \\ first index level = owning agent id (additive share) | ||
32 | \\ second index level = agent id, price id | ||
33 | m = vector(n,i,matrix(n,k,a,b,random(q))) | ||
34 | |||
35 | \\ zkp | ||
36 | proofs1 = vector(n,i,zkp1_proof(G, x[i])) | ||
37 | |||
38 | \\ public keyshares of agents | ||
39 | yshares = vector(n,i,proofs1[i][4]) | ||
40 | \\yshares = vector(n,i,G^x[i]) | ||
41 | |||
42 | \\ for performance evaluations we need to check the proofs for every bidder | ||
43 | \\ i := checking bidder (0 == seller) | ||
44 | \\ h := bidder to check | ||
45 | { | ||
46 | for(i=0,n, | ||
47 | for(h=1,n, | ||
48 | if(1 != zkp1_check(proofs1[h]), | ||
49 | error("zkp1 failure in round0") | ||
50 | ) | ||
51 | ) | ||
52 | ) | ||
53 | } | ||
54 | |||
55 | \\ shared public key | ||
56 | y = prod(X=1,n,yshares[X]) | ||
57 | |||
58 | \\\\\\\\\\\\ | ||
59 | \\ ROUND1 | ||
60 | \\\\\\\\\\\\ | ||
61 | |||
62 | \\ bid matrix | ||
63 | b = matrix(n,k,i,j,G^(bid[i]==j)) | ||
64 | |||
65 | \\ zkp | ||
66 | proofs3 = matrix(n,k,i,j, zkp3_proof(G,y,G^(bid[i]==j))) | ||
67 | |||
68 | \\ index = owning agent id, price id | ||
69 | r = matrix(n,k,i,j,proofs3[i,j][13]) | ||
70 | \\r = matrix(n,k,i,j,random(q)) | ||
71 | |||
72 | \\ encrypted bids | ||
73 | Alpha = matrix(n,k,i,j, proofs3[i,j][3]) | ||
74 | Beta = matrix(n,k,i,j, proofs3[i,j][4]) | ||
75 | \\Alpha = matrix(n,k,i,j, b[i,j]*y^r[i,j]) | ||
76 | \\Beta = matrix(n,k,i,j, G^r[i,j]) | ||
77 | |||
78 | proofs2 = vector(n,i, zkp2_proof(y,G,sum(j=1,k, r[i,j]))) | ||
79 | \\ i := checking bidder (0 == seller) | ||
80 | \\ h := bidder to check | ||
81 | \\ j := price index to check | ||
82 | { | ||
83 | for(i=0,n, | ||
84 | for(h=1,n, | ||
85 | for(j=1,k, | ||
86 | if(1 != zkp3_check(proofs3[h,j]), | ||
87 | error("zkp3 failure in round1") | ||
88 | ) | ||
89 | ); | ||
90 | if((prod(j=1,k,Alpha[h,j])/G) != proofs2[h][6], | ||
91 | error("alpha product doesn't match") | ||
92 | ); | ||
93 | if(prod(j=1,k,Beta[h,j]) != proofs2[h][7], | ||
94 | error("beta product doesn't match") | ||
95 | ); | ||
96 | if(1 != zkp2_check(proofs2[h]), | ||
97 | error("zkp2 failure in round1") | ||
98 | ) | ||
99 | ) | ||
100 | ) | ||
101 | } | ||
102 | |||
103 | \\\\\\\\\\\\ | ||
104 | \\ ROUND2 | ||
105 | \\\\\\\\\\\\ | ||
106 | |||
107 | \\ multiplicative shares | ||
108 | \\ first index level = owning agent id (multiplicative share) | ||
109 | \\ second index level = agent id, price id | ||
110 | Gamma = vector(n,a,matrix(n,k,i,j, prod(h=1,n,prod(d=j+1,k,Alpha[h,d])) * prod(d=1,j-1,Alpha[i,d]) * prod(h=1,i-1,Alpha[h,j]) )) | ||
111 | Delta = vector(n,a,matrix(n,k,i,j, prod(h=1,n,prod(d=j+1,k, Beta[h,d])) * prod(d=1,j-1, Beta[i,d]) * prod(h=1,i-1, Beta[h,j]) )) | ||
112 | \\Gamma = vector(n,a,matrix(n,k,i,j, ( prod(h=1,n,prod(d=j+1,k,Alpha[h,d])) * prod(d=1,j-1,Alpha[i,d]) * prod(h=1,i-1,Alpha[h,j]) )^m[a][i,j] )) | ||
113 | \\Delta = vector(n,a,matrix(n,k,i,j, ( prod(h=1,n,prod(d=j+1,k, Beta[h,d])) * prod(d=1,j-1, Beta[i,d]) * prod(h=1,i-1, Beta[h,j]) )^m[a][i,j] )) | ||
114 | |||
115 | \\ random masking and zkp | ||
116 | proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Gamma[a][i,j], Delta[a][i,j], random(q)) )) | ||
117 | |||
118 | \\ for performance evaluations we need to check the proofs for every bidder | ||
119 | \\ i := checking bidder (0 == seller) | ||
120 | \\ h := bidder to check | ||
121 | \\ t := target bidder (creator of the proof) | ||
122 | \\ j := price | ||
123 | { | ||
124 | for(t=1,n, | ||
125 | for(h=1,n, | ||
126 | for(j=1,k, | ||
127 | for(i=0,n, | ||
128 | if(1 != zkp2_check(proofs2[t][h,j]), | ||
129 | error("zkp2 failure in round2") | ||
130 | ) | ||
131 | ); | ||
132 | \\ use masked values generated during the zkp | ||
133 | Gamma[t][h,j] = proofs2[t][h,j][6]; | ||
134 | Delta[t][h,j] = proofs2[t][h,j][7]; | ||
135 | ) | ||
136 | ) | ||
137 | ) | ||
138 | } | ||
139 | |||
140 | |||
141 | \\\\\\\\\\\\ | ||
142 | \\ ROUND3 | ||
143 | \\\\\\\\\\\\ | ||
144 | |||
145 | \\ multiplicative shares (decryption) | ||
146 | \\ first index level = owning agent id (multiplicative share) | ||
147 | \\ second index level = agent id, price id | ||
148 | Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j]) )) | ||
149 | \\Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j])^x[a] )) | ||
150 | |||
151 | proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Phi[a][i,j], G, x[a]) )) | ||
152 | |||
153 | \\ for performance evaluations we need to check the proofs for every bidder | ||
154 | \\ i := checking bidder (0 == seller) | ||
155 | \\ h := bidder to check | ||
156 | \\ t := target bidder (creator of the proof) | ||
157 | \\ j := price | ||
158 | { | ||
159 | for(t=1,n, | ||
160 | for(h=1,n, | ||
161 | for(j=1,k, | ||
162 | for(i=0,n, | ||
163 | if(1 != zkp2_check(proofs2[t][h,j]), | ||
164 | error("zkp2 failure in round2") | ||
165 | ) | ||
166 | ); | ||
167 | \\ use masked values generated during the zkp | ||
168 | Phi[t][h,j] = proofs2[t][h,j][6]; | ||
169 | ) | ||
170 | ) | ||
171 | ) | ||
172 | } | ||
173 | |||
174 | |||
175 | \\\\\\\\\\\\ | ||
176 | \\ EPILOG | ||
177 | \\\\\\\\\\\\ | ||
178 | |||
179 | \\ winner matrix | ||
180 | v = matrix(n,k,a,j, prod(i=1,n,Gamma[i][a,j]) / prod(i=1,n,Phi[i][a,j]) ) | ||
181 | vi = lift(v) | ||
182 | |||
183 | print("bids are: ", bid) | ||
184 | for(X=1,n, if(vecmin(vi[X,])==1, print("And the winner is ", X) )) | ||
185 | |||
186 | ; | ||
diff --git a/gp-scripts/group.gp b/gp-scripts/group.gp new file mode 100644 index 0000000..3f941b8 --- /dev/null +++ b/gp-scripts/group.gp | |||
@@ -0,0 +1,15 @@ | |||
1 | \\ p generated by ssh-keygen from the following moduli(5) line: | ||
2 | \\ 20161024184335 2 6 100 3071 2 C63A6E912985E56A40FA7747D856C9FFD01B052F0BDEA89F0B17C34EC168E918FCC6121351CA0003453E96EBB5CE228D97610D0F7AA0EE1EC26124723BDA68607D0348B30A39B92DFBB4E23219DA3440756C169A4F1B929DDB487CF2C53520910C800340DE87CA65D2041FA393FD0D25019589B7ED89D0AD256764FF690B122FC868ED5E314346CA93505700B650BDD74D6395767E67AA4E29517699A2170892B572EC6050FD4F0545FE981D9583CD47411788ADFD7C60B33E6A186FCAE5ACAF8CE012B5551A3A54B15AA28D4F7C3EF37220819CA180B3BA855D816FF5D3AC0A8D2AB4E0C9D638C785F0E2707B591326A6E657F3E26D9EEDE5760E81165B0B3680ADA447AFE0A31EA9A31CC1825EB9B36AF746FB579A0A327AEF54D16B1C7A1575A241139F9B8551EA3C687E2E333ABDA9E5F491CA7F1611E478F8B4FA74E34A6771374198FE337634E8B0021BA826BF332818BB43052B6BC6D84E4E34BD1ABEC166881CC69079ED1F306C7143C5F9E341C6955DD501ED51FCE5F7F94CFA6273 | ||
3 | \\ This is a "safe prime", see moduli(5) | ||
4 | \\ Therefore q = (p-1)/2 is also prime | ||
5 | |||
6 | p = 4498546982183741806042046874925230841367752610105215768946438255470120740195522849201856997179866815126313339756915558167423398334072639778026401904031844016861682960881473450120265256327641310709437833580886250441164652551031655405301329413885250587408573319621138304678094611598436119854035881555472079889364307701983275427495796082239390426306590239630071293304476993188112145295406185504400770379250448236759388051149856191572199475958274963892549036586332373555561624378385324018563641781073722121282924048194073332885386583853286835384896286468480594489851988635137146304050743119406030150457214703115428415028345445439080824905967347767410065096124691155434106090788541491301971510767072678641286317388382884979008351941634738407020421109176416998181365911697340148847292136114015951382836045342314909586957351991419538245920973429697625016569947794803114551396527414933624103391788313038751051589980762413698400281203 | ||
7 | |||
8 | \\ From that we can compute the subgroup-order prime q: | ||
9 | q = (p-1)/2 | ||
10 | |||
11 | \\ Cyclic Subgroups of Z_p must have order 1, 2, q or p-1 | ||
12 | \\ => The generator of Subgroup Z_p^* is 3 as we can check with G^q == Mod(1, p) | ||
13 | G = Mod(3, p) | ||
14 | |||
15 | ; | ||
diff --git a/gp-scripts/smc.gp b/gp-scripts/smc.gp index 2b7e188..f32f5f2 100644 --- a/gp-scripts/smc.gp +++ b/gp-scripts/smc.gp | |||
@@ -17,19 +17,3 @@ smc_hextodec(s:str) = | |||
17 | ret; | 17 | ret; |
18 | } | 18 | } |
19 | 19 | ||
20 | smc_genbid(k:small, bid:small, g)= | ||
21 | { | ||
22 | vector(k,j,g^(bid==j)); | ||
23 | } | ||
24 | |||
25 | smc_genalpha(k:small, b:vec, r:vec, y)= | ||
26 | { | ||
27 | vector(k, j, b[j]*y^r[j]); | ||
28 | } | ||
29 | |||
30 | smc_genbeta(k:small, r:vec, g)= | ||
31 | { | ||
32 | vector(k, j, g^r[j]); | ||
33 | } | ||
34 | |||
35 | |||
diff --git a/gp-scripts/zkp.gp b/gp-scripts/zkp.gp new file mode 100644 index 0000000..9bf7b7d --- /dev/null +++ b/gp-scripts/zkp.gp | |||
@@ -0,0 +1,129 @@ | |||
1 | \\ zero knowledge proofs | ||
2 | |||
3 | read(group); | ||
4 | |||
5 | \\ Don't use in production code! | ||
6 | \\ This is a very stupid implementation only used in performance evaluation. | ||
7 | kdf(in:vec) = | ||
8 | { | ||
9 | prod(h=1,length(in),lift(in[h]))%q | ||
10 | } | ||
11 | |||
12 | |||
13 | zkp1_proof(G:intmod, x:int) = | ||
14 | { | ||
15 | local(V:intmod, z:int, A:intmod, c:int, r:int); | ||
16 | V = G^x; | ||
17 | z = random(q); | ||
18 | A = G^z; | ||
19 | c = kdf([G, V, A]); | ||
20 | r = (z+c*x)%q; | ||
21 | [G, r, A, V] | ||
22 | } | ||
23 | |||
24 | zkp1_check(P:vec) = | ||
25 | { | ||
26 | local(c:int, G:intmod, r:int, A:intmod, V:intmod); | ||
27 | if (length(P) < 4, error("Proof1 too short.")); | ||
28 | if (type(P[1]) == "t_INTMOD", G = P[1], error("P[1] has wrong type.")); | ||
29 | if (type(P[2]) == "t_INT", r = P[2], error("P[2] has wrong type.")); | ||
30 | if (type(P[3]) == "t_INTMOD", A = P[3], error("P[3] has wrong type.")); | ||
31 | if (type(P[4]) == "t_INTMOD", V = P[4], error("P[4] has wrong type.")); | ||
32 | c = kdf([G, V, A]); | ||
33 | G^r == A*V^c | ||
34 | } | ||
35 | |||
36 | |||
37 | zkp2_proof(G1:intmod, G2:intmod, x:int) = | ||
38 | { | ||
39 | local(V:intmod, W:intmod, z:int, A:intmod, B:intmod, c:int, r:int); | ||
40 | V = G1^x; | ||
41 | W = G2^x; | ||
42 | z = random(q); | ||
43 | A = G1^z; | ||
44 | B = G2^z; | ||
45 | c = kdf([G1, G2, V, W, A, B]); | ||
46 | r = (z+c*x)%q; | ||
47 | [G1, G2, r, A, B, V, W] | ||
48 | } | ||
49 | |||
50 | zkp2_check(P:vec) = | ||
51 | { | ||
52 | local(c:int, | ||
53 | G1:intmod, G2:intmod, r:int, A:intmod, B:intmod, V:intmod, W:intmod); | ||
54 | if (length(P) < 7, error("Proof2 too short.")); | ||
55 | if (type(P[1]) == "t_INTMOD", G1 = P[1], error("P[1] has wrong type.")); | ||
56 | if (type(P[2]) == "t_INTMOD", G2 = P[2], error("P[2] has wrong type.")); | ||
57 | if (type(P[3]) == "t_INT", r = P[3], error("P[3] has wrong type.")); | ||
58 | if (type(P[4]) == "t_INTMOD", A = P[4], error("P[4] has wrong type.")); | ||
59 | if (type(P[5]) == "t_INTMOD", B = P[5], error("P[5] has wrong type.")); | ||
60 | if (type(P[6]) == "t_INTMOD", V = P[6], error("P[6] has wrong type.")); | ||
61 | if (type(P[7]) == "t_INTMOD", W = P[7], error("P[7] has wrong type.")); | ||
62 | c = kdf([G1, G2, V, W, A, B]); | ||
63 | G1^r == A*V^c && G2^r == B*W^c | ||
64 | } | ||
65 | |||
66 | |||
67 | zkp3_proof(G:intmod, Y:intmod, M:intmod) = | ||
68 | { | ||
69 | local(Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod, | ||
70 | d1:int, d2:int, r1:int, r2:int, w:int, r:int); | ||
71 | r = random(q); | ||
72 | Alpha = M*Y^r; | ||
73 | Beta = G^r; | ||
74 | if (M == Mod(1, p), | ||
75 | d1 = random(q); | ||
76 | r1 = random(q); | ||
77 | w = random(q); | ||
78 | A1 = G^r1 * Beta^d1; | ||
79 | B1 = Y^r1 * (Alpha / G)^d1; | ||
80 | A2 = G^w; | ||
81 | B2 = Y^w; | ||
82 | c = kdf([G, Alpha, Beta, A1, A2, B1, B2]); | ||
83 | d2 = (c - d1) % q; | ||
84 | r2 = (w - r*d2) % q; | ||
85 | , | ||
86 | if (M == G, | ||
87 | d2 = random(q); | ||
88 | r2 = random(q); | ||
89 | w = random(q); | ||
90 | A1 = G^w; | ||
91 | B1 = Y^w; | ||
92 | A2 = G^r2 * Beta^d2; | ||
93 | B2 = Y^r2 * Alpha^d2; | ||
94 | c = kdf([G, Alpha, Beta, A1, A2, B1, B2]); | ||
95 | d1 = (c - d2) % q; | ||
96 | r1 = (w - r*d1) % q; | ||
97 | , error("M is neither 1 nor G") | ||
98 | ) | ||
99 | ); | ||
100 | [G, Y, Alpha, Beta, A1, A2, B1, B2, d1, d2, r1, r2, r] | ||
101 | } | ||
102 | |||
103 | zkp3_check(P:vec) = | ||
104 | { | ||
105 | local(c:int, | ||
106 | G:intmod, Y:intmod, Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod, | ||
107 | d1:int, d2:int, r1:int, r2:int); | ||
108 | if (length(P) < 12, error("Proof3 too short.")); | ||
109 | if (type(P[1] ) == "t_INTMOD", G = P[1], error("P[1] has wrong type.")); | ||
110 | if (type(P[2] ) == "t_INTMOD", Y = P[2], error("P[2] has wrong type.")); | ||
111 | if (type(P[3] ) == "t_INTMOD", Alpha = P[3], error("P[3] has wrong type.")); | ||
112 | if (type(P[4] ) == "t_INTMOD", Beta = P[4], error("P[4] has wrong type.")); | ||
113 | if (type(P[5] ) == "t_INTMOD", A1 = P[5], error("P[5] has wrong type.")); | ||
114 | if (type(P[6] ) == "t_INTMOD", A2 = P[6], error("P[6] has wrong type.")); | ||
115 | if (type(P[7] ) == "t_INTMOD", B1 = P[7], error("P[7] has wrong type.")); | ||
116 | if (type(P[8] ) == "t_INTMOD", B2 = P[8], error("P[8] has wrong type.")); | ||
117 | if (type(P[9] ) == "t_INT", d1 = P[9], error("P[9] has wrong type.")); | ||
118 | if (type(P[10]) == "t_INT", d2 = P[10], error("P[10] has wrong type.")); | ||
119 | if (type(P[11]) == "t_INT", r1 = P[11], error("P[11] has wrong type.")); | ||
120 | if (type(P[12]) == "t_INT", r2 = P[12], error("P[12] has wrong type.")); | ||
121 | c = kdf([G, Alpha, Beta, A1, A2, B1, B2]); | ||
122 | c == (d1 + d2) % q && | ||
123 | A1 == G^r1 * Beta^d1 && | ||
124 | A2 == G^r2 * Beta^d2 && | ||
125 | B1 == Y^r1 * (Alpha / G)^d1 && | ||
126 | B2 == Y^r2 * Alpha^d2 | ||
127 | } | ||
128 | |||
129 | ; | ||