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) ))
+
+;