Homomorphic secret sharing - AbsoluteAstronomy.com

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, homomorphic secret sharing is a type of secret sharing

Secret sharing

Secret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...

algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

in which the secret is encrypted via homomorphic encryption

Homomorphic encryption

Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....

. A homomorphism

Homomorphism

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...

is a transformation from one type of algebraic structure

Algebraic structure

In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...

into another 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.

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
Secret sharing
Secret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...

)
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

Shamir's secret sharing

Shamir's Secret Sharing

Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret....

is a kind of homomorphic secret sharing in which a secret, represented by a number, is transformed into a polynomial. As a specific application, suppose a community is worried about corrupt authorities tampering with their votes. Instead of sending their votes to a single authority who might be corrupt, they decide to use secret sharing to distribute encrypted fragments of their votes to several authorities, hoping to decentralize the vote-counting process. In fact, Shamir's secret sharing has several advantages, which are discussed in more detail below. The protocol proceeds as follows:

Suppose that we have a simple ballot where a voter can either choose to vote yes (represented by the number +1) or no (represented by the number -1), and suppose there are

authorities who will be receiving the parts of votes.

Each voter generates a random polynomial of degree . . The constant term will equal the option they voted for, i.e. will be either +1 or -1.
Each authority has a publicly-known ID number . Next, the voter calculates for each of the authorities. The are the pieces of the secret, which are distributed to the corresponding recipients along with their voter ID.
- The secret is secure because it takes points to recover a polynomial of degree . (Two points determine a line, three points determine a parabola, and so on)
- Since it is mathematically impossible to determine the voter's choice with only one piece of the secret, the voter ID doesn't have to be confidential.
- Additionally, this system resists tampering because no authority would be able to predict how altering their piece would affect the vote.
After voting has been completed, each authority adds up the pieces he has received from all of the voters, and then sends this sum to the rest of the authorities.
- Recall that the secret has been transformed via . Because was a homomorphism, adding up the polynomials precisely corresponds to adding up the votes, that is .
When the sums from the authorities are all known, the sum-polynomial can be calculated. will be the sum of all the votes received. (Hence if is positive, more votes were received for yes than no, and if is negative, more votes were received for no than yes.)

Features

This protocol works as long as not all of the

authorities are corrupt—if they were, then they could collaborate to reconstruct

for each voter and then alter the votes.

The protocol

Cryptographic protocol

A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...

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

Cryptographic protocol

A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...

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, 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 his favor.

Technique

Example: decentralized voting protocol

Features

Vulnerabilities

See also