aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--gp-scripts/firstPrice.gp308
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
9n = 3 9\\n = 3
10\\ amount of possible prices 10\\ amount of possible prices
11k = 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)
13bid = 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
22read(group) 22read(group);
23read(zkp) 23read(zkp);
24 24
25\\\\\\\\\\\\ 25fp_priv(bids:vec, k:int) =
26\\ PROLOG
27\\\\\\\\\\\\
28
29\\ private keys of agents
30x = vector(n,i,random(q))
31\\ first index level = owning agent id (additive share)
32\\ second index level = agent id, price id
33m = vector(n,i,matrix(n,k,a,b,random(q)))
34
35\\ zkp
36proofs1 = vector(n,i,zkp1_proof(G, x[i]))
37
38\\ public keyshares of agents
39yshares = 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{
46for(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
56y = 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]);
63b = 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
66proofs3 = 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,
69r = 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
73Alpha = matrix(n,k,i,j, proofs3[i,j][3])
74Beta = 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
78proofs2 = 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{
83for(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));
110Gamma = 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
111Delta = 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]);
116proofs2 = 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
124for(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 \\\\\\\\\\\\
148Phi = 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
151proofs2 = 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{
159for(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
180v = matrix(n,k,a,j, prod(i=1,n,Gamma[i][a,j]) / prod(i=1,n,Phi[i][a,j]) )
181vi = lift(v)
182
183print("bids are: ", bid)
184for(X=1,n, if(vecmin(vi[X,])==1, print("And the winner is ", X) ))
185 187
186; 188;