<commit_before>\documentclass[a4paper]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{hyperref}

\newcommand{\version}{0.2}

\newcommand{\F}{\mathbbm{F}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\I}{\mathbbm{I}}
\newcommand{\B}{\mathbbm{B}}

\newcommand{\public}{\textsf{public}}
\newcommand{\shuffle}{\textsf{shuffle}}
\newcommand{\basesixfour}{\textsf{BASE64}}
\newcommand{\shatwo}{\textsf{SHA256}}

\newcommand{\jstring}{\texttt{string}}
\newcommand{\uuid}{\texttt{uuid}}
\newcommand{\tpk}{\texttt{trustee\_public\_key}}
\newcommand{\election}{\texttt{election}}
\newcommand{\ballot}{\texttt{ballot}}
\newcommand{\etally}{\texttt{encrypted\_tally}}
\newcommand{\pdecryption}{\texttt{partial\_decryption}}
\newcommand{\result}{\texttt{result}}

\title{Belenios specification}
\date{Version~\version}
\author{<NAME>}

\begin{document}
\maketitle
\tableofcontents

\section{Introduction}

This document is a specification of the voting protocol implemented in
Belenios v\version. More discussion, theoretical explanations and
bibliographical references can be found in a technical report
available online.\footnote{\url{http://eprint.iacr.org/2013/177}}

The Belenios protocol is very similar to Helios (with a signature
added to ballots and different zero-knowledge proofs) and Helios-C
(with the distributed key generation of trustees of Helios, without
threshold support).

The cryptography involved in Belenios needs a cyclic group $\G$ where
discrete logarithms are hard to compute. We will denote by $g$ a
generator and $q$ its order. We use a multiplicative notation for the
group operation. For practical purposes, we use a multiplicative
subgroup of $\F^*_p$ (hence, all exponentiations are implicitly done
modulo $p$). We suppose the group parameters are agreed on
beforehand. Default group parameters are given as examples in
section~\ref{default-group}.

\section{Parties}

\begin{itemize}
\item $S$: voting server
\item $A$: server administrator
\item $C$: credential authority
\item $T_1,\dots,T_m$: trustees
\item $V_1,\dots,V_n$: voters
\end{itemize}

\section{Processes}
\label{processes}

\subsection{Election setup}
\label{election-setup}

\begin{enumerate}
\item $A$ generates a fresh \hyperref[basic-types]{$\uuid$} $u$ and
  sends it to $C$
\item $C$ generates \hyperref[credentials]{credentials}
  $c_1,\dots,c_n$ and computes
  $L=\shuffle(\public(c_1),\dots,\public(c_n))$
\item for $j\in[1\dots n]$, $C$ sends $c_j$ to $V_j$
\item $C$ forgets $c_1,\dots,c_n$
\item $C$ forgets the mapping between $j$ and $\public(c_j)$
  if credential recovery is not needed
\item $C$ sends $L$ to $A$
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $T_z$ generates a \hyperref[trustee-keys]{$\tpk$} $k_z$ and
    sends it to $A$
  \item $A$ checks $k_z$
  \end{enumerate}
\item $A$ combines all the trustee public keys into the election
  public key $y$
\item $A$ creates the \hyperref[elections]{$\election$} $E$
\item $A$ loads $E$ and $L$ into $S$ and starts it
\end{enumerate}

\subsection{Vote}

\begin{enumerate}
\item $V$ gets $E$
\item $V$ creates a \hyperref[ballots]{$\ballot$} $b$ and submits it to $S$
\item $S$ validates $b$ and publishes it
\end{enumerate}

\subsection{Credential recovery}

\begin{enumerate}
\item $V$ contacts $C$
\item $C$ looks up $V$'s public credential $\public(c_i)$ and
  generates a new credential $c'_i$
\item $C$ sends $c'_i$ to $V$ and forgets it
\item $C$ sends $\public(c_i)$ and $\public(c'_i)$ to $A$
\item $A$ checks that $\public(c_i)$ has not been used and replaces it
  by $\public(c'_i)$ in $L$
\end{enumerate}

\subsection{Tally}

\begin{enumerate}
\item $A$ stops $S$ and computes the \hyperref[tally]{$\etally$} $\Pi$
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $A$ sends $\Pi$ to $T_z$
  \item $T_z$ generates a \hyperref[tally]{$\pdecryption$} $\delta_z$
    and sends it to $A$
  \item $A$ verifies $\delta_z$
  \end{enumerate}
\item $A$ combines all the partial decryptions, computes and publishes
  the election \hyperref[election-result]{\result}
\end{enumerate}

\section{Messages}
\label{messages}

\subsection{Conventions}

Structured data is encoded in JSON (RFC 4627). There is no specific
requirement on the formatting and order of fields, but care must be
taken when hashes are computed. We use the notation
$\textsf{field}(o)$ to access the field \textsf{field} of $o$.

\subsection{Basic types}
\label{basic-types}

\begin{itemize}
\item $\jstring$: JSON string
\item $\uuid$: UUID (see RFC 4122), encoded as a JSON string
\item $\I$: small integer, encoded as a JSON number
\item $\B$: boolean, encoded as a JSON boolean
\item $\N$, $\Z_q$, $\G$: big integer, written in base 10 and encoded as a
  JSON string
\end{itemize}

\subsection{Common structures}
\label{common}

\newcommand{\pk}{\texttt{public\_key}}
\newcommand{\sk}{\texttt{private\_key}}
\newcommand{\proof}{\texttt{proof}}
\newcommand{\iproof}{\texttt{iproof}}
\newcommand{\ciphertext}{\texttt{ciphertext}}

\newcommand{\pklabel}{\textsf{public\_key}}
\newcommand{\pok}{\textsf{pok}}
\newcommand{\challenge}{\textsf{challenge}}
\newcommand{\response}{\textsf{response}}
\newcommand{\alphalabel}{\textsf{alpha}}
\newcommand{\betalabel}{\textsf{beta}}
\newcommand{\Hash}{\mathcal{H}}

\begin{gather*}
  \proof=\left\{
    \begin{array}{rcl}
      \challenge&:&\Z_q\\
      \response&:&\Z_q
    \end{array}
  \right\}
  \qquad
  \ciphertext=\left\{
    \begin{array}{rcl}
      \alphalabel&:&\G\\
      \betalabel&:&\G
    \end{array}
  \right\}
\end{gather*}

\subsection{Trustee keys}
\label{trustee-keys}

\begin{gather*}
  \pk=\G\qquad\sk=\Z_q\\
  \tpk=\left\{
    \begin{array}{rcl}
      \pok&:&\proof\\
      \pklabel&:&\pk
    \end{array}
  \right\}
\end{gather*}

A private key is a random number $x$ modulo $q$. The corresponding
$\pklabel$ is $X=g^x$. A $\tpk$ is a bundle of this public key with a
\hyperref[common]{$\proof$} of knowledge computed as follows:
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A=g^w$
\item $\challenge=\Hash_\pok(X,A)\mod q$
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
where $\Hash_\pok$ is computed as follows:
\[\Hash_\pok(X,A) = \shatwo(\verb=pok|=X\verb=|=A) \]
where $\pok$ and the vertical bars are verbatim and numbers are
written in base 10. The result is interpreted as a 256-bit big-endian
number. The proof is verified as follows:
\begin{enumerate}
\item compute $A={g^\response}/{y^\challenge}$
\item check that $\challenge=\Hash_\pok(\pklabel,A)\mod q$
\end{enumerate}

\subsection{Credentials}
\label{credentials}

\newcommand{\secret}{\texttt{secret}}

A secret \emph{credential} $c$ is a 15-character string, where characters are
taken from the set:
\[\texttt{123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz}\]
The first 14 characters are random, and the last one is a checksum to
detect typing errors. To compute the checksum, each character is
interpreted as a base 58 digit: $\texttt{1}$ is $0$, $\texttt{2}$ is
$1$, \dots, $\texttt{z}$ is $57$. The first 14 characters are
interpreted as a big-endian number $c_1$ The checksum is $53-c_1\mod
53$.

From this string, a secret exponent $s=\secret(c)$ is derived by using
PBKDF2 (RFC 2898) with:
\begin{itemize}
\item $c$ as password;
\item HMAC-SHA256 (RFC 2104, FIPS PUB 180-2) as pseudorandom function;
\item the $\uuid$ (interpreted as a 16-byte array) of the election as
  salt;
\item $1000$ iterations
\end{itemize}
and an output size of 1 block, which is interpreted as a big-endian
256-bit number and then reduced modulo $q$ to form $s$.  From this
secret exponent, a public key $\public(c)=g^s$ is computed.

\subsection{Election}
\label{elections}

\newcommand{\question}{\texttt{question}}

\begin{gather*}
  \texttt{wrapped\_pk}=\left\{
    \begin{array}{rcl}
      \textsf{g}&:&\G\\
      \textsf{p}&:&\N\\
      \textsf{q}&:&\N\\
      \textsf{y}&:&\G
    \end{array}
  \right\}
\end{gather*}
The election public key, which is denoted by $y$ thoughout this
document, is computed by multiplying all the public keys of the
trustees, and bundled with the group parameters in a
\texttt{wrapped\_pk} structure.

\newcommand{\blank}{\textsf{blank}}
\newcommand{\minlabel}{\textsf{min}}
\newcommand{\maxlabel}{\textsf{max}}
\newcommand{\answers}{\textsf{answers}}

\begin{gather*}
  \question=\left\{
    \begin{array}{rcl}
      \answers&:&\jstring^\ast\\
      ?\blank&:&\B\\
      \minlabel&:&\I\\
      \maxlabel&:&\I\\
      \textsf{question}&:&\jstring
    \end{array}
  \right\}
  \qquad
  \election=\left\{
    \begin{array}{rcl}
      \textsf{description}&:&\jstring\\
      \textsf{name}&:&\jstring\\
      \textsf{public\_key}&:&\texttt{wrapped\_pk}\\
      \textsf{questions}&:&\texttt{question}^\ast\\
      \textsf{uuid}&:&\texttt{uuid}
    \end{array}
  \right\}
\end{gather*}

The $\blank$ field of $\question$ is optional. When present and true,
the voter can vote blank for this question. In a blank vote, all
answers are set to $0$ regardless of the values of $\minlabel$ and
$\maxlabel$ ($\minlabel$ doesn't need to be $0$).

\newcommand{\answer}{\texttt{answer}}
\newcommand{\signature}{\texttt{signature}}
\newcommand{\iproofs}{\textsf{individual\_proofs}}
\newcommand{\oproof}{\textsf{overall\_proof}}
\newcommand{\bproof}{\textsf{blank\_proof}}
\newcommand{\choices}{\textsf{choices}}
\newcommand{\iprove}{\textsf{iprove}}

During an election, the following data needs to be public in order to
verify the setup phase and to validate ballots:
\begin{itemize}
\item the $\election$ structure described above;
\item all the $\tpk$s that were generated during the
  \hyperref[election-setup]{setup phase};
\item the set $L$ of public credentials.
\end{itemize}

\subsection{Encrypted answers}
\label{answers}

\begin{gather*}
  \answer=\left\{
    \begin{array}{rcl}
      \choices&:&\ciphertext^\ast\\
      \iproofs&:&\iproof^\ast\\
      \oproof&:&\iproof\\
      ?\bproof&:&\proof^2
    \end{array}
  \right\}
\end{gather*}

An answer to a \hyperref[elections]{$\question$} is the vector
$\choices$ of encrypted weights given to each answer. When $\blank$ is
false (or absent), a blank vote is not allowed and this vector has the
same length as $\answers$; otherwise, a blank vote is allowed and this
vector has an additionnal leading weight corresponding to whether the
vote is blank or not.  Each weight comes with a proof (in \iproofs,
same length as \choices) that it is $0$ or $1$. The whole answer also
comes with additional proofs that weights respect constraints.

More concretely, each weight $m\in[0\dots1]$ is encrypted into a
$\ciphertext$ as follows:
\begin{enumerate}
\item pick a random $r\in\Z_q$
\item $\alphalabel=g^r$
\item $\betalabel=y^rg^m$
\end{enumerate}
where $y$ is the election public key.

To compute the proofs, the voter needs a
\hyperref[credentials]{credential} $c$. Let $s=\secret(c)$, and
$S=g^s$ written in base 10. The individual proof that $m\in[0\dots1]$
is computed by running $\iprove(S,r,m,0,1)$ (see
section~\ref{iproof}).

When a blank vote is not allowed, $\oproof$ proves that
$M\in[\minlabel\dots\maxlabel]$ and is computed by running
$\iprove(S,R,M-\minlabel,\minlabel,\dots,\maxlabel)$ where $R$ is the
sum of the $r$ used in ciphertexts, and $M$ the sum of the $m$. There
is no $\bproof$.

When a blank vote is allowed, and there are $n$ choices, the answer is
modeled as a vector $(m_0,m_1,\dotsc,m_n)$, when $m_0$ is whether this
is a blank vote or not, and $m_i$ (for $i>0$) is whether choice $i$
has been selected. Each $m_i$ is encrypted and proven equal to $0$ or
$1$ as above. Let $m_\Sigma=m_1+\dotsb+m_n$. The additionnal proofs
are as follows:
\begin{itemize}
\item $\bproof$ proves that $m_0=0\lor m_\Sigma=0$;
\item $\oproof$ proves that $m_0=1\lor m_\Sigma\in[\minlabel\dots\maxlabel]$.
\end{itemize}
They are computed as described in section~\ref{bproof}.

\subsection{Proofs of interval membership}
\label{iproof}

\begin{gather*}
  \iproof=\proof^\ast
\end{gather*}

Given a pair $(\alpha,\beta)$ of group elements, one can prove that it
has the form $(g^r,y^rg^{M_i})$ with $M_i\in[M_0,\dots,M_k]$ by
creating a sequence of $\proof$s $\pi_0,\dots,\pi_k$ with the
following procedure, parameterised by a group element $S$:
\begin{enumerate}
\item for $j\neq i$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$
  \item compute
    \[A_j=\frac{g^\response}{\alpha^\challenge}\quad\text{and}\quad
    B_j=\frac{y^\response}{(\beta/g^{M_j})^\challenge}\]
  \end{enumerate}
\item $\pi_i$ is created as follows:
  \begin{enumerate}
  \item pick a random $w\in\Z_q$
  \item compute $A_i=g^w$ and $B_i=y^w$
  \item $\challenge(\pi_i)=\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)-\sum_{j\neq
      i}\challenge(\pi_j)\mod q$
  \item $\response(\pi_i)=w+r\times\challenge(\pi_i)\mod q$
  \end{enumerate}
\end{enumerate}
In the above, $\Hash_\iprove$ is computed as follows:
\[\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)=\shatwo(\verb=prove|=S\verb=|=\alpha\verb=,=\beta\verb=|=A_0\verb=,=B_0\verb=,=\dots\verb=,=A_k\verb=,=B_k)\mod q\]
where \verb=prove=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number. We will denote the whole procedure by
$\iprove(S,r,i,M_0,\dots,M_k)$.

The proof is verified as follows:
\begin{enumerate}
\item for $j\in[0\dots k]$, compute
  \[A_j=\frac{g^{\response(\pi_j)}}{\alpha^{\challenge(\pi_j)}}\quad\text{and}\quad
  B_j=\frac{y^{\response(\pi_j)}}{(\beta/g^{M_j})^{\challenge(\pi_j)}}\]
\item check that
  \[\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)=\sum_{j\in[0\dots
    k]}\challenge(\pi_j)\mod q\]
\end{enumerate}

\subsection{Proofs of possibly-blank votes}
\label{bproof}

In this section, we suppose:
\[
(\alpha_0,\beta_0)=(g^{r_0},y^{r_0}g^{m_0})
\quad\text{and}\quad
(\alpha_\Sigma,\beta_\Sigma)=(g^{r_\Sigma},y^{r_\Sigma}g^{m_\Sigma})
\]
Note that $\alpha_\Sigma$, $\beta_\Sigma$ and $r_\Sigma$ can be easily
computed from the encryptions of $m_1,\dotsc,m_n$ and their associated
secrets.

Additionnally, let $P$ be the string
``$g\verb=,=y\verb=,=\alpha_0\verb=,=\beta_0\verb=,=\alpha_\Sigma\verb=,=\beta_\Sigma$'',
where the commas are verbatim and the numbers are written in base
10. Let also $M_1,\dotsc,M_k$ be the sequence
$\minlabel,\dots,\maxlabel$ ($k=\maxlabel-\minlabel+1$).

\subsubsection{Non-blank votes ($m_0=0$)}
\label{non-blank-votes}

\paragraph{Computing \bproof}
In $m_0=0\lor m_\Sigma=0$, the first case is true. The proof $\bproof$
of the whole statement is the couple of proofs $(\pi_0,\pi_\Sigma)$
built as follows:
\begin{enumerate}
\item pick random $\challenge(\pi_\Sigma)$ and $\response(\pi_\Sigma)$
  in $\Z_q$
\item compute
  $A_\Sigma=g^{\response(\pi_\Sigma)}\times\alpha_\Sigma^{\challenge(\pi_\Sigma)}$
  and
  $B_\Sigma=y^{\response(\pi_\Sigma)}\times\beta_\Sigma^{\challenge(\pi_\Sigma)}$
\item pick a random $w$ in $\Z_q$
\item compute $A_0=g^w$ and $B_0=y^w$
\item compute \[\challenge(\pi_0)=\Hash_{\mathsf{bproof0}}(S,P,A_0,B_0,A_\Sigma,B_\Sigma)-\challenge(\pi_\Sigma)\mod q\]
\item compute $\response(\pi_0)=w-r_0\times\challenge(\pi_0)\mod q$
\end{enumerate}
In the above, $\Hash_{\mathsf{bproof0}}$ is computed as follows:
\[\Hash_{\mathsf{bproof0}}(\dotsc)=
\shatwo(\verb=bproof0|=S\verb=|=P\verb=|=A_0\verb=,=B_0\verb=,=A_\Sigma\verb=,=B_\Sigma)\mod q\]
where \verb=bproof0=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

\paragraph{Computing \oproof}
In $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$, the second case
is true. Let $i$ be such that $m_\Sigma=M_i$. The proof of the whole
statement is a $(k+1)$-tuple $(\pi_0,\pi_1,\dotsc,\pi_k)$ built as
follows:
\begin{enumerate}
\item pick random $\challenge(\pi_0)$ and $\response(\pi_0)$
  in $\Z_q$
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times(\beta_0/g)^{\challenge(\pi_0)}$
\item for $j>0$ and $j\neq i$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$ in $\Z_q$
  \item compute
    $A_j={g^\response}\times{\alpha_\Sigma^\challenge}$ and
    $B_j={y^\response}\times{(\beta_\Sigma/g^{M_j})^\challenge}$
  \end{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A_i=g^w$ and $B_i=y^w$
\item compute
  \[\challenge(\pi_i)=\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)-\sum_{j\neq i}\challenge(\pi_j)\mod q\]
\item compute $\response(\pi_i)=w-r_\Sigma\times\challenge(\pi_i)\mod q$
\end{enumerate}
In the above, $\Hash_{\mathsf{bproof1}}$ is computed as follows:
\[\Hash_{\mathsf{bproof1}}(\dotsc)=
\shatwo(\verb=bproof1|=S\verb=|=P\verb=|=A_0\verb=,=B_0\verb=,=\dotsc\verb=,=A_k\verb=,=B_k)\mod q\]
where \verb=bproof1=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

\subsubsection{Blank votes ($m_0=1$)}

\paragraph{Computing \bproof}
In $m_0=0\lor m_\Sigma=0$, the second case is true. The proof
$\bproof$ of the whole statement is the couple of proofs
$(\pi_0,\pi_\Sigma)$ built as in section~\ref{non-blank-votes}, but
exchanging subscripts $0$ and $\Sigma$ everywhere except in the call
to $\Hash_{\textsf{bproof0}}$.

\paragraph{Computing \oproof}
In $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$, the first case is
true. The proof of the whole statement is a $(k+1)$-tuple
$(\pi_0,\pi_1,\dotsc,\pi_k)$ built as follows:
\begin{enumerate}
\item for $j>0$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$ in $\Z_q$
  \item compute
    $A_j={g^\response}\times{\alpha_\Sigma^\challenge}$ and
    $B_j={y^\response}\times{(\beta_\Sigma/g^{M_j})^\challenge}$
  \end{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A_0=g^w$ and $B_0=y^w$
\item compute
  \[\challenge(\pi_0)=\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)-\sum_{j>0}\challenge(\pi_j)\mod q\]
\item compute $\response(\pi_0)=w-r_0\times\challenge(\pi_0)\mod q$
\end{enumerate}

\subsubsection{Verifying proofs}

\paragraph{Verifying \bproof}
A proof of $m_0=0\lor m_\Sigma=0$ is a couple of proofs
$(\pi_0,\pi_\Sigma)$ such that the following procedure passes:
\begin{enumerate}
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times\beta_0^{\challenge(\pi_0)}$
\item compute
  $A_\Sigma=g^{\response(\pi_\Sigma)}\times\alpha_\Sigma^{\challenge(\pi_\Sigma)}$
  and
  $B_\Sigma=y^{\response(\pi_\Sigma)}\times\beta_\Sigma^{\challenge(\pi_\Sigma)}$
\item check that
  \[\Hash_{\mathsf{bproof0}}(S,P,A_0,B_0,A_\Sigma,B_\Sigma)=\challenge(\pi_0)+\challenge(\pi_\Sigma)\mod q\]
\end{enumerate}

\paragraph{Verifying \oproof}
A proof of $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$ is a $(k+1)$-tuple
$(\pi_0,\pi_1,\dotsc,\pi_k)$ such that the following procedure passes:
\begin{enumerate}
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times(\beta_0/g)^{\challenge(\pi_0)}$
\item for $j>0$, compute
  \[A_j=g^{\response(\pi_j)}\times\alpha_j^{\challenge(\pi_j)}
  \quad\text{and}\quad
  B_j=y^{\response(\pi_j)}\times(\beta_j/g^{M_j})^{\challenge(\pi_j)}\]
\item check that
  \[\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)=\sum_{j=0}^k\challenge(\pi_j)\mod q\]
\end{enumerate}

\subsection{Signatures}
\label{signatures}

\begin{gather*}
  \signature=\left\{
    \begin{array}{rcl}
      \pklabel&:&\pk\\
      \challenge&:&\Z_q\\
      \response&:&\Z_q
    \end{array}
  \right\}
\end{gather*}

\newcommand{\siglabel}{\textsf{signature}}

Each ballot contains a digital signature to avoid ballot stuffing. The
signature needs a \hyperref[credentials]{credential} $c$ and uses all
the \ciphertext{}s $\gamma_1,\dots,\gamma_l$ that appear in the ballot
($l$ is the sum of the lengths of $\choices$). It is computed as
follows:
\begin{enumerate}
\item compute $s=\secret(c)$
\item pick a random $w\in\Z_q$
\item compute $A=g^w$
\item $\pklabel=g^s$
\item $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
\item $\response=w-s\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\siglabel$ is computed as follows:
\[
\Hash_\siglabel(S,A,\gamma_1,\dots,\gamma_l)=\shatwo(\verb=sig|=S\verb=|=A\verb=|=\alphalabel(\gamma_1)\verb=,=\betalabel(\gamma_1)\verb=,=\dots\verb=,=\alphalabel(\gamma_l)\verb=,=\betalabel(\gamma_l))
\]
where \verb=sig=, the vertical bars and commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

Signatures are verified as follows:
\begin{enumerate}
\item compute $A=g^\response\times \pklabel^\challenge$
\item check that $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
\end{enumerate}

\subsection{Ballots}
\label{ballots}

\newcommand{\json}{\textsf{JSON}}

\begin{gather*}
  \ballot=\left\{
    \begin{array}{rcl}
      \answers&:&\hyperref[answers]{\answer}^\ast\\
      \textsf{election\_hash}&:&\jstring\\
      \textsf{election\_uuid}&:&\uuid\\
      \siglabel&:&\hyperref[signatures]{\signature}
    \end{array}
  \right\}
\end{gather*}
The so-called hash (or \emph{fingerprint}) of the election
is computed with the function $\Hash_\json$:
\[
\Hash_\json(J)=\basesixfour(\shatwo(J))
\]
Where $J$ is the serialization (done by the server) of the $\election$
structure.

The same hashing function is used on a serialization (done by the
voting client) of the $\ballot$ structure to produce a so-called
\emph{smart ballot tracker}.

\subsection{Tally}
\label{tally}

\begin{gather*}
  \etally=\ciphertext^\ast{}^\ast
\end{gather*}
The encrypted tally is the pointwise product of the ciphertexts of all
accepted ballots:
\[
\begin{array}{rcl}
\alphalabel(\etally_{i,j})&=&\prod\alphalabel(\choices(\answers(\ballot)_i)_j)\\
\betalabel(\etally_{i,j})&=&\prod\betalabel(\choices(\answers(\ballot)_i)_j)
\end{array}
\]

\newcommand{\dfactors}{\textsf{decryption\_factors}}
\newcommand{\dproofs}{\textsf{decryption\_proofs}}
\newcommand{\decrypt}{\textsf{decrypt}}

\begin{gather*}
  \pdecryption=\left\{
    \begin{array}{rcl}
      \dfactors&:&\G^\ast{}^\ast\\
      \dproofs&:&\proof^\ast{}^\ast
    \end{array}
  \right\}
\end{gather*}
From the encrypted tally, each trustee computes a partial decryption
using the \hyperref[trustee-keys]{private key} $x$ (and the
corresponding public key $X=g^x$) he generated during election
setup. It consists of so-called decryption factors:
\[
\dfactors_{i,j}=\alphalabel(\etally_{i,j})^x
\]
and proofs that they were correctly computed. Each $\dproofs_{i,j}$ is
computed as follows:
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A=g^w$ and $B=\alphalabel(\etally_{i,j})^w$
\item $\challenge=\Hash_\decrypt(X,A,B)$
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\decrypt$ is computed as follows:
\[
\Hash_\decrypt(X,A,B)=\shatwo(\verb=decrypt|=X\verb=|=A\verb=,=B)\mod q
\]
where \verb=decrypt=, the vertical bars and the comma are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

These proofs are verified using the $\tpk$ structure $k$ that the
trustee sent to the administrator during the election setup:
\begin{enumerate}
\item compute
\[
A=\frac{g^\response}{\pklabel(k)^\challenge}
\quad\text{and}\quad
B=\frac{\alphalabel(\etally_{i,j})^\response}{\dfactors_{i,j}^\challenge}
\]
\item check that $\Hash_\decrypt(\pklabel(k),A,B)=\challenge$
\end{enumerate}

\subsection{Election result}
\label{election-result}

\newcommand{\ntallied}{\textsf{num\_tallied}}
\newcommand{\etallylabel}{\textsf{encrypted\_tally}}
\newcommand{\pdlabel}{\textsf{partial\_decryptions}}
\newcommand{\resultlabel}{\textsf{result}}

\begin{gather*}
  \result=\left\{
    \begin{array}{rcl}
      \ntallied&:&\I\\
      \etallylabel&:&\etally\\
      \pdlabel&:&\pdecryption^\ast\\
      \resultlabel&:&\I^\ast{}^\ast
    \end{array}
  \right\}
\end{gather*}
The decryption factors are combined for each ciphertext to build
synthetic ones:
\[
F_{i,j}=\prod_{z\in[1\dots m]}\pdlabel_{z,i,j}
\]
where $m$ is the number of trustees. The $\resultlabel$ field of the
$\result$ structure is then computed as follows:
\[
\resultlabel_{i,j}=\log_g\left(\frac{\betalabel(\etallylabel_{i,j})}{F_{i,j}}\right)
\]
Here, the discrete logarithm can be easily computed because it is
bounded by $\ntallied$.

After the election, the following data needs to be public in order to
verify the tally:
\begin{itemize}
\item the $\election$ structure;
\item all the $\tpk$s that were generated during the
  \hyperref[election-setup]{setup phase};
\item the set of public credentials;
\item the set of ballots;
\item the $\result$ structure described above.
\end{itemize}
<commit_msg>Update the specification with threshold decryption support<commit_after>\documentclass[a4paper]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{hyperref}

\newcommand{\version}{1.5}

\newcommand{\F}{\mathbbm{F}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\I}{\mathbbm{I}}
\newcommand{\B}{\mathbbm{B}}

\newcommand{\public}{\textsf{public}}
\newcommand{\shuffle}{\textsf{shuffle}}
\newcommand{\basesixfour}{\textsf{BASE64}}
\newcommand{\shatwo}{\textsf{SHA256}}

\newcommand{\jstring}{\texttt{string}}
\newcommand{\uuid}{\texttt{uuid}}
\newcommand{\tpk}{\texttt{trustee\_public\_key}}
\newcommand{\election}{\texttt{election}}
\newcommand{\ballot}{\texttt{ballot}}
\newcommand{\etally}{\texttt{encrypted\_tally}}
\newcommand{\pdecryption}{\texttt{partial\_decryption}}
\newcommand{\result}{\texttt{result}}

\newcommand{\cert}{\texttt{cert}}
\newcommand{\poly}{\texttt{polynomial}}
\newcommand{\vinput}{\texttt{vinput}}
\newcommand{\voutput}{\texttt{voutput}}

\title{Belenios specification}
\date{Version~\version}
\author{<NAME>}

\begin{document}
\maketitle
\tableofcontents

\section{Introduction}

This document is a specification of the voting protocol implemented in
Belenios v\version. More discussion, theoretical explanations and
bibliographical references can be found in a technical report
available online.\footnote{\url{http://eprint.iacr.org/2013/177}}

The cryptography involved in Belenios needs a cyclic group $\G$ where
discrete logarithms are hard to compute. We will denote by $g$ a
generator and $q$ its order. We use a multiplicative notation for the
group operation. For practical purposes, we use a multiplicative
subgroup of $\F^*_p$ (hence, all exponentiations are implicitly done
modulo $p$). We suppose the group parameters are agreed on
beforehand. Default group parameters are given as examples in
section~\ref{default-group}.

\section{Parties}

\begin{itemize}
\item $S$: voting server
\item $A$: server administrator
\item $C$: credential authority
\item $T_1,\dots,T_m$: trustees
\item $V_1,\dots,V_n$: voters
\end{itemize}

\section{Processes}
\label{processes}

\subsection{Election setup}
\label{election-setup}

\begin{enumerate}
\item $A$ generates a fresh \hyperref[basic-types]{$\uuid$} $u$ and
  sends it to $C$
\item $C$ generates \hyperref[credentials]{credentials}
  $c_1,\dots,c_n$ and computes
  $L=\shuffle(\public(c_1),\dots,\public(c_n))$
\item for $j\in[1\dots n]$, $C$ sends $c_j$ to $V_j$
\item $C$ forgets $c_1,\dots,c_n$
\item $C$ forgets the mapping between $j$ and $\public(c_j)$
  if credential recovery is not needed
\item $C$ sends $L$ to $A$
\item $A$ and $T_1,\dotsc,T_m$ run a key establishment protocol
  (either \ref{no-threshold} or \ref{threshold})
\item $A$ creates the \hyperref[elections]{$\election$} $E$
\item $A$ loads $E$ and $L$ into $S$ and starts it
\end{enumerate}

\subsubsection{Basic decryption support}
\label{no-threshold}

To perform tally with this scheme, all trustees will need to compute a
partial decryption.

\begin{enumerate}
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $T_z$ generates a \hyperref[trustee-keys]{$\tpk$} $k_z$ and
    sends it to $A$
  \item $A$ checks $k_z$
  \end{enumerate}
\item $A$ combines all the trustee public keys into the election
  public key $y$
\end{enumerate}

\subsubsection{Threshold decryption support}
\label{threshold}

To perform tally with this scheme, $t+1$ trustees will need to compute
a partial decryption.

\begin{enumerate}
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $T_z$ generates a \hyperref[certificates]{$\cert$} $\gamma_z$
    and sends it to $A$
  \item $A$ checks $\gamma_z$
  \end{enumerate}
\item $A$ assembles $\Gamma=\gamma_1,\dotsc,\gamma_n$
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $A$ sends $\Gamma$ to $T_z$ and $T_z$ checks it
  \item $T_z$ generates a \hyperref[polynomials]{$\poly$} $P_z$ and
    sends it to $A$
  \item $A$ checks $P_z$
  \end{enumerate}
\item for $z\in[1\dots m]$, $A$ computes a
  \hyperref[vinputs]{$\vinput$} $\textsf{vi}_z$
\item for $z\in[1\dots m]$,
  \begin{enumerate}
  \item $A$ sends $\Gamma$ to $T_z$ and $T_z$ checks it
  \item $A$ sends $\textsf{vi}_z$ to $T_z$ and $T_z$ checks it
  \item $A$ computes a \hyperref[voutputs]{$\voutput$} $\textsf{vo}_z$ and
    sends it to $A$
  \item $A$ checks $\textsf{vo}_z$
  \end{enumerate}
\item $A$ extracts encrypted decryption keys $K_1,\dots,K_m$ and
  \hyperref[threshold-params]{threshold parameters}
\end{enumerate}

\subsection{Vote}

\begin{enumerate}
\item $V$ gets $E$
\item $V$ creates a \hyperref[ballots]{$\ballot$} $b$ and submits it to $S$
\item $S$ validates $b$ and publishes it
\end{enumerate}

\subsection{Credential recovery}

\begin{enumerate}
\item $V$ contacts $C$
\item $C$ looks up $V$'s public credential $\public(c_i)$ and
  generates a new credential $c'_i$
\item $C$ sends $c'_i$ to $V$ and forgets it
\item $C$ sends $\public(c_i)$ and $\public(c'_i)$ to $A$
\item $A$ checks that $\public(c_i)$ has not been used and replaces it
  by $\public(c'_i)$ in $L$
\end{enumerate}

\subsection{Tally}

\begin{enumerate}
\item $A$ stops $S$ and computes the \hyperref[tally]{$\etally$} $\Pi$
\item for $z\in[1\dots m]$ (or, if in threshold mode, a subset of it
  of size at least $t+1$),
  \begin{enumerate}
  \item $A$ sends $\Pi$ (and $K_z$ if in threshold mode) to $T_z$
  \item $T_z$ generates a \hyperref[tally]{$\pdecryption$} $\delta_z$
    and sends it to $A$
  \item $A$ verifies $\delta_z$
  \end{enumerate}
\item $A$ combines all the partial decryptions, computes and publishes
  the election \hyperref[election-result]{\result}
\end{enumerate}

\section{Messages}
\label{messages}

\subsection{Conventions}

Structured data is encoded in JSON (RFC 4627). There is no specific
requirement on the formatting and order of fields, but care must be
taken when hashes are computed. We use the notation
$\textsf{field}(o)$ to access the field \textsf{field} of $o$.

\subsection{Basic types}
\label{basic-types}

\begin{itemize}
\item $\jstring$: JSON string
\item $\uuid$: UUID (see RFC 4122), encoded as a JSON string
\item $\I$: small integer, encoded as a JSON number
\item $\B$: boolean, encoded as a JSON boolean
\item $\N$, $\Z_q$, $\G$: big integer, written in base 10 and encoded as a
  JSON string
\end{itemize}

\subsection{Common structures}
\label{common}

\newcommand{\pk}{\texttt{public\_key}}
\newcommand{\sk}{\texttt{private\_key}}
\newcommand{\proof}{\texttt{proof}}
\newcommand{\iproof}{\texttt{iproof}}
\newcommand{\ciphertext}{\texttt{ciphertext}}

\newcommand{\pklabel}{\textsf{public\_key}}
\newcommand{\pok}{\textsf{pok}}
\newcommand{\challenge}{\textsf{challenge}}
\newcommand{\response}{\textsf{response}}
\newcommand{\alphalabel}{\textsf{alpha}}
\newcommand{\betalabel}{\textsf{beta}}
\newcommand{\Hash}{\mathcal{H}}

\begin{gather*}
  \proof=\left\{
    \begin{array}{rcl}
      \challenge&:&\Z_q\\
      \response&:&\Z_q
    \end{array}
  \right\}
  \qquad
  \ciphertext=\left\{
    \begin{array}{rcl}
      \alphalabel&:&\G\\
      \betalabel&:&\G
    \end{array}
  \right\}
\end{gather*}

\subsection{Trustee keys}
\label{trustee-keys}

\begin{gather*}
  \pk=\G\qquad\sk=\Z_q\\
  \tpk=\left\{
    \begin{array}{rcl}
      \pok&:&\proof\\
      \pklabel&:&\pk
    \end{array}
  \right\}
\end{gather*}

A private key is a random number $x$ modulo $q$. The corresponding
$\pklabel$ is $X=g^x$. A $\tpk$ is a bundle of this public key with a
\hyperref[common]{$\proof$} of knowledge computed as follows:
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A=g^w$
\item $\challenge=\Hash_\pok(X,A)\mod q$
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
where $\Hash_\pok$ is computed as follows:
\[\Hash_\pok(X,A) = \shatwo(\verb=pok|=X\verb=|=A) \]
where $\pok$ and the vertical bars are verbatim and numbers are
written in base 10. The result is interpreted as a 256-bit big-endian
number. The proof is verified as follows:
\begin{enumerate}
\item compute $A={g^\response}/{y^\challenge}$
\item check that $\challenge=\Hash_\pok(\pklabel,A)\mod q$
\end{enumerate}

\subsection{Messages specific to threshold decryption support}

\subsubsection{Public key infrastructure}
\label{pki}

Establishing a public key so that threshold decryption is supported
requires private communications between trustees. To achieve this,
Belenios uses a custom public key infrastructure. During the key
establishment protocol, each trustee starts by generating a secret
seed (at random), then derives from it encryption and decryption keys,
as well as signing and verification keys. These four keys are then
used to exchange messages between trustees by using $A$ as a proxy.

The secret seed $s$ is a 22-character string, where characters are
taken from the set:
\[\texttt{123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz}\]

\paragraph{Deriving keys}

The (private) signing key $\textsf{sk}$ is derived by computing the
SHA256 of $s$ prefixed by the string \verb/sk|/. The corresponding
(public) verification key is $g^{\textsf{sk}}$. The (private)
decryption key $\textsf{dk}$ is derived by computing the SHA256 of $s$
prefixed by the string \verb/dk|/. The corresponding (public)
encryption key is $g^{\textsf{dk}}$.

\paragraph{Signing}

Signing takes a signing key $\textsf{sk}$ and a \textsf{message} $M$
(as a $\jstring$), computes a \textsf{signature} and produces a
$\texttt{signed\_msg}$. For the signature, we use a (Schnorr-like)
non-interactive zero-knowledge proof.

\begin{gather*}
  \texttt{signed\_msg}=\left\{
    \begin{array}{rcl}
      \textsf{message}&:&\jstring\\
      \textsf{signature}&:&\texttt{proof}
    \end{array}
  \right\}
\end{gather*}
To compute the \textsf{signature},
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute the commitment $A=g^w$
\item compute the \textsf{challenge} as
  $\textsf{SHA256}(\texttt{sigmsg|}M\texttt{|}A)$, where $A$ is written
  in base 10 and the result is interpreted as a 256-bit big-endian
  number
\item compute the \textsf{response} as
  $w-\textsf{sk}\times\textsf{challenge}\mod q$
\end{enumerate}
To verify a \textsf{signature} using a verification key \textsf{vk},
\begin{enumerate}
\item compute the commitment $A=g^{\textsf{response}}\times\textsf{vk}^{\textsf{challenge}}$
\item check that $\textsf{challenge}=\textsf{SHA256}(\texttt{sigmsg|}M\texttt{|}A)$
\end{enumerate}

\paragraph{Encrypting}

Encrypting takes an encryption key $\textsf{ek}$ and a message $M$ (as
a $\jstring$), computes an \texttt{encrypted\_msg} and serializes it
as a $\jstring$. We use an El Gamal-like system.

\begin{gather*}
  \texttt{encrypted\_msg}=\left\{
    \begin{array}{rcl}
      \textsf{alpha}&:&\G\\
      \textsf{beta}&:&\G\\
      \textsf{data}&:&\jstring
    \end{array}
  \right\}
\end{gather*}
To compute the \texttt{encrypted\_msg}:
\begin{enumerate}
\item pick random $r,s\in\Z_q$
\item compute $\textsf{alpha}=g^r$
\item compute $\textsf{beta}=\textsf{ek}^r\times g^s$
\item compute $\textsf{data}$ as the hexadecimal encoding of the (symmetric)
  encryption of $M$ using AES in CCM mode with
  $\textsf{SHA256}(g^s)$ as the key and $\textsf{SHA256}(g^r)$ as the
  initialization vector (where numbers are written in base 10)
\end{enumerate}
To decrypt an \texttt{encrypted\_msg} using a decryption key \textsf{dk}:
\begin{enumerate}
\item compute the symmetric key as $\textsf{SHA256}(\textsf{beta}/(\textsf{alpha}^{\textsf{dk}}))$
\item compute the initialization vector as $\textsf{SHA256}(\textsf{alpha})$
\item decrypt $\textsf{data}$
\end{enumerate}

\subsubsection{Certificates}
\label{certificates}

A certificate is a \texttt{signed\_msg} encapsulating a serialized
\texttt{cert\_keys} structure, itself filled with the public keys
generated as described in section~\ref{pki}.
\begin{gather*}
  \texttt{cert}=\texttt{signed\_msg}
  \qquad
  \texttt{cert\_keys}=\left\{
    \begin{array}{rcl}
      \textsf{verification}&:&\G\\
      \textsf{encryption}&:&\G
    \end{array}
  \right\}
\end{gather*}
The message is signed with the signing key associated to
\textsf{verification}.

\subsubsection{Channels}
\label{channels}

A \textsf{message} is sent securely from \textsf{sk} (a signing key)
to \textsf{recipient} (an encryption key) by encapsulating it in a
\texttt{channel\_msg}, serializing it as a $\jstring$, signing it with
\textsf{sk} and serializing the resulting \texttt{signed\_msg} as a
$\jstring$, and finally encrypting it with \textsf{recipient}. The
resulting $\jstring$ will be denoted by
$\textsf{send}(\textsf{sk},\textsf{recipient},\textsf{message})$, and
can be transmitted using a third-party (such as the election
administrator).
\begin{gather*}
  \texttt{channel\_msg}=\left\{
    \begin{array}{rcl}
      \textsf{recipient}&:&\G\\
      \textsf{message}&:&\G
    \end{array}
  \right\}
\end{gather*}

\subsubsection{Polynomials}
\label{polynomials}

Let $\Gamma=\gamma_1,\dotsc,\gamma_m$ be the certificates of all
trustees. We will denote by $\textsf{vk}_z$ (resp. $\textsf{ek}_z$)
the \textsf{verification} key (resp. the \textsf{encryption} key) of
$\gamma_z$. Each trustee must compute a \texttt{polynomial} structure
in step 3 of the key establishment protocol.
\begin{gather*}
  \texttt{polynomial}=\left\{
    \begin{array}{rcl}
      \textsf{polynomial}&:&\jstring\\
      \textsf{secrets}&:&\jstring^\ast\\
      \textsf{coefexps}&:&\texttt{coefexps}
    \end{array}
  \right\}
\end{gather*}
Suppose $T_i$ is the trustee who is computing. Therefore, $T_i$ knows
the signing key $\textsf{sk}$ corresponding to $\textsf{vk}_i$ and the
decryption key $\textsf{dk}$ corresponding to $\textsf{ek}_i$. $T_i$
first checks that keys indeed match. Then $T_i$ picks a random
polynomial
\[
  f_i(x)=a_{i0}+a_{i1}x+\dotsb+a_{it}x^t\in\Z_q[x]
\]
and computes $A_{ik}=g^{a_{ik}}$ for $k=0,\dotsc,t$ and
$s_{ij}=f_i(j)\mod q$ for $j=1,\dotsc,m$. $T_i$ then fills the
\texttt{polynomial} structure as follows:
\begin{itemize}
\item the \textsf{polynomial} field is
  $\textsf{send}(\textsf{sk},\textsf{ek}_i,M)$ where $M$ is a
  serialized \texttt{raw\_polynomial} structure
  \begin{gather*}
    \texttt{raw\_polynomial}=\left\{
      \begin{array}{rcl}
        \textsf{polynomial}&:&\Z_q^\ast
      \end{array}
    \right\}
  \end{gather*}
  filled with $a_{i0},\dotsc,a_{it}$
\item the \textsf{secrets} field is
  $\textsf{send}(\textsf{sk},\textsf{ek}_1,M_{i1}),\dotsc,\textsf{send}(\textsf{sk},\textsf{ek}_m,M_{im})$
  where $M_{ij}$ is a serialized \texttt{secret} structure
  \begin{gather*}
    \texttt{secret}=\left\{
      \begin{array}{rcl}
        \textsf{secret}&:&\Z_q
      \end{array}
    \right\}
  \end{gather*}
  filled with $s_{ij}$
\item the \textsf{coefexps} field is a signed message containing a
  serialized \texttt{raw\_coefexps} structure
  \begin{gather*}
    \texttt{coefexps}=\texttt{signed\_msg}
    \qquad
    \texttt{raw\_coefexps}=\left\{
      \begin{array}{rcl}
        \textsf{coefexps}&:&\G^\ast
      \end{array}
    \right\}
  \end{gather*}
  filled with $A_{i0},\dotsc,A_{it}$
\end{itemize}

\subsubsection{Vinputs}
\label{vinputs}

Once we receive all the \texttt{polynomial} structures
$P_1,\dotsc,P_m$, we compute (during step 4) input data (called
\texttt{vinput}) for a verification step performed later by the
trustees. Step 4 can be seen as a routing step.
\begin{gather*}
  \texttt{vinput}=\left\{
    \begin{array}{rcl}
      \textsf{polynomial}&:&\jstring\\
      \textsf{secrets}&:&\jstring^\ast\\
      \textsf{coefexps}&:&\texttt{coefexps}^\ast
    \end{array}
  \right\}
\end{gather*}
Suppose we are computing the \texttt{vinput} structure $\textsf{vi}_j$
for trustee $T_j$. We fill it as follows:
\begin{itemize}
\item the \textsf{polynomial} field is the same as the one of $P_j$
\item the \textsf{secret} field is
  $\textsf{secret}(P_1)_j,\dotsc,\textsf{secret}(P_m)_j$
\item the \textsf{coefexps} field is
  $\textsf{coefexps}(P_1),\dotsc,\textsf{coefexps}(P_m)$
\end{itemize}
Note that the \textsf{coefexps} field is the same for all trustees.

In step~5, $T_j$ checks consistency of $\textsf{vi}_j$ by unpacking it
and checking that, for $i=1,\dotsc,m$,
\[
g^{s_{ij}}=\prod_{k=0}^t(A_{ik})^{j^k}
\]

\subsubsection{Voutputs}
\label{voutputs}

In step 5 of the key establishment protocol, a trustee $T_j$ receives
$\Gamma$ and $\textsf{vi}_j$, and produces a \texttt{voutput}
$\textsf{vo}_j$.
\begin{gather*}
  \texttt{voutput}=\left\{
    \begin{array}{rcl}
      \textsf{private\_key}&:&\jstring\\
      \textsf{public\_key}&:&\texttt{trustee\_public\_key}
    \end{array}
  \right\}
\end{gather*}
Trustee $T_j$ fills $\textsf{vo}_j$ as follows:
\begin{itemize}
\item \textsf{private\_key} is set to
  $\textsf{send}(\textsf{sk},\textsf{ek}_j,S)$, where $S_j$ is $T_j$'s
  (private) decryption key:
  \[
    S_j=\sum_{i=1}^m s_{ij}\mod q
  \]
\item \textsf{public\_key} is set to a
  \hyperref[trustee-keys]{\texttt{trustee\_public\_key}} structure
  built using $S_j$ as private key.
\end{itemize}
The administrator checks $\textsf{vo}_j$ as follows:
\begin{itemize}
\item check that:
  \[
    \textsf{public\_key}(\textsf{public\_key}(\textsf{vo}_j))=\prod_{i=1}^m \prod_{k=0}^t (A_{ik})^{j^k}
  \]
\item check $\textsf{pok}(\textsf{public\_key}(\textsf{vo}_j))$
\end{itemize}

\subsubsection{Threshold parameters}
\label{threshold-params}

The \texttt{threshold\_parameters} structure embeds data that is
published during the election.
\begin{gather*}
  \texttt{threshold\_parameters}=\left\{
    \begin{array}{rcl}
      \textsf{threshold}&:&\I\\
      \textsf{certs}&:&\texttt{cert}^\ast\\
      \textsf{coefexps}&:&\texttt{coefexps}^\ast\\
      \textsf{verification\_keys}&:&\texttt{trustee\_public\_key}^\ast
    \end{array}
  \right\}
\end{gather*}
The administrator fills it as follows:
\begin{itemize}
\item \textsf{threshold} is set to $t+1$
\item \textsf{certs} is set to $\Gamma=\gamma_1,\dotsc,\gamma_m$
\item \textsf{coefexps} is set to the same value as the
  \textsf{coefexps} field of \texttt{vinput}s
\item \textsf{verification\_keys} is set to
  $\textsf{public\_key}(\textsf{vo}_1),\dotsc,\textsf{public\_key}(\textsf{vo}_m)$
\end{itemize}

\subsection{Credentials}
\label{credentials}

\newcommand{\secret}{\texttt{secret}}

A secret \emph{credential} $c$ is a 15-character string, where characters are
taken from the set:
\[\texttt{123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz}\]
The first 14 characters are random, and the last one is a checksum to
detect typing errors. To compute the checksum, each character is
interpreted as a base 58 digit: $\texttt{1}$ is $0$, $\texttt{2}$ is
$1$, \dots, $\texttt{z}$ is $57$. The first 14 characters are
interpreted as a big-endian number $c_1$ The checksum is $53-c_1\mod
53$.

From this string, a secret exponent $s=\secret(c)$ is derived by using
PBKDF2 (RFC 2898) with:
\begin{itemize}
\item $c$ as password;
\item HMAC-SHA256 (RFC 2104, FIPS PUB 180-2) as pseudorandom function;
\item the $\uuid$ (interpreted as a 16-byte array) of the election as
  salt;
\item $1000$ iterations
\end{itemize}
and an output size of 1 block, which is interpreted as a big-endian
256-bit number and then reduced modulo $q$ to form $s$.  From this
secret exponent, a public key $\public(c)=g^s$ is computed.

\subsection{Election}
\label{elections}

\newcommand{\question}{\texttt{question}}

\begin{gather*}
  \texttt{wrapped\_pk}=\left\{
    \begin{array}{rcl}
      \textsf{g}&:&\G\\
      \textsf{p}&:&\N\\
      \textsf{q}&:&\N\\
      \textsf{y}&:&\G
    \end{array}
  \right\}
\end{gather*}
The election public key, which is denoted by $y$ thoughout this
document, is computed during the setup phase, and bundled with the
group parameters in a \texttt{wrapped\_pk} structure.

\newcommand{\blank}{\textsf{blank}}
\newcommand{\minlabel}{\textsf{min}}
\newcommand{\maxlabel}{\textsf{max}}
\newcommand{\answers}{\textsf{answers}}

\begin{gather*}
  \question=\left\{
    \begin{array}{rcl}
      \answers&:&\jstring^\ast\\
      ?\blank&:&\B\\
      \minlabel&:&\I\\
      \maxlabel&:&\I\\
      \textsf{question}&:&\jstring
    \end{array}
  \right\}
  \qquad
  \election=\left\{
    \begin{array}{rcl}
      \textsf{description}&:&\jstring\\
      \textsf{name}&:&\jstring\\
      \textsf{public\_key}&:&\texttt{wrapped\_pk}\\
      \textsf{questions}&:&\texttt{question}^\ast\\
      \textsf{uuid}&:&\texttt{uuid}
    \end{array}
  \right\}
\end{gather*}

The $\blank$ field of $\question$ is optional. When present and true,
the voter can vote blank for this question. In a blank vote, all
answers are set to $0$ regardless of the values of $\minlabel$ and
$\maxlabel$ ($\minlabel$ doesn't need to be $0$).

\newcommand{\answer}{\texttt{answer}}
\newcommand{\signature}{\texttt{signature}}
\newcommand{\iproofs}{\textsf{individual\_proofs}}
\newcommand{\oproof}{\textsf{overall\_proof}}
\newcommand{\bproof}{\textsf{blank\_proof}}
\newcommand{\choices}{\textsf{choices}}
\newcommand{\iprove}{\textsf{iprove}}

During an election, the following data needs to be public in order to
verify the setup phase and to validate ballots:
\begin{itemize}
\item the $\election$ structure described above;
\item all the $\tpk$s, or the
  $\texttt{threshold\_parameters}$, that were generated during the
  \hyperref[election-setup]{setup phase};
\item the set $L$ of public credentials.
\end{itemize}

\subsection{Encrypted answers}
\label{answers}

\begin{gather*}
  \answer=\left\{
    \begin{array}{rcl}
      \choices&:&\ciphertext^\ast\\
      \iproofs&:&\iproof^\ast\\
      \oproof&:&\iproof\\
      ?\bproof&:&\proof^2
    \end{array}
  \right\}
\end{gather*}

An answer to a \hyperref[elections]{$\question$} is the vector
$\choices$ of encrypted weights given to each answer. When $\blank$ is
false (or absent), a blank vote is not allowed and this vector has the
same length as $\answers$; otherwise, a blank vote is allowed and this
vector has an additionnal leading weight corresponding to whether the
vote is blank or not.  Each weight comes with a proof (in \iproofs,
same length as \choices) that it is $0$ or $1$. The whole answer also
comes with additional proofs that weights respect constraints.

More concretely, each weight $m\in[0\dots1]$ is encrypted (in an El
Gamal-like fashion) into a $\ciphertext$ as follows:
\begin{enumerate}
\item pick a random $r\in\Z_q$
\item $\alphalabel=g^r$
\item $\betalabel=y^rg^m$
\end{enumerate}
where $y$ is the election public key.

To compute the proofs, the voter needs a
\hyperref[credentials]{credential} $c$. Let $s=\secret(c)$, and
$S=g^s$ written in base 10. The individual proof that $m\in[0\dots1]$
is computed by running $\iprove(S,r,m,0,1)$ (see
section~\ref{iproof}).

When a blank vote is not allowed, $\oproof$ proves that
$M\in[\minlabel\dots\maxlabel]$ and is computed by running
$\iprove(S,R,M-\minlabel,\minlabel,\dots,\maxlabel)$ where $R$ is the
sum of the $r$ used in ciphertexts, and $M$ the sum of the $m$. There
is no $\bproof$.

When a blank vote is allowed, and there are $n$ choices, the answer is
modeled as a vector $(m_0,m_1,\dotsc,m_n)$, when $m_0$ is whether this
is a blank vote or not, and $m_i$ (for $i>0$) is whether choice $i$
has been selected. Each $m_i$ is encrypted and proven equal to $0$ or
$1$ as above. Let $m_\Sigma=m_1+\dotsb+m_n$. The additionnal proofs
are as follows:
\begin{itemize}
\item $\bproof$ proves that $m_0=0\lor m_\Sigma=0$;
\item $\oproof$ proves that $m_0=1\lor m_\Sigma\in[\minlabel\dots\maxlabel]$.
\end{itemize}
They are computed as described in section~\ref{bproof}.

\subsection{Proofs of interval membership}
\label{iproof}

\begin{gather*}
  \iproof=\proof^\ast
\end{gather*}

Given a pair $(\alpha,\beta)$ of group elements, one can prove that it
has the form $(g^r,y^rg^{M_i})$ with $M_i\in[M_0,\dots,M_k]$ by
creating a sequence of $\proof$s $\pi_0,\dots,\pi_k$ with the
following procedure, parameterised by a group element $S$:
\begin{enumerate}
\item for $j\neq i$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$
  \item compute
    \[A_j=\frac{g^\response}{\alpha^\challenge}\quad\text{and}\quad
    B_j=\frac{y^\response}{(\beta/g^{M_j})^\challenge}\]
  \end{enumerate}
\item $\pi_i$ is created as follows:
  \begin{enumerate}
  \item pick a random $w\in\Z_q$
  \item compute $A_i=g^w$ and $B_i=y^w$
  \item $\challenge(\pi_i)=\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)-\sum_{j\neq
      i}\challenge(\pi_j)\mod q$
  \item $\response(\pi_i)=w+r\times\challenge(\pi_i)\mod q$
  \end{enumerate}
\end{enumerate}
In the above, $\Hash_\iprove$ is computed as follows:
\[\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)=\shatwo(\verb=prove|=S\verb=|=\alpha\verb=,=\beta\verb=|=A_0\verb=,=B_0\verb=,=\dots\verb=,=A_k\verb=,=B_k)\mod q\]
where \verb=prove=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number. We will denote the whole procedure by
$\iprove(S,r,i,M_0,\dots,M_k)$.

The proof is verified as follows:
\begin{enumerate}
\item for $j\in[0\dots k]$, compute
  \[A_j=\frac{g^{\response(\pi_j)}}{\alpha^{\challenge(\pi_j)}}\quad\text{and}\quad
  B_j=\frac{y^{\response(\pi_j)}}{(\beta/g^{M_j})^{\challenge(\pi_j)}}\]
\item check that
  \[\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)=\sum_{j\in[0\dots
    k]}\challenge(\pi_j)\mod q\]
\end{enumerate}

\subsection{Proofs of possibly-blank votes}
\label{bproof}

In this section, we suppose:
\[
(\alpha_0,\beta_0)=(g^{r_0},y^{r_0}g^{m_0})
\quad\text{and}\quad
(\alpha_\Sigma,\beta_\Sigma)=(g^{r_\Sigma},y^{r_\Sigma}g^{m_\Sigma})
\]
Note that $\alpha_\Sigma$, $\beta_\Sigma$ and $r_\Sigma$ can be easily
computed from the encryptions of $m_1,\dotsc,m_n$ and their associated
secrets.

Additionnally, let $P$ be the string
``$g\verb=,=y\verb=,=\alpha_0\verb=,=\beta_0\verb=,=\alpha_\Sigma\verb=,=\beta_\Sigma$'',
where the commas are verbatim and the numbers are written in base
10. Let also $M_1,\dotsc,M_k$ be the sequence
$\minlabel,\dots,\maxlabel$ ($k=\maxlabel-\minlabel+1$).

\subsubsection{Non-blank votes ($m_0=0$)}
\label{non-blank-votes}

\paragraph{Computing \bproof}
In $m_0=0\lor m_\Sigma=0$, the first case is true. The proof $\bproof$
of the whole statement is the couple of proofs $(\pi_0,\pi_\Sigma)$
built as follows:
\begin{enumerate}
\item pick random $\challenge(\pi_\Sigma)$ and $\response(\pi_\Sigma)$
  in $\Z_q$
\item compute
  $A_\Sigma=g^{\response(\pi_\Sigma)}\times\alpha_\Sigma^{\challenge(\pi_\Sigma)}$
  and
  $B_\Sigma=y^{\response(\pi_\Sigma)}\times\beta_\Sigma^{\challenge(\pi_\Sigma)}$
\item pick a random $w$ in $\Z_q$
\item compute $A_0=g^w$ and $B_0=y^w$
\item compute \[\challenge(\pi_0)=\Hash_{\mathsf{bproof0}}(S,P,A_0,B_0,A_\Sigma,B_\Sigma)-\challenge(\pi_\Sigma)\mod q\]
\item compute $\response(\pi_0)=w-r_0\times\challenge(\pi_0)\mod q$
\end{enumerate}
In the above, $\Hash_{\mathsf{bproof0}}$ is computed as follows:
\[\Hash_{\mathsf{bproof0}}(\dotsc)=
\shatwo(\verb=bproof0|=S\verb=|=P\verb=|=A_0\verb=,=B_0\verb=,=A_\Sigma\verb=,=B_\Sigma)\mod q\]
where \verb=bproof0=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

\paragraph{Computing \oproof}
In $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$, the second case
is true. Let $i$ be such that $m_\Sigma=M_i$. The proof of the whole
statement is a $(k+1)$-tuple $(\pi_0,\pi_1,\dotsc,\pi_k)$ built as
follows:
\begin{enumerate}
\item pick random $\challenge(\pi_0)$ and $\response(\pi_0)$
  in $\Z_q$
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times(\beta_0/g)^{\challenge(\pi_0)}$
\item for $j>0$ and $j\neq i$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$ in $\Z_q$
  \item compute
    $A_j={g^\response}\times{\alpha_\Sigma^\challenge}$ and
    $B_j={y^\response}\times{(\beta_\Sigma/g^{M_j})^\challenge}$
  \end{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A_i=g^w$ and $B_i=y^w$
\item compute
  \[\challenge(\pi_i)=\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)-\sum_{j\neq i}\challenge(\pi_j)\mod q\]
\item compute $\response(\pi_i)=w-r_\Sigma\times\challenge(\pi_i)\mod q$
\end{enumerate}
In the above, $\Hash_{\mathsf{bproof1}}$ is computed as follows:
\[\Hash_{\mathsf{bproof1}}(\dotsc)=
\shatwo(\verb=bproof1|=S\verb=|=P\verb=|=A_0\verb=,=B_0\verb=,=\dotsc\verb=,=A_k\verb=,=B_k)\mod q\]
where \verb=bproof1=, the vertical bars and the commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

\subsubsection{Blank votes ($m_0=1$)}

\paragraph{Computing \bproof}
In $m_0=0\lor m_\Sigma=0$, the second case is true. The proof
$\bproof$ of the whole statement is the couple of proofs
$(\pi_0,\pi_\Sigma)$ built as in section~\ref{non-blank-votes}, but
exchanging subscripts $0$ and $\Sigma$ everywhere except in the call
to $\Hash_{\textsf{bproof0}}$.

\paragraph{Computing \oproof}
In $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$, the first case is
true. The proof of the whole statement is a $(k+1)$-tuple
$(\pi_0,\pi_1,\dotsc,\pi_k)$ built as follows:
\begin{enumerate}
\item for $j>0$:
  \begin{enumerate}
  \item create $\pi_j$ with a random $\challenge$ and a random
    $\response$ in $\Z_q$
  \item compute
    $A_j={g^\response}\times{\alpha_\Sigma^\challenge}$ and
    $B_j={y^\response}\times{(\beta_\Sigma/g^{M_j})^\challenge}$
  \end{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A_0=g^w$ and $B_0=y^w$
\item compute
  \[\challenge(\pi_0)=\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)-\sum_{j>0}\challenge(\pi_j)\mod q\]
\item compute $\response(\pi_0)=w-r_0\times\challenge(\pi_0)\mod q$
\end{enumerate}

\subsubsection{Verifying proofs}

\paragraph{Verifying \bproof}
A proof of $m_0=0\lor m_\Sigma=0$ is a couple of proofs
$(\pi_0,\pi_\Sigma)$ such that the following procedure passes:
\begin{enumerate}
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times\beta_0^{\challenge(\pi_0)}$
\item compute
  $A_\Sigma=g^{\response(\pi_\Sigma)}\times\alpha_\Sigma^{\challenge(\pi_\Sigma)}$
  and
  $B_\Sigma=y^{\response(\pi_\Sigma)}\times\beta_\Sigma^{\challenge(\pi_\Sigma)}$
\item check that
  \[\Hash_{\mathsf{bproof0}}(S,P,A_0,B_0,A_\Sigma,B_\Sigma)=\challenge(\pi_0)+\challenge(\pi_\Sigma)\mod q\]
\end{enumerate}

\paragraph{Verifying \oproof}
A proof of $m_0=1\lor m_\Sigma\in[M_1\dots M_k]$ is a $(k+1)$-tuple
$(\pi_0,\pi_1,\dotsc,\pi_k)$ such that the following procedure passes:
\begin{enumerate}
\item compute
  $A_0=g^{\response(\pi_0)}\times\alpha_0^{\challenge(\pi_0)}$
  and
  $B_0=y^{\response(\pi_0)}\times(\beta_0/g)^{\challenge(\pi_0)}$
\item for $j>0$, compute
  \[A_j=g^{\response(\pi_j)}\times\alpha_j^{\challenge(\pi_j)}
  \quad\text{and}\quad
  B_j=y^{\response(\pi_j)}\times(\beta_j/g^{M_j})^{\challenge(\pi_j)}\]
\item check that
  \[\Hash_{\textsf{bproof1}}(S,P,A_0,B_0,\dots,A_k,B_k)=\sum_{j=0}^k\challenge(\pi_j)\mod q\]
\end{enumerate}

\subsection{Signatures}
\label{signatures}

\begin{gather*}
  \signature=\left\{
    \begin{array}{rcl}
      \pklabel&:&\pk\\
      \challenge&:&\Z_q\\
      \response&:&\Z_q
    \end{array}
  \right\}
\end{gather*}

\newcommand{\siglabel}{\textsf{signature}}

Each ballot contains a (Schnorr-like) digital signature to avoid ballot stuffing. The
signature needs a \hyperref[credentials]{credential} $c$ and uses all
the \ciphertext{}s $\gamma_1,\dots,\gamma_l$ that appear in the ballot
($l$ is the sum of the lengths of $\choices$). It is computed as
follows:
\begin{enumerate}
\item compute $s=\secret(c)$
\item pick a random $w\in\Z_q$
\item compute $A=g^w$
\item $\pklabel=g^s$
\item $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
\item $\response=w-s\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\siglabel$ is computed as follows:
\[
\Hash_\siglabel(S,A,\gamma_1,\dots,\gamma_l)=\shatwo(\verb=sig|=S\verb=|=A\verb=|=\alphalabel(\gamma_1)\verb=,=\betalabel(\gamma_1)\verb=,=\dots\verb=,=\alphalabel(\gamma_l)\verb=,=\betalabel(\gamma_l))
\]
where \verb=sig=, the vertical bars and commas are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

Signatures are verified as follows:
\begin{enumerate}
\item compute $A=g^\response\times \pklabel^\challenge$
\item check that $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
\end{enumerate}

\subsection{Ballots}
\label{ballots}

\newcommand{\json}{\textsf{JSON}}

\begin{gather*}
  \ballot=\left\{
    \begin{array}{rcl}
      \answers&:&\hyperref[answers]{\answer}^\ast\\
      \textsf{election\_hash}&:&\jstring\\
      \textsf{election\_uuid}&:&\uuid\\
      \siglabel&:&\hyperref[signatures]{\signature}
    \end{array}
  \right\}
\end{gather*}
The so-called hash (or \emph{fingerprint}) of the election
is computed with the function $\Hash_\json$:
\[
\Hash_\json(J)=\basesixfour(\shatwo(J))
\]
Where $J$ is the serialization (done by the server) of the $\election$
structure.

The same hashing function is used on a serialization (done by the
voting client) of the $\ballot$ structure to produce a so-called
\emph{smart ballot tracker}.

\subsection{Tally}
\label{tally}

\begin{gather*}
  \etally=\ciphertext^\ast{}^\ast
\end{gather*}
The encrypted tally is the pointwise product of the ciphertexts of all
accepted ballots:
\[
\begin{array}{rcl}
\alphalabel(\etally_{i,j})&=&\prod\alphalabel(\choices(\answers(\ballot)_i)_j)\\
\betalabel(\etally_{i,j})&=&\prod\betalabel(\choices(\answers(\ballot)_i)_j)
\end{array}
\]

\newcommand{\dfactors}{\textsf{decryption\_factors}}
\newcommand{\dproofs}{\textsf{decryption\_proofs}}
\newcommand{\decrypt}{\textsf{decrypt}}

\begin{gather*}
  \pdecryption=\left\{
    \begin{array}{rcl}
      \dfactors&:&\G^\ast{}^\ast\\
      \dproofs&:&\proof^\ast{}^\ast
    \end{array}
  \right\}
\end{gather*}
From the encrypted tally, each trustee computes a partial decryption
using the \hyperref[trustee-keys]{private key} $x$ (and the
corresponding public key $X=g^x$) he generated during election
setup. It consists of so-called decryption factors:
\[
\dfactors_{i,j}=\alphalabel(\etally_{i,j})^x
\]
and proofs that they were correctly computed. Each $\dproofs_{i,j}$ is
computed as follows:
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A=g^w$ and $B=\alphalabel(\etally_{i,j})^w$
\item $\challenge=\Hash_\decrypt(X,A,B)$
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\decrypt$ is computed as follows:
\[
\Hash_\decrypt(X,A,B)=\shatwo(\verb=decrypt|=X\verb=|=A\verb=,=B)\mod q
\]
where \verb=decrypt=, the vertical bars and the comma are verbatim and
numbers are written in base 10. The result is interpreted as a 256-bit
big-endian number.

These proofs are verified using the $\tpk$ structure $k$ that the
trustee sent to the administrator during the election setup:
\begin{enumerate}
\item compute
\[
A=\frac{g^\response}{\pklabel(k)^\challenge}
\quad\text{and}\quad
B=\frac{\alphalabel(\etally_{i,j})^\response}{\dfactors_{i,j}^\challenge}
\]
\item check that $\Hash_\decrypt(\pklabel(k),A,B)=\challenge$
\end{enumerate}

\subsection{Election result}
\label{election-result}

\newcommand{\ntallied}{\textsf{num\_tallied}}
\newcommand{\etallylabel}{\textsf{encrypted\_tally}}
\newcommand{\pdlabel}{\textsf{partial\_decryptions}}
\newcommand{\resultlabel}{\textsf{result}}

\begin{gather*}
  \result=\left\{
    \begin{array}{rcl}
      \ntallied&:&\I\\
      \etallylabel&:&\etally\\
      \pdlabel&:&\pdecryption^\ast\\
      \resultlabel&:&\I^\ast{}^\ast
    \end{array}
  \right\}
\end{gather*}
The decryption factors are combined for each ciphertext to build
synthetic ones $F_{i,j}$. With basic decryption support:
\[
F_{i,j}=\prod_{z\in[1\dots m]}\pdlabel_{z,i,j}
\]
where $m$ is the number of trustees. With threshold decryption
support:
\[
F_{i,j}=\prod_{z\in\mathcal{I}}(\pdlabel_{z,i,j})^{\lambda_z^{\mathcal{I}}}
\]
where $\mathcal{I}=\{z_1,\dotsc,z_{t+1}\}$ is the set of indexes of
supplied partial decryptions, and $\lambda_z^{\mathcal{I}}$ are the
Lagrange coefficients:
\[
  \lambda_z^{\mathcal{I}}=\prod_{k\in\mathcal{I}\backslash\{z\}}\frac{k}{k-z}\mod q
\]

The $\resultlabel$ field of the $\result$ structure is then computed
as follows:
\[
\resultlabel_{i,j}=\log_g\left(\frac{\betalabel(\etallylabel_{i,j})}{F_{i,j}}\right)
\]
Here, the discrete logarithm can be easily computed because it is
bounded by $\ntallied$.

After the election, the following data needs to be public in order to
verify the tally:
\begin{itemize}
\item the $\election$ structure;
\item all the $\tpk$s, or the $\texttt{threshold\_parameters}$, that
  were generated during the \hyperref[election-setup]{setup phase};
\item the set of public credentials;
\item the set of ballots;
\item the $\result$ structure described above.
\end{itemize}

{'fraction_non_alphanumeric': 0.17435493970873941, 'fraction_numerical': 0.010404457218092194, 'mean_word_length': 4.434729493891798, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4187581', 'n_tokens_mistral': 23055, 'n_tokens_neox': 22162, 'n_words': 5896}