diff options
Diffstat (limited to 'tex-stuff')
| -rw-r--r-- | tex-stuff/math.tex | 63 |
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. |