1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multirow}
\begin{document}
\newcommand{\todo}[1]{\marginpar{\footnotesize\emph{#1}}}
\newcommand{\ZZ}{\mathbb{Z}}
\section{Parameters of the Encryption Scheme}
\begin{itemize}
\item There are $n$ authorities, $A_1 \dots A_n$.
\item Let $k$ be the minimum number of authorities required to jointly decrypt a cyphertext.
\item \todo {How do we show that's feasable? Prime number theorem?}
Let $p$ and $q$ be large primes, where $p=2q+1$ ($q$ is commonly called a Sophie Germain prime, $p$ a safe prime). A pair of such numbers can be found by generating a random prime $q$ and checking if $2q+1$ is also prime.
\item \todo{Write down proof? Usually just stated as a fact in literature}
Let $g$ be a generator of $G_q$, where $G_q$ is the unique subgroup of $\ZZ_p^*$ of order $q$. The \emph{Decisional Diffie--Hellman assumption} is believed to hold for $G_q$, as $G_q$ is the subgroup of quadratic residues in $\ZZ_q^*$. \cite{ddh}
\item The generator $g$ can be computed as follows \cite[Section 4.6]{hac}:
\begin{enumerate}
\item Repeatedly choose an $\alpha \in \ZZ_p^*$ at random, until it satisfies $\alpha^q \ne 1$ and $\alpha^2 \ne 1$,
that is, the order of $\alpha$ is neither $q$, $2$ nor $1$. Then $\alpha$ is a generator of $\ZZ_p^*$.
\emph{Proof:} By Lagrange's Theorem, $\ZZ_p^*$ has exactly two proper non-trivial subgroups of order $p$ and $2$, respectively.
As $\alpha$ is neither of order $p$, $2$ nor $1$, it can only be a generator of $\ZZ_p^*$.
\item Compute $g=\alpha^k$, where $k=(p-1)/q$. Then $g$ is a generator of $G_q$.
\emph{Proof:} Let $ord(\cdot)$ be the order a group element. As $k$ divides $ord(\alpha)$, it follows from a standard result of group theory \cite[Proposition 4.5]{algebra} that $ord(\alpha^k) = ord(\alpha)/k = q$.
\end{enumerate}
\end{itemize}
\section{Key Distribution}
\begin{itemize}
\item Let $x := \sum_{i=1}^{n} x_i$ be the private key. Note that no single authority should be able to know $x$.
\item Every authority $A_i$ chooses a random $x_i \in \ZZ_q$, and publishes $h_i := g^{x_i}$.
\item Let $h := g^{x}$ is the public key, which can be computed as $h = \prod_{i=1}^{n} h_i$.
\item Every authority $A_i$ generates the random polynomial
\begin{equation}
f_i(z) = \sum_{l=0}^{k-1} f_{i,l}^{l},
\end{equation}
with $f_i(z) \in \ZZ_q[z]$, where $f_{i,0} = 0$ and $f_{i,l} \in \ZZ_q$ is chosen randomly for $l \ne 0$.
It follows by definition that $f_i(0) = x_i$.
\item Every authority $A_i$ publishes $(F_{i,l})_{l=1,\dots,k-1}$, where
\begin{equation}
F_{i,l} = g^{f_{i,l}}
\end{equation}
is the commitment of authority $A_j$ to the value of $f_{i,l}$.
\item Now every authority $A_i$ secretly sends
\begin{equation} \label{eq:sendshares}
s_{i,j} = f_i(j)
\end{equation}
to each authority $A_j$.
\item \todo{Do we need to prove the consistency? Doesn't it just follow from the fact that it is the same computation, only in the exponent of $g$?}
$A_i$ verifies the share received from $A_j$ is consistent with the previously published values by
verifying that
\begin{equation}
g^{s_{i,j}} = \prod_{l=0}^{k-1} F_{jl}^{(i^l)}.
\end{equation}
This equation follows directly from raising $g$ to both
sides of equation \eqref{eq:sendshares}.
\todo{I think it should be illustrated why this works / what happens with the polynomials}
\item $A_i$ computes his share of $x$ as $s_i = \sum_{j=1}^n s_{ji}$.
\item Each authority $A_i$ publishes
\begin{equation}
\sigma_i := g^{s_i}
\end{equation}
as a commitment to the received share.
\end{itemize}
\section{Cooperative Decryption}
\begin{itemize}
\item The full private key can be restored by a set at least $k$ cooperating authorities $\Lambda \subseteq \{A_1,\dots,A_n\}$, $k \le |\Lambda|$, for example by using Lagrange interpolation:
\begin{equation} \label{eq:pkey}
x = \sum_{A_j \in \Lambda} s_j \lambda_{j,\Lambda}
\end{equation}
where the Lagrange coefficients are
\begin{equation}
\lambda_{j,\Lambda} := \prod_{\substack{
A_l \in \Lambda \\ l \neq j} } \frac{l}{l-k}.
\end{equation}
Note that this formula is only used for the derivation of the cooperative encryption process, and authorities never actually should cooperate to restore the public key $x$.
\item To decrypt an ElGamal encryption $(c_1, c_2) = (g^y, h^y m)$ of the message $m \in G_q$, each authority $A_j$ broadcasts $w_j = c_1^{s_j}$.
\item To prove that an authority has computed $w_j$ correctly, it has to prove in zero-knowledge that
\[
s_j = \log_g \sigma_j = \log_{c_1} w_j,
\]
in words that $w_j$ has actually been computed with the authority's share.
\item By raising $c_1$ to both sides of equation \eqref{eq:pkey} and then dividing $c_2$ by both sides, we get
\[
m = c_2 / \prod_{A_j \in \Lambda} w_j^{\lambda_{j,\Lambda}}.
\]
\end{itemize}
\section{Zero-knowledge-proof for discrete logarithms}
\begin{itemize}
\item The Prover wants to prove
\[
s_j = \log_g \sigma_j = \log_{c_1} w_j
\]
without revealing the value of $s_j$.
\item The Prover sends $(g^\beta, c_1^\beta)$, with $\beta \in_R Z_q$
\item The Verifier sends $c \in_R Z_q$
\item The Prover sends $r = \beta + s_i c$
\item The Verifier checks the two equalities
\[
g^r = g^\beta \sigma^c
\]
\[
c_1^r = c_1^\beta w_i^c
\]
\end{itemize}
This proof utilizes the fact that it is hard to compute $g^{ab}$ from $g$ and $a$ without having $b$.
\section{Casting a vote}
\begin{itemize}
\item A vote has the form $(g^y, h^yG^b)$, where $G$ is a generator of $G_q$ (one could just use $G=q$), $b \in \{-1,1\}$ denotes the value of the vote, and $y \in_R Z_q$.
\end{itemize}
\section{Verifying a vote}
The details on how this protocol can be constructed from the discrete log protocol can be found in \cite{Cramer94}.
\newcommand{\?}{\stackrel{?}{=}}
\begin{table}[!h]
\begin{tabular}{ c|ccp{\columnwidth} }
\multicolumn{2}{c}{ Voter } & &
Verifier \\ \\
$v=1$ & $v=-1$ & & \\ \cline{1-2}
$\alpha,w,r_1,d_1 \in_R Z_q$ & $\alpha,w,r_2,d_2 \in_R Z_q$ \\ \\
$x \leftarrow g^\alpha$ & $x \leftarrow g^\alpha$ \\
$y \leftarrow h^\alpha G$ & $y \leftarrow h^\alpha / G$ \\
$a_1 \leftarrow g^{r_1}x^{d_1}$ & $y \leftarrow g^w$ \\
$b_1 \leftarrow h^{r_1}(yG)^{d_1}$ & $b_1 \leftarrow g^w$ \\
$a_2 \leftarrow g^w$ & $y \leftarrow g^{r_2}x^{d_2}$ \\
$b_2 \leftarrow h^w$ & $b_2 \leftarrow h^{r_2}(y/G)^{d_2}$ &
$\xrightarrow{x,y,a_1,b_1,a_2,b_2}$ \\ \\
$d_2 \leftarrow c - d_1$ & $d_1 \leftarrow c - d_2$ &
$\xleftarrow{c}$ & $c \in_R Z_q$ \\ \\
$r_2 \leftarrow w - \alpha d_2$ & $r_1 \leftarrow w - \alpha d_1$ &
$\xrightarrow{d_1,d_2,r_1,r_2}$ & $c \; \? d_1 + d_2$ \\
\multicolumn{3}{c}{} & $a_1 \? g^{r1} x^{d_1}$ \\
\multicolumn{3}{c}{} & $b_1 \? h^{r1} (yG)^{d_1}$ \\
\multicolumn{3}{c}{} & $a_2 \? g^{r2} x^{d_2}$ \\
\multicolumn{3}{c}{} & $b_2 \? h^{r2} (y/G)^{d_2}$ \\
\end{tabular}
\end{table}
\clearpage
\section{Counting votes}
\begin{itemize}
\item Let $(x_i, y_i)$ be the vote casted by Voter $V_i$
\item $(X,Y) = (\prod_{i=1}^{l}x_i,\prod_{i=1}^{l} y_i)$ is computed by all authorities.
\item $(X,Y)$ is decrypted cooperatively, obtaining $G^T$,
where $T$ is the outcome of the election.
\item Let $l$ be the number of votes. As $T \in \{-t,...,t\}$ holds,
the number of votes can be found by brute-force.
\end{itemize}
\section{Notes on Notation}
\begin{table}[!h]
\begin{tabular}{ | c | c | c | c | }
\hline
\cite{Cramer97} & \cite{Pedersen} & this document & source code \\ \hline
$s$ & $x$ & $x$ & BigInteger x \\
-- & $x_i$ & $x_i$ & BigInteger\lbrack\rbrack \, xParts; xParts\lbrack i\rbrack \\
\hline
\end{tabular}
\end{table}
\appendix
\section{ElGamal}
To encrypt a cyphertext $m \in G_q$, the sender chooses a random $y \in_R Z_q$ and sends the pair $(c_1, c_2) = (g^y, m h^y)$.
The decrypt the cyphertext, the receiver recovers the plaintext as $c_2 / c_1^x = (m h^y) / g^{yx} = (m h^y) / h^y = m$.
\clearpage
\bibliographystyle{alpha}
\bibliography{voting}
\end{document}
|
