Homomorphic secret sharing

From Wikipedia, the free encyclopedia

 This article lacks information on the notability of the subject matter.
Please help improve this article by providing context for a general audience, especially in the lead section. (November 2007)
This article does not cite any references or sources. (November 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.
Not to be confused with homeomorphism or secret sharing.

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.

Contents

[edit] A simplistic decentralized voting protocol

A Homomorphic, EVoting protocol based on the Shamir secret sharing technique. Homographic based protocols in general, has 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.

[edit] 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 fa with a security parameter t where: fa (0) = Ba.

Then, for each authority, Rk: k \in [n], 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.

[edit] 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:

  1. A ballot can not be backtracked to the ID so the privacy of the voters is preserved.
  2. A voter can not prove how he voted.
  3. 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.

[edit] 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.

[edit] See also