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:
At the System Setup why does each voter have a public key signature algorithm and not a private one?
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?
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?
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." ?
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}
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}