diff options
Diffstat (limited to 'gp-scripts/firstPrice.gp')
| -rw-r--r-- | gp-scripts/firstPrice.gp | 186 |
1 files changed, 186 insertions, 0 deletions
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 @@ +\\ From: "How to obtain full privacy in auctions" (2006) by Felix Brandt pages 19-20 + + +\\\\\\\\\\\\ +\\ Adapt the following values to your needs +\\\\\\\\\\\\ + +\\ amount of bidders +n = 3 +\\ amount of possible prices +k = 2^2 +\\ randomize bids (change to something static, if you like) +bid = vector(n,i,random(k)+1) +\\bid = vector(n,i,n-i+1) \\ first bidder wins +\\bid = vector(n,i,i) \\ last bidder wins +\\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties) + +\\\\\\\\\\\\ +\\ SETUP +\\\\\\\\\\\\ + +read(group) +read(zkp) + +\\\\\\\\\\\\ +\\ PROLOG +\\\\\\\\\\\\ + +\\ private keys of agents +x = vector(n,i,random(q)) +\\ first index level = owning agent id (additive share) +\\ second index level = agent id, price id +m = vector(n,i,matrix(n,k,a,b,random(q))) + +\\ zkp +proofs1 = vector(n,i,zkp1_proof(G, x[i])) + +\\ public keyshares of agents +yshares = vector(n,i,proofs1[i][4]) +\\yshares = vector(n,i,G^x[i]) + +\\ for performance evaluations we need to check the proofs for every bidder +\\ i := checking bidder (0 == seller) +\\ h := bidder to check +{ +for(i=0,n, + for(h=1,n, + if(1 != zkp1_check(proofs1[h]), + error("zkp1 failure in round0") + ) + ) +) +} + +\\ shared public key +y = prod(X=1,n,yshares[X]) + +\\\\\\\\\\\\ +\\ ROUND1 +\\\\\\\\\\\\ + +\\ bid matrix +b = matrix(n,k,i,j,G^(bid[i]==j)) + +\\ zkp +proofs3 = matrix(n,k,i,j, zkp3_proof(G,y,G^(bid[i]==j))) + +\\ index = owning agent id, price id +r = matrix(n,k,i,j,proofs3[i,j][13]) +\\r = matrix(n,k,i,j,random(q)) + +\\ encrypted bids +Alpha = matrix(n,k,i,j, proofs3[i,j][3]) +Beta = matrix(n,k,i,j, proofs3[i,j][4]) +\\Alpha = matrix(n,k,i,j, b[i,j]*y^r[i,j]) +\\Beta = matrix(n,k,i,j, G^r[i,j]) + +proofs2 = vector(n,i, zkp2_proof(y,G,sum(j=1,k, r[i,j]))) +\\ i := checking bidder (0 == seller) +\\ h := bidder to check +\\ j := price index to check +{ +for(i=0,n, + for(h=1,n, + for(j=1,k, + if(1 != zkp3_check(proofs3[h,j]), + error("zkp3 failure in round1") + ) + ); + if((prod(j=1,k,Alpha[h,j])/G) != proofs2[h][6], + error("alpha product doesn't match") + ); + if(prod(j=1,k,Beta[h,j]) != proofs2[h][7], + error("beta product doesn't match") + ); + if(1 != zkp2_check(proofs2[h]), + error("zkp2 failure in round1") + ) + ) +) +} + +\\\\\\\\\\\\ +\\ ROUND2 +\\\\\\\\\\\\ + +\\ multiplicative shares +\\ first index level = owning agent id (multiplicative share) +\\ second index level = agent id, price id +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]) )) +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]) )) +\\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] )) +\\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] )) + +\\ random masking and zkp +proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Gamma[a][i,j], Delta[a][i,j], random(q)) )) + +\\ for performance evaluations we need to check the proofs for every bidder +\\ i := checking bidder (0 == seller) +\\ h := bidder to check +\\ t := target bidder (creator of the proof) +\\ j := price +{ +for(t=1,n, + for(h=1,n, + for(j=1,k, + for(i=0,n, + if(1 != zkp2_check(proofs2[t][h,j]), + error("zkp2 failure in round2") + ) + ); + \\ use masked values generated during the zkp + Gamma[t][h,j] = proofs2[t][h,j][6]; + Delta[t][h,j] = proofs2[t][h,j][7]; + ) + ) +) +} + + +\\\\\\\\\\\\ +\\ ROUND3 +\\\\\\\\\\\\ + +\\ multiplicative shares (decryption) +\\ first index level = owning agent id (multiplicative share) +\\ second index level = agent id, price id +Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j]) )) +\\Phi = vector(n,a,matrix(n,k,i,j, prod(h=1,n,Delta[h][i,j])^x[a] )) + +proofs2 = vector(n,a,matrix(n,k,i,j, zkp2_proof(Phi[a][i,j], G, x[a]) )) + +\\ for performance evaluations we need to check the proofs for every bidder +\\ i := checking bidder (0 == seller) +\\ h := bidder to check +\\ t := target bidder (creator of the proof) +\\ j := price +{ +for(t=1,n, + for(h=1,n, + for(j=1,k, + for(i=0,n, + if(1 != zkp2_check(proofs2[t][h,j]), + error("zkp2 failure in round2") + ) + ); + \\ use masked values generated during the zkp + Phi[t][h,j] = proofs2[t][h,j][6]; + ) + ) +) +} + + +\\\\\\\\\\\\ +\\ EPILOG +\\\\\\\\\\\\ + +\\ winner matrix +v = matrix(n,k,a,j, prod(i=1,n,Gamma[i][a,j]) / prod(i=1,n,Phi[i][a,j]) ) +vi = lift(v) + +print("bids are: ", bid) +for(X=1,n, if(vecmin(vi[X,])==1, print("And the winner is ", X) )) + +; |