An electronic voting system

Question

This semester I am taking the course Cryptography. I will have a presentation about the topic "Voting Scheme".

I am preparing myself by reading from the book “Cryptography : an Introduction” by N.Smart and I came across some points at which I am facing some difficulties.

The part that I am reading is this:

The voting system will assume that we have $m$ voters, and that there are $n$ centres which perform the tallying. The use of a multitude of tallying centres is to allow voter anonymity and stop a few centres colluding to fix the vote. We shall assume that voters are only given a choice of one of two candidates.

• System Setup

  Each of the $n$ tally centres has a public key encryption function $E_i$. We assume a finite abelian group $G$ is fixed, of prime order $q$, and two elements $g, h \in G$ are selected for which no party (including the tally centres) know the discrete logarithm \begin{equation}h=g^x.\end{equation} Each voter has a public key signature algorithm.

• Vote Casting

  Each of the $m$ voters picks a vote $v_j$ from the set $\{-1, 1\}$. The voter picks a random blinding value $a_j \in \mathbb{Z}/q\mathbb{Z}$ and publishes their vote \begin{equation}B_j=B_{a_j}(v_j),\end{equation} using the bit commitment scheme. This vote is public to all participating parties, both tally centres and other voters. Along with the vote $B_j$ the voter also publishes a non-interactive version of the protocol to show that the vote was chosen from the set $\{-1, 1\}$. The vote and its proof are then digitally signed using the signing algorithm of the voter.

• Vote Distribution

  We now need to distribute the votes cast around the tally centres so that the final tally can be computed. Each voter employs Shamir's secret sharing scheme as follows, to share the $a_j$ and $v_j$ around the tallying centres: Each voter picks two random polynomials modulo $q$ of degree $t<n$. \begin{equation}R_j(X)=v_j+r_{1,j}X+\dots +r_{t,j}X^t\end{equation} \begin{equation}S_j(X)=a_j+s_{1,j}X+\dots +s_{t,j}X^t\end{equation} The voter computes \begin{equation}(u_{i,j}, w_{i,j})=(R_j(i), S_j(i)) \text{ for } 1 \leq i \leq n.\end{equation}The voter encrypts the pair $(u_{i,j}, w_{i,j})$ using the $i$th tally centre's encryption algorithm $E_i$. This encrypts share is sent to the relevant tally centre. The voter then publishes its commitment to the polynomial $R_j(X)$ by publicly posting \begin{equation}B_{l, j}=B_{s_{l, j}}(r_{l,j}) \text{ for } 1 \leq l \leq t,\end{equation} again using the commitment scheme.

• Consistency Check

  Each centre $i$ needs to check that the values of \begin{equation}(u_{i,j}, w_{i,j})\end{equation} it has received from voter $j$ are consistent with the commitments made by the voter. This is done by verifying the following equation \begin{equation} \begin{split} B_j \prod_{l=1}^t {B_{l,j}}^{i^l}&=B_{a_j}(v_j)\prod_{l=1}^t B_{s_{l,j}}(r_{l,j})^{i_l}\\&=h^{v_j}g^{a_j}=\prod_{l=1}^t(h^{r_{l,j}}g^{s_{l,j}})^{i_l}\\&=h^{(v_j+\sum_{l=1}^t r_{l,j}i^l)}g^{(a_j+\sum_{l=1}^t s_{l,j}i^l)}\\&=h^{u_{i,j}}g^{w_{i,j}} \end{split} \end{equation}

• Tally Counting

  Each of the $n$ tally centres now computes and publicly posts its sum of the shares of the votes cast \begin{equation} T_i=\sum_{j=1}^mu_{i,j}\end{equation} plus it posts its sum of shares of the blinding factors \begin{equation}A_i=\sum_{j=1}^mw_{i,j}.\end{equation} Every other party, both other centres and voters can check that this has been done correctly by verifying that \begin{equation}\begin{split}\prod_{j=1}^m \left ( B_j \prod_{l=1}^t {B_{l,j}}^{j^l} \right )&=\prod_{j=1}^m h^{u_{i,j}}g^{w_{i,j}}\\&=h^{T_i}g^{A_i}.\end{split}\end{equation} Any party can compute the final tally by taking $t$ of the values $T_i$ and interpolating them to reveal the final tally, This is because $T_i$ is the evaluation at $i$ of a polynomial which shares out the sum of the votes. To see this we have \begin{equation}\begin{split}T_i&=\sum_{j=1}^mu_{i,j}\\&=\sum_{j=1}^mR_j(i)\\&=\left ( \sum_{j=1}^m v_j \right ) +\left ( \sum_{j=1}^m r_{1,j} \right )i+\dots +\left ( \sum_{j=1}^m r_{t,j} \right )i^t.\end{split}\end{equation} If the final tally is negative then the majority of the people voted $-1$, whilst if the final tally is positive then the majority of people voted $+1$.

I have the following questions:

1. At the System Setup why does each voter have a public key signature algorithm and not a private one?

2. What is the purpose of the Vote Casting? At this step does the voter choose the vote and publishes $B_j$ as commitment and also a proof that the vote was indeed chosen from the set $\{-1, 1\}$? What does it mean that the voter publishes these?

3. AT the part Vote Distribution at the sentence "The voter encrypts the pair $(u_{i,j}, w_{i,j})$ using the ith tally centre's encryption algorithm $E_i$." which $i$ does each voter take? Does the voter chooses it randomly?

4. Could you explain to me at the part Vote Distribution the sentence "The voter then publishes it commitments to the polynomial $R_j(X)$ by publicly posting \begin{equation}B_{l, j}=B_{s_{l, j}}(r_{l,j}) \text{ for } 1 \leq l \leq t,\end{equation} again using the commitment scheme." ?

5. Could you explain to me at the part Consistency Check why, to check that the values are consistent with the commitments made by the voter, do we have to verify the following equation? \begin{equation} \begin{split} B_j \prod_{l=1}^t {B_{l,j}}^{i^l}&=B_{a_j}(v_j)\prod_{l=1}^t B_{s_{l,j}}(r_{l,j})^{i_l}\\&=h^{v_j}g^{a_j}=\prod_{l=1}^t(h^{r_{l,j}}g^{s_{l,j}})^{i_l}\\&=h^{(v_j+\sum_{l=1}^t r_{l,j}i^l)}g^{(a_j+\sum_{l=1}^t s_{l,j}i^l)}\\&=h^{u_{i,j}}g^{w_{i,j}} \end{split} \end{equation}

6. At the part Tally Counting could you explain to me why we check if it has been done correctly we have to verify the following equation? \begin{equation}\begin{split}\prod_{j=1}^m \left ( B_j \prod_{l=1}^t {B_{l,j}}^{j^l} \right )&=\prod_{j=1}^m h^{u_{i,j}}g^{w_{i,j}}\\&=h^{T_i}g^{A_i}.\end{split}\end{equation}

Answer 1

Full disclosure: In 2007 I founded an association aiming at voting transparency. I'm proud that my efforts may have had some role, however small, in the fact that the number of French cities using electronic voting machines for political elections, then growing, has been declining since then.

The book defining the protocol of the question is made freely available by his author. The protocol is here. It is not intended as a state-of-the-art electronic voting protocol, only as an application of other techniques in the book. It makes heavy use of the Pedersen bit commitment scheme defined earlier in the book (which security is the origin of the requirement in System Setup that nobody must get to know the discrete logarithm $x$ of $h$ to base $g$ in the finite abelian group $G$).

The description of a practical implementation of the scheme including networking and trusted hardware issues is beyond the scope of the book, is thus not given, and hence can not be criticized. It is made no explicit attempt to address the requirement of preventing a voter from proving how s/he voted (by leaking the supposedly secret $a_j$), perhaps because s/he's being rewarded or threatened to do so; which is an aim of good voting systems, achieved to a large degree by most actual ones (electronic or not) when voting takes place in a physical public polling station. And, most importantly, the issue of how human voters are supposed to be confident in the system despite it relying on mathematics most have not studied, and physical systems which design and fabrication details are in practice secret, is not addressed.

Trying to answer some of the questions:

1. The voter makes the signature according to a public-key signature scheme (such as RSA, ElGamal, Schnorr..), thus using the private component of her or his public/private key pair. A public-key signature scheme allows verification of origin and integrity of a piece of data (here, the casting of the vote) without requiring knowledge of anything that would allow to forge a signature. [Note: that's a cardinal advantage compared to other schemes aiming at ensuring message origin and integrity that use symmetrical algorithms (such as CMAC, HMAC), which require signer and verifier to share a secret key, with the concern that the verifier could use that secret to make a forgery that other verifiers would not be able to detect as such (one known working workaround is to embed the symmetrical secret key used by verifiers into devices only usable for verification; but then one has to trust these devices, and thus in practice their maker; the scheme proposed does not do this)].
   Note following comment: The sentence " Each voter has a public key signature algorithm " implies that each voter has a public/private key pair, and allows different voters to use a different scheme. The verification procedures (methods and public keys) must be public, so the union of these signature schemes can be considered a signature scheme; much like the various RSA/DSA/ECDSA signature schemes and parameterizations in FIPS 186-4 can be considered the FIPS 186-4 signature scheme.
2. The purpose of Vote Casting (in any voting protocol) is to:
   • Allow the voter to make a choice (here of $v_j\in\{-1,1\}\;$) in a way that will allow the system to count them (here the sign of the sum will be the outcome of the election).
   • Prevent the voter from changing her or his mind or otherwise messing-up with the system; here, this is done by publishing a signature of a commitment of the vote, so that anyone interested can later know that the voter has cast a vote, and what this voter's commitment was (the commitment is verifiable publicly, but that leaves $v_j$ confidential for someone with no information about $a_j$). The publication mean shall leave no ambiguity, in particular should prevent multiple casting (perhaps with different $v_j$). An implementation in a physical public polling station could use an ink jet printer to write a QR code on the electoral register along the name and date of birth of the voter. The example protocol does not address how that could be done using an online mean, but a good old fashioned Usenet group using nntp might be some approximation (at least the threats facing the publishing system have similarities to that nntp faces).
3. In this example system, the voter makes the stated computation of $(u_{i,j}, w_{i,j})$ and sends $\operatorname{Enc}_i(u_{i,j},w_{i,j})$ to voting center $i$ for every voting center.
4. The voter commits to the polynomial $R(X)$ by publishing (using publication means as in Vote Casting) a commitment $B_{l,j}$ to each coefficient $R_j$ of that polynomial, except for the lower-order coefficient $v_j$ (which the voter has already committed to by publishing the commitment $B_j$ during Vote Casting).

Answer 2

I thought that the structure of the presentation would be as followed.

One of the basic tools that are used by the most cryptographic protocols of electronic voting are the Zero-Knowledge proofs. These proofs use protocols at which the Prover confirms to a Verifier the correctness of a statement, in such a way that the Verifier cannot find anything out besides the fact that the statement is correct.

The basic properties of a zero-knowledge protocol are:

• Completeness: Given that the prover is honest, i.e. the statement is indeed true, then the verifier will accept the proof. That means that the verifier will accept the proof with probability $1$.
• Soundness: If the prover is not honest, that means that the statement is false, then the verifier should not accept the proof, only with a very small probability.

A zero-knowledge proof can be separated into two categories: interactive and non-interactive. The electronic voting systems use non-interactive zero-knowledge proofs, i.e. the interaction between the prover and the verifier is not needed.

A non-interactive zero-knowledge protocol that the electronic voting systems use is the following:

Let $G$ a finite abelian group of prime order $q$ and $g$ a generator, $G=<g>$. Let $h \in <g>$, where the discrete logarithm of $h$ with basis $g$ is unknown to each member of the system.

Given $g,h$ we define the commitment scheme $B_a(x)$ with $B_a(x)=h^xg^a$ for the commitment to an integer $x$ modulo $q$, where $a$ is a random integer modulo $q$.

We suppose that $x \in \{-1,1\}$.

• The Verifier publishes the commitment $B_a(x)$, chooses random numbers $d$, $r$ and $w$ modulo $q$ and publishes $\alpha_1$ and $\alpha_2$ where $$\alpha_1=\left\{\begin{matrix} g^r(B_a(x)h)^{-d} & \text{ if } x=1 \\ g^w & \text{ if } x=-1 \end{matrix}\right. \ \ , \ \ \alpha_2=\left\{\begin{matrix} g^w & \text{ if } x=1 \\ g^r(B_a(x)h^{-1})^{-d} & \text{ if } x=-1 \end{matrix}\right.$$
• The challenge is $c=H(\alpha_1 || \alpha_2 || B_a(x))$, where $H$ is a hash function.
• The Verifier responds by setting $$d'=c-d \ \ , \ \ r'=w+a'$$ and returns the values $$(d_1, d_2, r_1, r_2)=\left\{\begin{matrix} (d, d', r, r') & \text{ if } x=1 \\ (d', d, r', r) & \text{ if } x=-1 \end{matrix}\right.$$
• We can verify that the following equations hold $$c=d_1+d_2 \ \ , \ \ g^{r_1}=\alpha_1 (B_a(x)h)^{d_1} \ \ , \ \ g^{r_2}=\alpha_2 (B_a(x)h^{-1})^{d_2}$$

An other basic tool is the secret sharing, and especially the scheme of Shamir.

We suppose that we have $n$ members and we want to share a secret so that $t$, or less, members cannot reveal the secret. Let $s \in \mathbb{F}_p$ the secret, where $p$ a prime with $p>n+1$. - We choose values $x_i$, for $i=1, \dots , n$, a values for each member, that is known to everyone. - We choose $t$ secret elements $a_1, \dots , a_t$ and form the polynomial $$f(x)=s+\sum_{j=1}^{t}a_j x^j$$ - We calculate the share $y_i=f(x_i)$ for $1 \leq i \leq n$ and give it to the member $i$. - If $t+1$ members come together they can reveal the initial polynomial with Lagrange interpolation, and so the secret $s$.

We suppose that we have $m$ voters and $n$ tallying centers. We also suppose that the voters can choose one of two candidates, which are codified with the values $1$ and $-1$.

Each electronic voting consists of $5$ stages.

1. System Setup

Each of the $n$ tally centers has a public key encryption function $E_i$ and each voter has a public key signature algorithm.

2. Vote Casting

Each of the $m$ voters picks a vote $v_j$ from the set $\{-1, 1\}$ and a random blinding value $a_j \in \mathbb{Z}/q\mathbb{Z}$. Then he/she publishes the vote \begin{equation}B_j=B_{a_j}(v_j),\end{equation}with the above commitment scheme. This vote is public to all members of the system, both tally centers and other voters. Along with the vote $B_j$ the voter also publishes a proof to show that the vote was chosen from the set $\{-1, 1\}$ using the above zero-knowledge protocol. Finally, the voter uses its signature algorithm to give a digital signature to the vote and the to the proof.

3.Vote Distribution

The votes have to be distributed to the tally centers so that the final result can be computed. Each voter uses Shamir's secret sharing scheme to share the $a_j$ and $v_j$ to the tallying centers. He/She picks two random polynomials modulo $q$ of degree $t<n$. \begin{equation}R_j(X)=v_j+r_{1,j}X+\dots +r_{t,j}X^t\end{equation} \begin{equation}S_j(X)=a_j+s_{1,j}X+\dots +s_{t,j}X^t\end{equation} Then he/she computes the pair \begin{equation}(u_{i,j}, w_{i,j})=(R_j(i), S_j(i)) \text{ for } 1 \leq i \leq n.\end{equation} encrypts it using the $i$th tally center's encryption algorithm $E_i$ and sends $E_i(u_{i,j}, w_{i,j})$ to the $i$th tally center for each $i$, $1 \leq i \leq n$. The voter commits to the polynomial $R_j(X)$ by publishing a commitment $B_{l,j}$, \begin{equation}B_{l, j}=B_{s_{l, j}}(r_{l,j}) \text{ for } 1 \leq l \leq t,\end{equation} for each coefficient $r_{l,j}$ of the polynomial (except for the constant term $v_j$ which the voter has already committed to).

4. Consistency Check

Each center $i$ has to check if the values of \begin{equation}(u_{i,j}, w_{i,j})\end{equation} it has received from voter $j$ are consistent with the commitments made by the voter by verifying the equation \begin{equation} \begin{split} B_j \prod_{l=1}^t {B_{l,j}}^{i^l}&=B_{a_j}(v_j)\prod_{l=1}^t B_{s_{l,j}}(r_{l,j})^{i_l}\\&=h^{v_j}g^{a_j}=\prod_{l=1}^t(h^{r_{l,j}}g^{s_{l,j}})^{i_l}\\&=h^{(v_j+\sum_{l=1}^t r_{l,j}i^l)}g^{(a_j+\sum_{l=1}^t s_{l,j}i^l)}\\&=h^{u_{i,j}}g^{w_{i,j}} \end{split} \end{equation}

5. Tally Counting

Each of the $n$ tally centers computes and publishes its sum of the shares of the votes cast \begin{equation} T_i=\sum_{j=1}^mu_{i,j}\end{equation} and its sum of shares of the blinding factors \begin{equation}A_i=\sum_{j=1}^mw_{i,j}.\end{equation} The other centers and the voters can check that these are correct by verifying that \begin{equation}\begin{split}\prod_{j=1}^m \left ( B_j \prod_{l=1}^t {B_{l,j}}^{j^l} \right )&=\prod_{j=1}^m h^{u_{i,j}}g^{w_{i,j}}\\&=h^{T_i}g^{A_i}.\end{split}\end{equation} Each member of the system can compute the final result by taking $t$ of the values $T_i$ and using Lagrange interpolation. In this way everyone can calculate the coefficients of the polynomial $T_i$. We have \begin{equation}\begin{split}T_i&=\sum_{j=1}^mu_{i,j}\\&=\sum_{j=1}^mR_j(i)\\&=\left ( \sum_{j=1}^m v_j \right ) +\left ( \sum_{j=1}^m r_{1,j} \right )i+\dots +\left ( \sum_{j=1}^m r_{t,j} \right )i^t.\end{split}\end{equation} So, we know the term $\sum_{j=1}^{m}v_j$. If the sum is negative we conclude that the majority of the voters voted $-1$, whilst if the sum is positive we conclude that the majority of the voters voted $+1$.