In this note, we take a look at a recent survey paper on Threshold Signature Schemes (TSSs) in the context of ECDSA (a signature scheme we discussed earlier in this note) and talk about a particular way of sharing a secret value among different parties that relies on Lagrange polynomials called Shamir Secret Sharing (we will refer to it as SSS).
Since we discussed polynomial representation/decomposition based on Lagrange as part of our series on polynomial commitments, SSS is easy to discuss as it uses much of the same foundation. For a more general discussion, we highly recommend the original survey. Much of our discussion will be simplified in comparison.
A -secret sharing scheme splits a (secret) value/mathematical object into different shares to be distributed to multiple parties, such that distinct shares are necessary and sufficient to reconstruct .
This would mean that there is a certain amount of redundency of information in each of the shares (at least as much as ) such that accumulation of of them is enough to learn all the necessary information to determine (which we refer to as as if there was no redundency). Further, this redundency of information must be distributed to different shares such that any of them would be sufficient for reconstructing .
One can imagine that mathematical objects with infinite number of (easily accessible) representations such as polynomials would be useful for building redundencies.
In Shamir Secret Sharing, the mathematical object whose information is to be shared among multiple parties is a univariate polynomial . If the secret to be shared is a numeric value instead of the polynomial itself (which is usually the case), we can simply encode the secret value as part of this polynomial, e.g. as the evaluation of at the origin, . There are infinite number of polynomials with however, and therefore, the choice of will involve injecting some randomness.
The only other concern is the maximal degree of the polynomial to be considered. As we can imagine, for a -secret sharing scheme (which requires shares to reveal the secret), the sensible choice for the maximal degree is , as knowing the evaluations of such a polynomial at distinct points is enough to reconstruct the entire polynomial exactly. Since the secret is baked into the polynomial at the origin, knowing the polynomial is enough to discover the secret value. It is very intuitive.
Now, let us describe it more carefully. Assume that we wish to share the secret value in some way to participants such that any of them are enough to recover .
There are various ways one can randomly choose a polynomial of maximal degree such that it passes through at the origin. The simplest way would be to randomly sample the coefficient vector from a field.
As we have discussed before, this same polynomial can be represented instead through its evaluation set as long as and it contains at least values evaluated at unique points within it (redundant if more elements are in it than ). In fact, any element subset of is sufficient to reconstruct through Lagrange interpolation:
A distributor simply gives out a single element of the evaluation set to each party as a share. It is clear that shares would allow discovery of and therefore its evaluation of it at the origin . We can refer to this procedure as ,
This concludes the description of the secret sharing scheme.
It is important for SSS secret reconstruction to be additively and multiplicatively homomorphic for it to be used for signature schemes such as ECDSA (see [1]), as the signature algorithm of ECDSA can be thought of as a circuit with addition and multiplication gates of a certain depth. Being able to execute such circuits through sole computations on individual shares without directly computing/sharing intermediary results of ECDSA would make threshold signatures viable.
Additive homomorphism is not difficult to satisfy for many secret sharing schemes. However, multiplicative homomorphism is harder to accomplish and in the case of Shamir requires more shares to be available than , particularly in the naive approach. With further communication between parties, this can be reduced back to as we will see. Let us show how we can prove these properties in the case of Shamir.
Additive homomorphism:
Suppose there are two secrets and that are shared across parties as before with shares needed for reconstructing each. For the th party, the shares are and , which means that we are assuming the evaluation set is the same for both polynomials that secrets are embedded in.
Now, we wish to show that if , it is possible to reconstruct this new secret from any subset of the original shares. This is very straightforward for individual parties. They can simply compute a share for the new secret as from their existing shares for secrets and . Using the linearity of Lagrange interpolation at the same set of evaluation points ,
Adding two polynomials and that pass through and at the origin simply results in a polynomial (which we can obtain through shares of ) that passes through at the origin.
Multiplicative homomorphism:
Multiplicative homomorphism is a bit more challenging. We have the same setup as before but this time the new secret is computed as . Consider a polynomial where and are defined as before. It is clear that , which means that this polynomial passes through at the origin.
However, the maximal degree of the polynomial is , as it is a multiplication of two polynomials with maximal degree . This would mean that it would require distinct evaluations of this polynomial for it to be reconstructed through Lagrange interpolation.
As the evaluation of at a particular point is simply , and any distinct evaluations of uniquely identifies it among all polynomials with maximal degree , knowledge of at distinct evaluation points is enough to recover through Lagrange interpolation. Therefore, each individual party can create from and that they already have, so that they can use it to collaborate with other parties to reconstruct directly.
If parties have shares for secrets and , parties can come together to obtain secret using only their shares for and . This would of course require that at the beginning. Further, it is not ideal that required number of participants are now almost double the original for reconstructing secrets.
Clearly, using directly is not viable if we need to keep the required number of participants at . In this section, we present a method where a new polynomial of maximal degree is communicated and shared between parties s.t. it passes through the multiplicative secret at the origin.
This is accomplised by each party making computations on the shares they already have for and and communicating to other parties some of the results of these computations without revealing their original shares.
It starts with each party generating a new polynomial of maximal degree that pass through at its origin. Then the evaluations of these at are computed by each party, which we will refer to as . All of this can be represented as a matrix of values:
As it stands, the information in the th row is known only to the th party. A fair (non-adversarial) distributor/dealer sends information across parties such that the th party now also knows all the information from the th column. Particularly, becomes known to the th party alongside which they already knew. This does not reveal the original shares of the parties to each other.
Now, it is possible to create a new set of polynomials that pass through at points . Note that each is encoding some information from all the different random polynomials constructed at the previous stage. This can be represented as kind of a transpose of the original matrix s.t. the columns are evaluations of polynomials .
It is important to realize that unlike which are randomly chosen to be of maximal degree with only a single constraint at their origin evaluation, are determined through their constraints with Lagrange interpolation and have a maximal degree of as a result.
Now, the polynomial , as well as its value at the origin , are known only to the th party. It turns out that any distinct collection of identifies (through Lagrange interpolation) the same polynomial of maximal degree and further this polynomial passes through at the origin.
If this claim, which we will call, origin transfer lemma, is indeed true, all the parties now have updated shares for secret that they computed from their original shares for and (along with some information from others) without revealing those shares to others. Further, any of these new shares can be used for reconstructing secret as we wanted.
The only thing left now is to prove the origin transfer lemma.
Proof of origin transfer lemma: First, let us try to visually demonstrate what we are trying to prove. Consider an matrix whose elements represents evaluations of a series of polynomials at points . Complicating the matters is the fact that both individual rows and individual columns are associated with particular polynomials. For example, the elements of the first row represents the evaluations of polynomial at , while the first column represents the evaluation of polynomial at etc. Note that we can write this a bit more concisely as follows:
We obtained this matrix simply by combining all the information from the previous section. First column corresponds to evaluations of . are random values picked by each party such that each row corresponds to evaluations of random polynomials of maximal degree . Finally, of the first row are deterministically obtained from the Lagrange interpolations of columns of , which create as described before, whose evaluations at corresponds to .
What about in the first row? It is defined as a polynomial obtained from any subset of , and therefore has maximal degree . But if it is defined through a particular subset, the rest of the evaluations that are outside of that subset must be shown to be correct. Further, we do not know its evaluation at which needs to equal for the origin transfer lemma to be correct.
All row polynomials, and , are defined through Lagrange interpolation of evaluations. Specifically, we will define them through their evaluations at :
The column polynomials , on the other hand, use all evaluations available for a maximal order of :
The origin transfer lemma, as we called it (for the lack of a better term), is simply about proving two set of facts: that and that . If these can be proved based on the definitions above, we would be done.
We begin by writing out the definition of :
As we can see from this result, is just a linear combination of the column of values , and the same weights apply to all regardless of which column it is.
Mirroring this on the horizontal direction, we can also write the relationships between and row values , but for any points of evaluation:
Further, since is produced by Lagrange interpolation, we can compute f^+(0) directly,
Note that in the last step, we use a similar reasoning to the one we used for computations, to obtain , which is exactly what we wanted. The first part of the lemma is now proven.
The second part, that , is a bit more difficult. It is possible to prove this directly from the definitions above but a simpler argument goes as follows.
We argue that, now that we know for a fact that this relationship holds at points, as we explained earlier in our discussion of and which correspond to . Given this and the fact that the maximal orders of and are , it is easy to see that the above equality holds for all , as there are contraints for degrees of freedom.
Given the above equation, it is trivial to show that ,
This concludes our proof of the origin transfer lemma.