User:Taeshadow/Page for drafts/Homomorphic electronic voting
![]() | The topic of this article may not meet Wikipedia's general notability guideline. (November 2007) |
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
editRather 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
editWe 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: , , and . Suppose candidate receives 40\% of the votes and candidates and each receive 30\%. Candidate 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
editA 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
editA voter (m – group of voters) chooses a candidate (the secret) using a ballot . Then, the voter randomly chooses a polynomial fa with a security parameter t where: fa (0) = Ba.
Then, for each authority, Rk: , the voter computes the share fa(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) = f1(k)+ f2(k)+ .. + fm(k) = (f1+ f2+ .. + fm)(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)= f1(0)+ f2(0)+ .. + fm(0).
Notice that fi(0) for i=1…m is the value of the ballot submitted by the ith voter, and F(0) is the sum of the votes and therefore the result of the tally.
Features
editThe 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
edit- 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.
See also
edit- End-to-end auditable voting systems
- Electronic voting
- Certification of voting machines
- Techniques of potential election fraud through physical tampering with voting machines
- Preventing Election fraud: Testing and certification of electronic voting
- Vote counting system
- E-democracy
- Secure multi-party computation