specification.tex 38.3 KB
Newer Older
1
2
3
4
5
\documentclass[a4paper]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
6
7
\usepackage{amsmath}
\usepackage{bbm}
8
9
\usepackage{hyperref}

10
\newcommand{\version}{1.5}
11

12
13
14
15
16
\newcommand{\F}{\mathbbm{F}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\I}{\mathbbm{I}}
17
\newcommand{\B}{\mathbbm{B}}
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

\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}}

33
34
35
36
37
\newcommand{\cert}{\texttt{cert}}
\newcommand{\poly}{\texttt{polynomial}}
\newcommand{\vinput}{\texttt{vinput}}
\newcommand{\voutput}{\texttt{voutput}}

38
39
\title{Belenios specification}
\date{Version~\version}
40
41
42
43
44
45
\author{Stéphane Glondu}

\begin{document}
\maketitle
\tableofcontents

46
47
48
49
50
51
52
53
54
55
56
\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
Stephane Glondu's avatar
Stephane Glondu committed
57
subgroup of $\F^*_p$ (hence, all exponentiations are implicitly done
58
59
modulo $p$). We suppose the group parameters are agreed on
beforehand. Default group parameters are given as examples in
60
section~\ref{default-group}.
61

Stephane Glondu's avatar
Stephane Glondu committed
62
\section{Parties}
63
64

\begin{itemize}
65
66
67
68
69
\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
70
71
\end{itemize}

72
73
74
75
\section{Processes}
\label{processes}

\subsection{Election setup}
76
\label{election-setup}
77
78
79
80
81
82
83
84
85
86
87
88

\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$
89
90
91
92
93
94
95
96
97
98
99
100
101
\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}
102
\item for $z\in[1\dots m]$,
103
  \begin{enumerate}
104
  \item $T_z$ generates a \hyperref[trustee-keys]{$\tpk$} $k_z$ and
105
    sends it to $A$
106
  \item $A$ checks $k_z$
107
108
109
  \end{enumerate}
\item $A$ combines all the trustee public keys into the election
  public key $y$
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
\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
139
  \item $T_z$ computes a \hyperref[voutputs]{$\voutput$} $\textsf{vo}_z$ and
140
141
142
143
144
    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}
145
146
147
148
149
150
151
\end{enumerate}

\subsection{Vote}

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

\subsection{Credential recovery}

157
\begin{enumerate}
158
159
160
161
162
163
164
165
166
167
168
169
170
\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$
171
172
\item for $z\in[1\dots m]$ (or, if in threshold mode, a subset of it
  of size at least $t+1$),
173
  \begin{enumerate}
174
  \item $A$ sends $\Pi$ (and $K_z$ if in threshold mode) to $T_z$
175
  \item $T_z$ generates a \hyperref[tally]{$\pdecryption$} $\delta_z$
176
    and sends it to $A$
177
  \item $A$ verifies $\delta_z$
178
  \end{enumerate}
179
180
\item $A$ combines all the partial decryptions, computes and publishes
  the election \hyperref[election-result]{\result}
181
182
\end{enumerate}

183
184
185
186
\section{Messages}
\label{messages}

\subsection{Conventions}
187

188
189
190
191
192
193
194
195
196
197
198
199
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
200
\item $\B$: boolean, encoded as a JSON boolean
201
202
203
204
205
206
207
208
209
210
\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}}
211
\newcommand{\iproof}{\texttt{iproof}}
212
213
214
215
216
217
218
219
220
\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}}
221
222

\begin{gather*}
223
  \proof=\left\{
224
    \begin{array}{rcl}
225
226
      \challenge&:&\Z_q\\
      \response&:&\Z_q
227
228
229
    \end{array}
  \right\}
  \qquad
230
  \ciphertext=\left\{
231
    \begin{array}{rcl}
232
233
      \alphalabel&:&\G\\
      \betalabel&:&\G
234
235
236
237
    \end{array}
  \right\}
\end{gather*}

238
239
\subsection{Trustee keys}
\label{trustee-keys}
240
241

\begin{gather*}
242
243
  \pk=\G\qquad\sk=\Z_q\\
  \tpk=\left\{
244
    \begin{array}{rcl}
245
246
      \pok&:&\proof\\
      \pklabel&:&\pk
247
248
    \end{array}
  \right\}
249
250
251
\end{gather*}

A private key is a random number $x$ modulo $q$. The corresponding
252
$\pklabel$ is $X=g^x$. A $\tpk$ is a bundle of this public key with a
253
254
255
256
\hyperref[common]{$\proof$} of knowledge computed as follows:
\begin{enumerate}
\item pick a random $w\in\Z_q$
\item compute $A=g^w$
257
\item $\challenge=\Hash_\pok(X,A)\mod q$
258
259
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
260
261
262
263
264
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:
265
266
\begin{enumerate}
\item compute $A={g^\response}/{y^\challenge}$
267
\item check that $\challenge=\Hash_\pok(\pklabel,A)\mod q$
268
269
\end{enumerate}

270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
\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
350
  $\textsf{SHA256}(\texttt{key|}g^s)$ as the key and $\textsf{SHA256}(\texttt{iv|}g^r)$ as the
351
352
353
354
  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}
355
356
\item compute the symmetric key as $\textsf{SHA256}(\texttt{key|}\textsf{beta}/(\textsf{alpha}^{\textsf{dk}}))$
\item compute the initialization vector as $\textsf{SHA256}(\texttt{iv|}\textsf{alpha})$
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
\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\\
395
      \textsf{message}&:&\jstring
396
397
398
    \end{array}
  \right\}
\end{gather*}
Stephane Glondu's avatar
Stephane Glondu committed
399
When decoding such a message, \textsf{recipient} must be checked.
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418

\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
419
420
the signing key $\textsf{sk}_i$ corresponding to $\textsf{vk}_i$ and the
decryption key $\textsf{dk}_i$ corresponding to $\textsf{ek}_i$. $T_i$
421
422
423
424
425
426
427
428
429
430
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
431
  $\textsf{send}(\textsf{sk}_i,\textsf{ek}_i,M)$ where $M$ is a
432
433
434
435
436
437
438
439
440
441
  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
442
  $\textsf{send}(\textsf{sk}_i,\textsf{ek}_1,M_{i1}),\dotsc,\textsf{send}(\textsf{sk}_i,\textsf{ek}_m,M_{im})$
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
  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
516
  $\textsf{send}(\textsf{sk}_j,\textsf{ek}_j,S_j)$, where $S_j$ is $T_j$'s
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
  (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}

559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
\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*}
593
  \texttt{wrapped\_pk}=\left\{
594
    \begin{array}{rcl}
595
596
      \textsf{g}&:&\G\\
      \textsf{p}&:&\N\\
597
      \textsf{q}&:&\N\\
598
      \textsf{y}&:&\G
599
600
601
    \end{array}
  \right\}
\end{gather*}
602
The election public key, which is denoted by $y$ thoughout this
603
604
document, is computed during the setup phase, and bundled with the
group parameters in a \texttt{wrapped\_pk} structure.
605

606
\newcommand{\blank}{\textsf{blank}}
607
608
609
\newcommand{\minlabel}{\textsf{min}}
\newcommand{\maxlabel}{\textsf{max}}
\newcommand{\answers}{\textsf{answers}}
610
611

\begin{gather*}
612
  \question=\left\{
613
    \begin{array}{rcl}
614
      \answers&:&\jstring^\ast\\
615
      ?\blank&:&\B\\
616
617
618
      \minlabel&:&\I\\
      \maxlabel&:&\I\\
      \textsf{question}&:&\jstring
619
620
621
    \end{array}
  \right\}
  \qquad
622
  \election=\left\{
623
624
625
626
627
    \begin{array}{rcl}
      \textsf{description}&:&\jstring\\
      \textsf{name}&:&\jstring\\
      \textsf{public\_key}&:&\texttt{wrapped\_pk}\\
      \textsf{questions}&:&\texttt{question}^\ast\\
628
      \textsf{uuid}&:&\texttt{uuid}
629
630
631
632
    \end{array}
  \right\}
\end{gather*}

633
634
635
636
637
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$).

638
639
640
641
\newcommand{\answer}{\texttt{answer}}
\newcommand{\signature}{\texttt{signature}}
\newcommand{\iproofs}{\textsf{individual\_proofs}}
\newcommand{\oproof}{\textsf{overall\_proof}}
642
\newcommand{\bproof}{\textsf{blank\_proof}}
643
\newcommand{\choices}{\textsf{choices}}
644
\newcommand{\iprove}{\textsf{iprove}}
645

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

656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
\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.

679
680
More concretely, each weight $m\in[0\dots1]$ is encrypted (in an El
Gamal-like fashion) into a $\ciphertext$ as follows:
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
\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}.

712
\subsection{Proofs of interval membership}
713
\label{iproof}
714
715

\begin{gather*}
716
  \iproof=\proof^\ast
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
\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$
736
  \item $\challenge(\pi_i)=\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)-\sum_{j\neq
737
738
739
740
      i}\challenge(\pi_j)\mod q$
  \item $\response(\pi_i)=w+r\times\challenge(\pi_i)\mod q$
  \end{enumerate}
\end{enumerate}
741
In the above, $\Hash_\iprove$ is computed as follows:
742
\[\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\]
743
744
745
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
746
$\iprove(S,r,i,M_0,\dots,M_k)$.
747
748
749
750

The proof is verified as follows:
\begin{enumerate}
\item for $j\in[0\dots k]$, compute
Stephane Glondu's avatar
Stephane Glondu committed
751
752
  \[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)}}\]
753
\item check that
754
  \[\Hash_\iprove(S,\alpha,\beta,A_0,B_0,\dots,A_k,B_k)=\sum_{j\in[0\dots
755
756
757
    k]}\challenge(\pi_j)\mod q\]
\end{enumerate}

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

761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
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.
802

803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
\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.
835

836
837
838
839
840
841
842
843
844
845
846
847
848
\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:
849
\begin{enumerate}
850
851
852
853
854
855
856
857
858
859
860
861
862
\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$
863
864
\end{enumerate}

865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
\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}
898
899
900
901
902

\subsection{Signatures}
\label{signatures}

\begin{gather*}
903
  \signature=\left\{
904
    \begin{array}{rcl}
905
906
907
      \pklabel&:&\pk\\
      \challenge&:&\Z_q\\
      \response&:&\Z_q
908
909
    \end{array}
  \right\}
910
911
912
913
\end{gather*}

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

914
Each ballot contains a (Schnorr-like) digital signature to avoid ballot stuffing. The
915
916
917
918
919
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}
Stephane Glondu's avatar
Stephane Glondu committed
920
\item compute $s=\secret(c)$
921
\item pick a random $w\in\Z_q$
Stephane Glondu's avatar
Stephane Glondu committed
922
923
924
\item compute $A=g^w$
\item $\pklabel=g^s$
\item $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
925
926
927
928
\item $\response=w-s\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\siglabel$ is computed as follows:
\[
Stephane Glondu's avatar
Stephane Glondu committed
929
\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))
930
931
932
933
934
935
936
\]
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}
Stephane Glondu's avatar
Stephane Glondu committed
937
\item compute $A=g^\response\times \pklabel^\challenge$
Stephane Glondu's avatar
Stephane Glondu committed
938
\item check that $\challenge=\Hash_\siglabel(\pklabel,A,\gamma_1,\dots,\gamma_l)\mod q$
939
940
941
942
943
944
945
946
\end{enumerate}

\subsection{Ballots}
\label{ballots}

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

\begin{gather*}
947
  \ballot=\left\{
948
    \begin{array}{rcl}
949
950
951
952
      \answers&:&\hyperref[answers]{\answer}^\ast\\
      \textsf{election\_hash}&:&\jstring\\
      \textsf{election\_uuid}&:&\uuid\\
      \siglabel&:&\hyperref[signatures]{\signature}
953
954
    \end{array}
  \right\}
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
\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*}
988
  \pdecryption=\left\{
989
    \begin{array}{rcl}
990
991
      \dfactors&:&\G^\ast{}^\ast\\
      \dproofs&:&\proof^\ast{}^\ast
992
993
994
    \end{array}
  \right\}
\end{gather*}
995
From the encrypted tally, each trustee computes a partial decryption
996
997
998
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:
999
1000
1001
1002
1003
1004
1005
1006
\[
\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$
1007
\item $\challenge=\Hash_\decrypt(X,A,B)$
1008
1009
1010
1011
\item $\response=w+x\times\challenge\mod q$
\end{enumerate}
In the above, $\Hash_\decrypt$ is computed as follows:
\[
1012
\Hash_\decrypt(X,A,B)=\shatwo(\verb=decrypt|=X\verb=|=A\verb=,=B)\mod q
1013
\]
1014
1015
1016
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.
1017

1018
1019
1020
1021
1022
1023
1024
1025
1026
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}
\]
1027
\item check that $\Hash_\decrypt(\pklabel(k),A,B)=\challenge$
1028
\end{enumerate}
1029

1030
1031
\subsection{Election result}
\label{election-result}
1032

1033
1034
1035
1036
\newcommand{\ntallied}{\textsf{num\_tallied}}
\newcommand{\etallylabel}{\textsf{encrypted\_tally}}
\newcommand{\pdlabel}{\textsf{partial\_decryptions}}
\newcommand{\resultlabel}{\textsf{result}}
1037

1038
\begin{gather*}
1039
  \result=\left\{
1040
1041
1042
1043
1044
1045
1046
1047
1048
    \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
1049
synthetic ones $F_{i,j}$. With basic decryption support:
1050
1051
1052
\[
F_{i,j}=\prod_{z\in[1\dots m]}\pdlabel_{z,i,j}
\]
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
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:
1067
1068
1069
\[
\resultlabel_{i,j}=\log_g\left(\frac{\betalabel(\etallylabel_{i,j})}{F_{i,j}}\right)
\]
Stephane Glondu's avatar
Stephane Glondu committed
1070
1071
Here, the discrete logarithm can be easily computed because it is
bounded by $\ntallied$.
1072

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

1084
1085
1086
\section{Default group parameters}
\label{default-group}

1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
These parameters have been generated by the \verb=fips.sage= script
(available in Belenios sources), which is itself based on FIPS 186-4.

\[
\begin{array}{lcr}
p&=&20694785691422546\\
&&401013643657505008064922989295751104097100884787057374219242\\
&&717401922237254497684338129066633138078958404960054389636289\\
&&796393038773905722803605973749427671376777618898589872735865\\
&&049081167099310535867780980030790491654063777173764198678527\\
&&273474476341835600035698305193144284561701911000786737307333\\
&&564123971732897913240474578834468260652327974647951137672658\\
&&693582180046317922073668860052627186363386088796882120769432\\
&&366149491002923444346373222145884100586421050242120365433561\\
&&201320481118852408731077014151666200162313177169372189248078\\
&&507711827842317498073276598828825169183103125680162072880719\\
g&=&2402352677501852\\
&&209227687703532399932712287657378364916510075318787663274146\\
&&353219320285676155269678799694668298749389095083896573425601\\
&&900601068477164491735474137283104610458681314511781646755400\\
&&527402889846139864532661215055797097162016168270312886432456\\
&&663834863635782106154918419982534315189740658186868651151358\\
&&576410138882215396016043228843603930989333662772848406593138\\
&&406010231675095763777982665103606822406635076697764025346253\\
&&773085133173495194248967754052573659049492477631475991575198\\
&&775177711481490920456600205478127054728238140972518639858334\\
&&115700568353695553423781475582491896050296680037745308460627\\
q&=&78571733251071885\\
&&079927659812671450121821421258408794611510081919805623223441
\end{array}
\]

The additional output of the generation algorithm is:
1120
1121
\[
\begin{array}{lcr}
1122
1123
1124
1125
1126
\texttt{domain\_parameter\_seed}&=&478953892617249466\\
&&166106476098847626563138168027\\
&&716882488732447198349000396592\\
&&020632875172724552145560167746\\
\texttt{counter}&=&109
1127
1128
\end{array}
\]
1129
1130

\end{document}