User:Taeshadow/Page for drafts/Homomorphic electronic voting

In cryptography, homomorphic secret sharing is a form of secret sharing algorithm involving homomorphism.

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). The word homomorphism comes from the Greek language: homo meaning "same" and morphos meaning "shape".

In cryptography, secret sharing refers to any method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their own.

Bulletin Board

Rather than allow parties to communicate over private channels, we employ a \emph{bulletin board}\index{bulletin board} model. This model, introduced by Benaloh \cite{Benaloh87}, ensures that all communication is performed in the open.

A \emph{bulletin board} is a public memory shared by multiple \emph{users}. The bulletin board is divided into \emph{areas}\index{area (bulletin board)}, one for each user. Every user has read access to every area on the bulletin board, and append access to its own. We define the \emph{transcript}\index{transcript

 (bulletin board)} of the bulletin board to be the entire contents

of the bulletin board.

Observe that no user has delete access to any area of the bulletin board.

We make one final assumption about the communication model. This is that every user who posts to the bulletin board is \emph{authenticated}. That is, we never have to be concerned that a message is posted in a user's area that did not come from that user.

Ballot encoding

We begin by discussing various ways of performing elections. Namely, we discuss how ballots can be cast, and how winners can be chosen.

There are several voting methods. We will concern ourselves with the most well-known. In the \emph{plurality}\index{plurality} selection method, the winner is selected to be the candidate with the most votes. It is important to observe that the winner need not have the \emph{majority} of votes, only the most. For example, suppose there are three candidates: $A$ , $B$ , and $C$ . Suppose candidate $A$ receives 40\% of the votes and candidates $B$ and $C$ each receive 30\%. Candidate $A$ is selected as the winner, because it received the most votes, even though it did not receive the majority.

In order to use homomorphic encryption for ballot casting, it is necessary to find some method of numerically encoding ballots. Depending on what sorts of ballots are allowed, there are numerous ways of encoding them.

    At this stage, the authorities
     will participate in a protocol that will compute the public key for
      the election using a distributed key generation protocol.

        An authority $i$ logs in, reads $(g_j, n_j)$ (the public keys) for
          all authorities $j \in A_1$, and the authority threshold $t$. The
            authority creates its polynomial $f_i(\mathrm{X}) = s_{i0} +
              a_{i1}\mathrm{X} + \cdots + a_{it}\mathrm{X}^t$. It publishes value
                $A_{ik} = g^{a_ik}$, for each $k = 0, \ldots, t$, as well as $y_{ij}
                  = g^{s_ij}$ and $Y_{ij} = g_j^{s_{ij}}u_{ij}^{n_i}$, followed by a
                    proof $(e_ij, w_{ij}, z_{ij})$, for each $j \in A_1$. This serves
                      as a form of encryption of authority $j$'s index evaluated in
                        authority $i$'s polynomial. Let $A_2 \subseteq A_1$ be the set of
                          authorities that have completed this step. If $|A_2| < t'$, the
                            server terminates the procedure.

A simplistic decentralized voting protocol

A Homomorphic, EVoting protocol based on the Shamir secret sharing technique. Homographic based protocols in general, have limited scalability, therefore the poll is limited to several options.

For the purpose of the example we assume the voter has only two options {-1, 1}, which stands for two different candidates.

The protocol

A voter $a\in [m]$ (m – group of voters) chooses a candidate (the secret) using a ballot $Ba\in \{-1,1\}$ . Then, the voter randomly chooses a polynomial f_a with a security parameter t where: f_a (0) = B_a.

Then, for each authority, R_k: $k\in [n]$ , the voter computes the share f_a(k) (notice K is predetermined for each authority).

The calculated share is sent to its respective authority along with the voter ID. Notice the voter ID is sent with a share of the ballot and therefore can be sent with no need to be hidden.

After all ballots have been submitted by the voters, each authority calculates the sum of the shares of all the ballots that is received and propagates the result to all the other authorities. In other words, each authority calculates a point on the sum-polynomial:

F(k) = f₁(k)+ f₂(k)+ .. + f_m(k) = (f₁+ f₂+ .. + f_m)(k) .

Then the authority sends the result to all other authorities. Assuming t+1 authorities forward the correct values, the interpolation of the sum-polynomial at x=0

F(0)= f₁(0)+ f₂(0)+ .. + f_m(0).

Notice that f_i(0) for i=1…m is the value of the ballot submitted by the i^th voter, and F(0) is the sum of the votes and therefore the result of the tally.

Features

The protocol works over the assumption that there are less than t+1 malicious authorities in the system, the reason is that in a case where t+1 corrupted authorities collaborate, it is possible to reconstruct the polynomial and reveal the vote of each voter.

The protocol requires t+1 authorities to be completed, therefore in case there are N>t+1 authorities, N-t-1 authorities can be corrupted, which gives the protocol a certain degree of robustness.

The protocol manages the IDs of the voters (the IDs were submitted with the ballots) and therefore can verify that only legitimate voters have voted.

Under the assumptions on t:

A ballot can not be backtracked to the ID so the privacy of the voters is preserved.
A voter can not prove how he voted.
It is impossible to verify a vote.

The protocol implicitly prevents corruption of ballots. This is because the authorities has no incentive to change the ballot since each authority has only a share of the ballot and has no knowledge how changing the ballot will affect the outcome.

Vulnerabilities

The voter can not be certain that his vote had been recorded correctly.
The authorities can not be sure the votes were legal and equal, in example the voter can choose a value which is not a valid option ( i.e. not in {-1, 1} ) such as -20, 50 which will tilt the results in his favor.