\\ 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); fp_priv(bids:vec, k:int) = { local(n:int = length(bids)); \\\\\\\\\\\\ \\ 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^(bids[i]==j)); \\ zkp proofs3 = matrix(n,k,i,j, zkp3_proof(G,y,G^(bids[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: ", bids); for(X=1,n, if(vecmin(vi[X,])==1, print("And the winner is ", X) ) ); } ;