math.tex: add first price public outcome protocol and description for M+1st price private outcome protocol

1 files changed, 60 insertions, 3 deletions

diff --git a/tex-stuff/math.tex b/tex-stuff/math.tex
index 04cc1dc..b5cd37e 100644
--- a/tex-stuff/math.tex
+++ b/tex-stuff/math.tex
@@ -101,7 +101,9 @@ the price $p_{b_a}$ bidder $a$ is willing to pay. $\forall j: p_j < p_{j+1}$.
 \subsubsection{Generate public key}
 
 \begin{enumerate}
-        \item Choose $x_{+a} \in \mathbb{Z}_q$ and $\forall i,j: m_{ij}^{+a}, r_{aj} \bmod q$ at random.
+        \item Choose the private key share $x_{+a} \in \mathbb{Z}_q$ and \\
+                $\forall i,j:$ Blinding factors $m_{ij}^{+a} \bmod q$ and \\
+                $\forall j:$ El Gamal encryption parameters $r_{aj} \bmod q$ at random.
         \item Publish $Y_{\times a}={x_{+a}}G$ along with Proof 1 of $Y_{\times a}$'s ECDL.
         \item Compute $Y=\sum_{i=1}^nY_{\times i}$.
 \end{enumerate}
@@ -147,13 +149,68 @@ each $i, j$ and $h \neq i$ after having received all of them.
 
 \subsection{First Price Auction Protocol With Public Outcome}
 
-TODO
+\subsubsection{Round 2: Compute outcome}
+
+$\forall j:$ Compute and publish \\[2.0ex]
+$\gamma_j^{\times a} = m_j^{+a}\displaystyle\left(\sum_{h=1}^n\sum_{d=j+1}^k\alpha_{hd}\right)+\sum_{h=1}^n2^{h-1}\alpha_{hj}$ and \\[2.0ex]
+$\delta_j^{\times a} = m_j^{+a}\displaystyle\left(\sum_{h=1}^n\sum_{d=j+1}^k \beta_{hd}\right)+\sum_{h=1}^n2^{h-1} \beta_{hj}$ \\[2.0ex]
+with a corresponding Proof 2 for $\displaystyle ECDL\left(m_j^{+a}\left(\sum_{h=1}^n\sum_{d=j+1}^k\alpha_{hd}\right)\right) = ECDL\left(m_j^{+a}\left(\sum_{h=1}^n\sum_{d=j+1}^k \beta_{hd}\right)\right)$. \\[2.0ex]
+
+The message has $k$ parts, each consisting of $5$ Points. Therefore the message
+is $5k*32 = 160k$ bytes large. Note that compared to auctions with private
+outcome the message size is reduced by a factor of $n$ because we don't need to
+compute different outcome functions for each bidder when the outcome should be
+public. Therefore we don't need $nk$ blinding factors $m_{ij}^{+a}$ in this
+scheme, but only $k$ different ones $m_j^{+a}$.
+
+\subsubsection{Round 3: Decrypt outcome}
+
+$\forall j:$ Compute and publish $\displaystyle\varphi_j^{\times a} =
+x_{+a}\left(\sum_{h=1}^n\delta_j^{\times h}\right)$ with a Proof 2 showing
+$ECDL(\varphi_j^{\times a}) = ECDL(Y_{\times a})$ \\[2.0ex]
+
+This message has $k$ parts, each consisting of $4$ Points. Therefore the message
+is $4k*32 = 128k$ bytes large.
+
+\subsubsection{Epilogue: Outcome determination}
+
+\begin{enumerate}
+        \item $\forall j:$ Compute $\displaystyle V_j=\sum_{h=1}^n\gamma_j^{\times h} - \sum_{h=1}^n\varphi_j^{\times h}$.
+        \item The $V_j$ with the biggest index $p$ where $V_p \neq 0$ denotes that $p$ is the selling price.
+        \item We then compute $d=ECDL(V_p)/n$ which is doable since it only has small factors.
+        \item The lowest $w$ where the bit $w$ is set in $d$ denotes the winner.
+\end{enumerate}
 
 \subsection{M+1st Price Auction Protocol With Private Outcome}
 
+The tie breaking for M+1st Price Auctions is not only computationally intensive,
+but also introduces a lot of protocol complexity if done in an optimized
+way\footnote{TODO: quote diploma thesis}. Since this would lead to a huge amount
+of additional code which will likely introduce more bugs\footnote{TODO: quote},
+we decided to keep it simple and take another approach for tie breaking in the
+M+1st Price Auction schemes. We took the simplest one, interlacing the bids, so
+that no two bidders are allowed to bid the same price. On the application level
+we will still handle $k_{\text{app}}$ different prices, but within libbrandt we
+will multiply that by a factor of $n$ to get $k_{\text{lib}}=nk_{\text{app}}$.
+Then each bidder $i$ is only allowed to place his bid $b$ on prices $p$ with
+$\exists a\in{[1,k_{\text{app}}]}:b=an-i+1$. This condition will be checked by
+an additional proof in the first round of the protocol and ensures that the
+bidders with a lower index win in case of ties. This expansion will be done
+right at the beginning of an auction by libbrandt. In the remaining part about
+the M+1st Price Auction Protocols we will use $k$ instead of $k_{\text{lib}}$,
+so $k$ will be divisible by $n$ without remainder.
+
+Unfortunately this tie breaking simplification has the downside of revealing the
+identity and bid of the bidder who had the highest bid amongst the losing
+bidders. If there are multiple ones fulfilling this criteria (having a tie on
+the M+1st bid), then only the one with the lowest index will be revealed. This
+problem can be prevented by using anonymized bidder identities, so the winners
+only learn the selling prize (the M+1st highest bid), but not who placed this
+M+1st highest bid.
+
 \subsubsection{Addition to Round 1: Encrypt bid}
 
-The Bidders also have to use Proof 2 to show that $ ECDL_Y\left(\left(\sum_{j=1}^{k/n}\alpha_{a,jn+a}\right) - G\right) = ECDL_G\left(\sum_{j=1}^{k/n}\beta_{a,jn+a}\right)$.
+The Bidders also have to use Proof 2 to show that $\displaystyle ECDL_Y\left(\left(\sum_{j=1}^{k/n}\alpha_{a,jn+a}\right) - G\right) = ECDL_G\left(\sum_{j=1}^{k/n}\beta_{a,jn+a}\right)$. \\[2.0ex]
 This is to ensure bidders have only chosen valid bids for their bid index, since
 in M+1st price auctions the amount of possible prices is multiplied by $n$ to
 prevent ties. This increases the message size by $96$ bytes.