\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multirow} 

\begin{document}

\newcommand{\todo}[1]{\marginpar{\footnotesize\emph{#1}}}

\newcommand{\ZZ}{\mathbb{Z}}

\section{Parameters of the Encryption Scheme}
\begin{itemize}
  \item There are $n$ authorities, $A_1 \dots A_n$.
  \item Let $k$ be the minimum number of authorities required to jointly decrypt a cyphertext.
  \item \todo {How do we show that's feasable? Prime number theorem?}
    Let $p$ and $q$ be large primes, where $p=2q+1$ ($q$ is commonly called a Sophie Germain prime, $p$ a safe prime). A pair of such numbers can be found by generating a random prime $q$ and checking if $2q+1$ is also prime. 
  \item \todo{Write down proof? Usually just stated as a fact in literature}
    Let $g$ be a generator of $G_q$, where $G_q$ is the unique subgroup of $\ZZ_p^*$ of order $q$. The \emph{Decisional Diffie--Hellman assumption} is believed to hold for $G_q$, as $G_q$ is the subgroup of quadratic residues in $\ZZ_q^*$. \cite{ddh}
  \item The generator $g$ can be computed as follows \cite[Section 4.6]{hac}:
    \begin{enumerate}
      \item Repeatedly choose an $\alpha \in \ZZ_p^*$ at random, until it satisfies $\alpha^q \ne 1$ and $\alpha^2 \ne 1$, 
        that is, the order of $\alpha$ is neither $q$, $2$ nor $1$. Then $\alpha$ is a generator of $\ZZ_p^*$.

        \emph{Proof:} By Lagrange's Theorem, $\ZZ_p^*$ has exactly two proper non-trivial subgroups of order $p$ and $2$, respectively.
        As $\alpha$ is neither of order $p$, $2$ nor $1$, it can only be a generator of $\ZZ_p^*$.
      \item Compute $g=\alpha^k$, where $k=(p-1)/q$. Then $g$ is a generator of $G_q$.

        \emph{Proof:} Let $ord(\cdot)$ be the order a group element. As $k$ divides $ord(\alpha)$, it follows from a standard result of group theory \cite[Proposition 4.5]{algebra} that $ord(\alpha^k) = ord(\alpha)/k = q$.
    \end{enumerate}
\end{itemize}


\section{Key Distribution}
\begin{itemize}
  \item Let $x := \sum_{i=1}^{n} x_i$ be the private key. Note that no single authority should be able to know $x$.
  \item Every authority $A_i$ chooses a random $x_i \in \ZZ_q$, and publishes $h_i := g^{x_i}$.
  \item Let $h := g^{x}$ is the public key, which can be computed as $h = \prod_{i=1}^{n} h_i$.
  \item Every authority $A_i$ generates the random polynomial
    \begin{equation}
      f_i(z) = \sum_{l=0}^{k-1} f_{i,l}^{l},
    \end{equation}
    with $f_i(z) \in \ZZ_q[z]$, where $f_{i,0} = 0$ and $f_{i,l} \in \ZZ_q$ is chosen randomly for $l \ne 0$.
    It follows by definition that $f_i(0) = x_i$.
  \item Every authority $A_i$ publishes $(F_{i,l})_{l=1,\dots,k-1}$, where 
    \begin{equation}
      F_{i,l} = g^{f_{i,l}}
    \end{equation} 
    is the commitment of authority $A_j$ to the value of $f_{i,l}$.
  \item Now every authority $A_i$ secretly sends
    \begin{equation} \label{eq:sendshares}
      s_{i,j} = f_i(j)
    \end{equation} 
    to each authority $A_j$.
  \item \todo{Do we need to prove the consistency? Doesn't it just follow from the fact that it is the same computation, only in the exponent of $g$?}
    $A_i$ verifies the share received from $A_j$ is consistent with the previously published values by
    verifying that
    \begin{equation}
      g^{s_{i,j}} = \prod_{l=0}^{k-1} F_{jl}^{(i^l)}.
    \end{equation} 
    This equation follows directly from raising $g$ to both
    sides of equation \eqref{eq:sendshares}.
  \todo{I think it should be illustrated why this works / what happens with the polynomials}
  \item $A_i$ computes his share of $x$ as $s_i = \sum_{j=1}^n s_{ji}$.
  \item Each authority $A_i$ publishes
    \begin{equation}
      \sigma_i := g^{s_i}
    \end{equation}
  as a commitment to the received share.
\end{itemize}


\section{Cooperative Decryption}
\begin{itemize}
  \item The full private key can be restored by a set at least $k$ cooperating authorities $\Lambda \subseteq \{A_1,\dots,A_n\}$, $k \le |\Lambda|$, for example by using Lagrange interpolation:
    \begin{equation} \label{eq:pkey}
      x = \sum_{A_j \in \Lambda} s_j \lambda_{j,\Lambda}
    \end{equation}
    where the Lagrange coefficients are
    \begin{equation}
      \lambda_{j,\Lambda} := \prod_{\substack{
      A_l \in \Lambda \\ l \neq j} } \frac{l}{l-k}.
    \end{equation}
  Note that this formula is only used for the derivation of the cooperative encryption process, and authorities never actually should cooperate to restore the public key $x$.
  \item To decrypt an ElGamal encryption $(c_1, c_2) = (g^y, h^y m)$ of the message $m \in G_q$, each authority $A_j$ broadcasts $w_j = c_1^{s_j}$.
  \item To prove that an authority has computed $w_j$ correctly, it has to prove in zero-knowledge that
    \[
      s_j = \log_g \sigma_j = \log_{c_1} w_j,
    \]
    in words that $w_j$ has actually been computed with the authority's share.
  \item By raising $c_1$ to both sides of equation \eqref{eq:pkey} and then dividing $c_2$ by both sides, we get
    \[
      m = c_2 / \prod_{A_j \in \Lambda} w_j^{\lambda_{j,\Lambda}}.
    \]
\end{itemize}

\section{Zero-knowledge-proof for discrete logarithms}
\begin{itemize}
  \item The Prover wants to prove
    \[
      s_j = \log_g \sigma_j = \log_{c_1} w_j
    \]
    without revealing the value of $s_j$.
  \item The Prover sends $(g^\beta, c_1^\beta)$, with $\beta \in_R Z_q$
  \item The Verifier sends $c \in_R Z_q$
  \item The Prover sends $r = \beta + s_i c$
  \item The Verifier checks the two equalities
    \[
      g^r = g^\beta \sigma^c
    \]
    \[
      c_1^r = c_1^\beta w_i^c
    \]
\end{itemize}
This proof utilizes the fact that it is hard to compute $g^{ab}$ from $g$ and $a$ without having $b$.

\section{Casting a vote}
\begin{itemize}
  \item A vote has the form $(g^y, h^yG^b)$, where $G$ is a generator of $G_q$ (one could just use $G=q$), $b \in \{-1,1\}$ denotes the value of the vote, and $y \in_R Z_q$.
\end{itemize}

\section{Verifying a vote}
The details on how this protocol can be constructed from the discrete log protocol can be found in \cite{Cramer94}.

\newcommand{\?}{\stackrel{?}{=}}

\begin{table}[!h]
  \begin{tabular}{ c|ccp{\columnwidth} }
    \multicolumn{2}{c}{ Voter } & &
    Verifier \\ \\
    $v=1$ & $v=-1$ & & \\ \cline{1-2}
    $\alpha,w,r_1,d_1 \in_R Z_q$ & $\alpha,w,r_2,d_2 \in_R Z_q$ \\ \\
    $x \leftarrow g^\alpha$ & $x \leftarrow g^\alpha$ \\
    $y \leftarrow h^\alpha G$ & $y \leftarrow h^\alpha / G$ \\
    $a_1 \leftarrow g^{r_1}x^{d_1}$ & $y \leftarrow g^w$ \\
    $b_1 \leftarrow h^{r_1}(yG)^{d_1}$ & $b_1 \leftarrow g^w$ \\
    $a_2 \leftarrow g^w$ & $y \leftarrow g^{r_2}x^{d_2}$ \\
    $b_2 \leftarrow h^w$ & $b_2 \leftarrow h^{r_2}(y/G)^{d_2}$ & 
    $\xrightarrow{x,y,a_1,b_1,a_2,b_2}$ \\ \\
    $d_2 \leftarrow c - d_1$ & $d_1 \leftarrow c - d_2$ &

  $\xleftarrow{c}$ & $c \in_R Z_q$ \\ \\

    $r_2 \leftarrow w - \alpha d_2$ & $r_1 \leftarrow w - \alpha d_1$ &
    $\xrightarrow{d_1,d_2,r_1,r_2}$ & $c \; \? d_1 + d_2$ \\
    \multicolumn{3}{c}{} & $a_1 \? g^{r1} x^{d_1}$ \\
    \multicolumn{3}{c}{} & $b_1 \? h^{r1} (yG)^{d_1}$ \\
    \multicolumn{3}{c}{} & $a_2 \? g^{r2} x^{d_2}$ \\
    \multicolumn{3}{c}{} & $b_2 \? h^{r2} (y/G)^{d_2}$ \\
  \end{tabular}
\end{table}


\clearpage

\section{Counting votes}
\begin{itemize}
  \item Let $(x_i, y_i)$ be the vote casted by Voter $V_i$
  \item $(X,Y) = (\prod_{i=1}^{l}x_i,\prod_{i=1}^{l} y_i)$ is computed by all authorities.
  \item $(X,Y)$ is decrypted cooperatively, obtaining $G^T$,
    where $T$ is the outcome of the election.
  \item Let $l$ be the number of votes. As $T \in \{-t,...,t\}$ holds,
    the number of votes can be found by brute-force.
\end{itemize}


\section{Notes on Notation}

\begin{table}[!h]
  \begin{tabular}{ | c | c | c | c | }
    \hline
    \cite{Cramer97} & \cite{Pedersen} & this document & source code \\ \hline
    $s$ & $x$ & $x$ & BigInteger x \\
     -- & $x_i$ & $x_i$ & BigInteger\lbrack\rbrack \, xParts; xParts\lbrack i\rbrack \\
    \hline
  \end{tabular}
\end{table}


\appendix
\section{ElGamal}
To encrypt a cyphertext $m \in G_q$, the sender chooses a random $y \in_R Z_q$ and sends the pair $(c_1, c_2) = (g^y, m h^y)$.
The decrypt the cyphertext, the receiver recovers the plaintext as $c_2 / c_1^x = (m h^y) / g^{yx} = (m h^y) / h^y = m$.

\clearpage

\bibliographystyle{alpha}
\bibliography{voting}

\end{document}