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:

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).
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)
Distribute the parts of the secret to each of the recipients.
Combine each of the recipients' parts to recover the transformed secret, perhaps at a specified time.
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:

Two possible outcomes, either yes or no. We'll represent those outcomes numerically by +1 and -1, respectively.
A number of authorities, k, who will count the votes.
A number of voters, n, who will submit votes.

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.

In advance, each authority generates a publicly available numerical key, x_k.
Each voter encodes his vote in a polynomial p_n 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.
Each voter computes the value of his polynomial p_n at each authority's public key x_k.
- 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 p_n (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.)
The voter sends each authority the value that was produced using the authority's key.
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.
Once the voters have submitted their votes, each authority k computes and announces the sum A_k of all the values he's received.
There are k sums, A_k; when they are combined together, they determine a unique polynomial P(x)---specifically, the sum of all the voter polynomials: P(x) = p₁(x) + p₂(x) + … + p_n(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 p_n.
- 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:

A ballot cannot be backtracked to the ID so the privacy of the voters is preserved.
A voter cannot prove how they voted.
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

The voter cannot be certain that their vote has been recorded correctly.
The authorities cannot be sure the votes were legal and equal, for 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 their favor.

References

↑ Schoenmakers, Berry (1999). "A simple publicly verifiable secret sharing scheme and its application to electronic voting". Advances in Cryptology. 1666: 148–164. CiteSeerX 10.1.1.102.9375.