diff options
-rw-r--r-- | gp-scripts/firstPrice.gp | 308 |
1 files changed, 155 insertions, 153 deletions
diff --git a/gp-scripts/firstPrice.gp b/gp-scripts/firstPrice.gp index 5642fa0..c9d4f0c 100644 --- a/gp-scripts/firstPrice.gp +++ b/gp-scripts/firstPrice.gp | |||
@@ -6,11 +6,11 @@ | |||
6 | \\\\\\\\\\\\ | 6 | \\\\\\\\\\\\ |
7 | 7 | ||
8 | \\ amount of bidders | 8 | \\ amount of bidders |
9 | n = 3 | 9 | \\n = 3 |
10 | \\ amount of possible prices | 10 | \\ amount of possible prices |
11 | k = 2^2 | 11 | \\k = 2^2 |
12 | \\ randomize bids (change to something static, if you like) | 12 | \\ randomize bids (change to something static, if you like) |
13 | bid = vector(n,i,random(k)+1) | 13 | \\bid = vector(n,i,random(k)+1) |
14 | \\bid = vector(n,i,n-i+1) \\ first bidder wins | 14 | \\bid = vector(n,i,n-i+1) \\ first bidder wins |
15 | \\bid = vector(n,i,i) \\ last bidder wins | 15 | \\bid = vector(n,i,i) \\ last bidder wins |
16 | \\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties) | 16 | \\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties) |
@@ -19,168 +19,170 @@ bid = vector(n,i,random(k)+1) | |||
19 | \\ SETUP | 19 | \\ SETUP |
20 | \\\\\\\\\\\\ | 20 | \\\\\\\\\\\\ |
21 | 21 | ||
22 | read(group) | 22 | read(group); |
23 | read(zkp) | 23 | read(zkp); |
24 | 24 | ||
25 | \\\\\\\\\\\\ | 25 | fp_priv(bids:vec, k:int) = |
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 | { | 26 | { |
46 | for(i=0,n, | 27 | local(n:int = length(bids)); |
47 | for(h=1,n, | 28 | |
48 | if(1 != zkp1_check(proofs1[h]), | 29 | \\\\\\\\\\\\ |
49 | error("zkp1 failure in round0") | 30 | \\ PROLOG |
50 | ) | 31 | \\\\\\\\\\\\ |
51 | ) | 32 | |
52 | ) | 33 | \\ private keys of agents |
53 | } | 34 | x = vector(n,i,random(q)); |
54 | 35 | \\ first index level = owning agent id (additive share) | |
55 | \\ shared public key | 36 | \\ second index level = agent id, price id |
56 | y = prod(X=1,n,yshares[X]) | 37 | m = vector(n,i,matrix(n,k,a,b,random(q))); |
57 | 38 | ||
58 | \\\\\\\\\\\\ | 39 | \\ zkp |
59 | \\ ROUND1 | 40 | proofs1 = vector(n,i,zkp1_proof(G, x[i])); |
60 | \\\\\\\\\\\\ | 41 | |
61 | 42 | \\ public keyshares of agents | |
62 | \\ bid matrix | 43 | yshares = vector(n,i,proofs1[i][4]); |
63 | b = matrix(n,k,i,j,G^(bid[i]==j)) | 44 | \\yshares = vector(n,i,G^x[i]) |
64 | 45 | ||
65 | \\ zkp | 46 | \\ for performance evaluations we need to check the proofs for every bidder |
66 | proofs3 = matrix(n,k,i,j, zkp3_proof(G,y,G^(bid[i]==j))) | 47 | \\ i := checking bidder (0 == seller) |
67 | 48 | \\ h := bidder to check | |
68 | \\ index = owning agent id, price id | 49 | for(i=0,n, |
69 | r = matrix(n,k,i,j,proofs3[i,j][13]) | 50 | for(h=1,n, |
70 | \\r = matrix(n,k,i,j,random(q)) | 51 | if(1 != zkp1_check(proofs1[h]), |
71 | 52 | error("zkp1 failure in round0") | |
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 | ) | 53 | ) |
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 | ) | 54 | ) |
99 | ) | 55 | ); |
100 | ) | 56 | |
101 | } | 57 | \\ shared public key |
102 | 58 | y = prod(X=1,n,yshares[X]); | |
103 | \\\\\\\\\\\\ | 59 | |
104 | \\ ROUND2 | 60 | \\\\\\\\\\\\ |
105 | \\\\\\\\\\\\ | 61 | \\ ROUND1 |
106 | 62 | \\\\\\\\\\\\ | |
107 | \\ multiplicative shares | 63 | |
108 | \\ first index level = owning agent id (multiplicative share) | 64 | \\ bid matrix |
109 | \\ second index level = agent id, price id | 65 | b = matrix(n,k,i,j,G^(bids[i]==j)); |
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]) )) | 66 | |
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]) )) | 67 | \\ zkp |
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] )) | 68 | proofs3 = matrix(n,k,i,j, zkp3_proof(G,y,G^(bids[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] )) | 69 | |
114 | 70 | \\ index = owning agent id, price id | |
115 | \\ random masking and zkp | 71 | r = matrix(n,k,i,j,proofs3[i,j][13]); |
116 | proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Gamma[a][i,j], Delta[a][i,j], random(q)) )) | 72 | \\r = matrix(n,k,i,j,random(q)) |
117 | 73 | ||
118 | \\ for performance evaluations we need to check the proofs for every bidder | 74 | \\ encrypted bids |
119 | \\ i := checking bidder (0 == seller) | 75 | Alpha = matrix(n,k,i,j, proofs3[i,j][3]); |
120 | \\ h := bidder to check | 76 | Beta = matrix(n,k,i,j, proofs3[i,j][4]); |
121 | \\ t := target bidder (creator of the proof) | 77 | \\Alpha = matrix(n,k,i,j, b[i,j]*y^r[i,j]) |
122 | \\ j := price | 78 | \\Beta = matrix(n,k,i,j, G^r[i,j]) |
123 | { | 79 | |
124 | for(t=1,n, | 80 | proofs2 = vector(n,i, zkp2_proof(y,G,sum(j=1,k, r[i,j]))); |
125 | for(h=1,n, | 81 | \\ i := checking bidder (0 == seller) |
126 | for(j=1,k, | 82 | \\ h := bidder to check |
127 | for(i=0,n, | 83 | \\ j := price index to check |
128 | if(1 != zkp2_check(proofs2[t][h,j]), | 84 | for(i=0,n, |
129 | error("zkp2 failure in round2") | 85 | for(h=1,n, |
86 | for(j=1,k, | ||
87 | if(1 != zkp3_check(proofs3[h,j]), | ||
88 | error("zkp3 failure in round1") | ||
130 | ) | 89 | ) |
131 | ); | 90 | ); |
132 | \\ use masked values generated during the zkp | 91 | if((prod(j=1,k,Alpha[h,j])/G) != proofs2[h][6], |
133 | Gamma[t][h,j] = proofs2[t][h,j][6]; | 92 | error("alpha product doesn't match") |
134 | Delta[t][h,j] = proofs2[t][h,j][7]; | 93 | ); |
94 | if(prod(j=1,k,Beta[h,j]) != proofs2[h][7], | ||
95 | error("beta product doesn't match") | ||
96 | ); | ||
97 | if(1 != zkp2_check(proofs2[h]), | ||
98 | error("zkp2 failure in round1") | ||
99 | ) | ||
135 | ) | 100 | ) |
136 | ) | 101 | ); |
137 | ) | 102 | |
138 | } | 103 | \\\\\\\\\\\\ |
139 | 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 | for(t=1,n, | ||
124 | for(h=1,n, | ||
125 | for(j=1,k, | ||
126 | for(i=0,n, | ||
127 | if(1 != zkp2_check(proofs2[t][h,j]), | ||
128 | error("zkp2 failure in round2") | ||
129 | ) | ||
130 | ); | ||
131 | \\ use masked values generated during the zkp | ||
132 | Gamma[t][h,j] = proofs2[t][h,j][6]; | ||
133 | Delta[t][h,j] = proofs2[t][h,j][7]; | ||
134 | ) | ||
135 | ) | ||
136 | ); | ||
137 | |||
138 | |||
139 | \\\\\\\\\\\\ | ||
140 | \\ ROUND3 | ||
141 | \\\\\\\\\\\\ | ||
142 | |||
143 | \\ multiplicative shares (decryption) | ||
144 | \\ first index level = owning agent id (multiplicative share) | ||
145 | \\ second index level = agent id, price id | ||
146 | Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j]) )); | ||
147 | \\Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j])^x[a] )) | ||
148 | |||
149 | proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Phi[a][i,j], G, x[a]) )); | ||
150 | |||
151 | \\ for performance evaluations we need to check the proofs for every bidder | ||
152 | \\ i := checking bidder (0 == seller) | ||
153 | \\ h := bidder to check | ||
154 | \\ t := target bidder (creator of the proof) | ||
155 | \\ j := price | ||
156 | for(t=1,n, | ||
157 | for(h=1,n, | ||
158 | for(j=1,k, | ||
159 | for(i=0,n, | ||
160 | if(1 != zkp2_check(proofs2[t][h,j]), | ||
161 | error("zkp2 failure in round2") | ||
162 | ) | ||
163 | ); | ||
164 | \\ use masked values generated during the zkp | ||
165 | Phi[t][h,j] = proofs2[t][h,j][6]; | ||
166 | ) | ||
167 | ) | ||
168 | ); | ||
140 | 169 | ||
141 | \\\\\\\\\\\\ | ||
142 | \\ ROUND3 | ||
143 | \\\\\\\\\\\\ | ||
144 | 170 | ||
145 | \\ multiplicative shares (decryption) | 171 | \\\\\\\\\\\\ |
146 | \\ first index level = owning agent id (multiplicative share) | 172 | \\ EPILOG |
147 | \\ second index level = agent id, price id | 173 | \\\\\\\\\\\\ |
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 | 174 | ||
151 | proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Phi[a][i,j], G, x[a]) )) | 175 | \\ winner matrix |
176 | v = matrix(n,k,a,j, prod(i=1,n,Gamma[i][a,j]) / prod(i=1,n,Phi[i][a,j]) ); | ||
177 | vi = lift(v); | ||
152 | 178 | ||
153 | \\ for performance evaluations we need to check the proofs for every bidder | 179 | print("bids are: ", bids); |
154 | \\ i := checking bidder (0 == seller) | 180 | for(X=1,n, |
155 | \\ h := bidder to check | 181 | if(vecmin(vi[X,])==1, |
156 | \\ t := target bidder (creator of the proof) | 182 | print("And the winner is ", X) |
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 | ) | 183 | ) |
170 | ) | 184 | ); |
171 | ) | ||
172 | } | ||
173 | |||
174 | 185 | ||
175 | \\\\\\\\\\\\ | 186 | } |
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 | 187 | ||
186 | ; | 188 | ; |