Homomorphic secret sharing

In cryptography, homomorphic secret sharing is a type of secret sharing algorithm in which the secret is encrypted via homomorphic encryption. A homomorphism is a transformation from one algebraic structure into another of the same type so that the structure is preserved. Importantly, this means that for every kind of manipulation of the original data, there is a corresponding manipulation of the transformed data.[1]

Technique

Homomorphic secret sharing is used to transmit a secret to several recipients as follows:

  1. Transform the "secret" using a homomorphism. This often puts the secret into a form which is easy to manipulate or store. In particular, there may be a natural way to 'split' the new form as required by step (2).
  2. Split the transformed secret into several parts, one for each recipient. The secret must be split in such a way that it can only be recovered when all or most of the parts are combined. (See secret sharing)
  3. Distribute the parts of the secret to each of the recipients.
  4. Combine each of the recipients' parts to recover the transformed secret, perhaps at a specified time.
  5. Reverse the homomorphism to recover the original secret.

Example: decentralized voting protocol

Suppose a community wants to perform an election, but they want to ensure that the vote-counters won't lie about the results. Using a kind of homomorphic secret sharing known as Shamir's secret sharing, each member of the community can put his vote into a form that can be split into pieces, then submit each piece to a different vote-counter. The pieces are designed so that the vote-counters can't predict how altering a piece of a vote will affect the whole vote; thus, vote-counters are discouraged from tampering with their pieces. When all votes have been received, the vote-counters combine all the pieces together, which allows them to reverse the alteration process and to recover the aggregate election results.

In detail, suppose we have an election with:

Assume the election has two outcomes, so each member of the community can vote either yes or no. We'll represent those votes numerically by +1 and -1, respectively.

  1. In advance, each authority generates a publicly available numerical key, xk.
  2. Each voter encodes his vote in a polynomial pn according to the following rules: The polynomial should have degree k-1, its constant term should be either +1 or -1 (corresponding to voting "yes" or voting "no"), and its other coefficients should be randomly generated.
  3. Each voter computes the value of his polynomial pn at each authority's public key xk.
    • This produces k points, one for each authority.
    • These k points are the "pieces" of the vote: If you know all of the points, you can figure out the polynomial pn (and hence you can figure out how the voter voted). However, if you know only some of the points, you can't figure out the polynomial. (This is because you need k points to determine a degree-k-1 polynomial. Two points determine a line, three points determine a parabola, etc.)
  4. The voter sends each authority the value that was produced using the authority's key.
  5. Each authority collects the values that he receives. Since each authority only gets one value from each voter, he can't discover any given voter's polynomial. Moreover, he can't predict how altering the submissions will affect the vote.
  6. Once the voters have submitted their votes, each authority k computes and announces the sum Ak of all the values he's received.
  7. There are k sums, Ak; when they are combined together, they determine a unique polynomial P(x)---specifically, the sum of all the voter polynomials: P(x) = p1(x) + p2(x) + … + pn(x).
    • The constant term of P(x) is in fact the sum of all the votes, because the constant term of P(x) is the sum of the constant terms of the individual pn.
    • Thus the constant term of P(x) provides the aggregate election result: if it's positive, more people voted for +1 than for -1; if it's negative, more people voted for -1 than for +1.
A table illustrating the voting protocol

Features

This protocol works as long as not all of the k authorities are corrupt — if they were, then they could collaborate to reconstruct P(x) for each voter and also subsequently alter the votes.

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 cannot be backtracked to the ID so the privacy of the voters is preserved.
  2. A voter cannot prove how they voted.
  3. It is impossible to verify a vote.

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

Vulnerabilities

References

  1. ↑ Schoenmakers, Berry (1999). Advances in Cryptology 1666: 148–164. CiteSeerX: 10.1.1.102.9375. Missing or empty |title= (help)

See also