Try   HackMD

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

s 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.


Secret Sharing Schemes

A

(t,n)-secret sharing scheme splits a (secret) value/mathematical object
s
into
n
different shares to be distributed to multiple parties, such that
t+1n
distinct shares are necessary and sufficient to reconstruct
s
.

This would mean that there is a certain amount of redundency of information in each of the shares (at least as much as

n/(t+1)) such that accumulation of
t+1
of them is enough to learn all the necessary information to determine
s
(which we refer to as
n
as if there was no redundency). Further, this redundency of information must be distributed to different shares such that any
(t+1)
of them would be sufficient for reconstructing
s
.


Shamir Secret Sharing

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

f(x). If the secret to be shared
s
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
f
at the origin,
f(0)=s
. There are infinite number of polynomials with
f(0)=s
however, and therefore, the choice of
f
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

(t,n)-secret sharing scheme (which requires
t+1
shares to reveal the secret), the sensible choice for the maximal degree is
t
, as knowing the evaluations of such a polynomial at
t+1
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

s in some way to
n
participants such that any
t+1
of them are enough to recover
s
.

There are various ways one can randomly choose a polynomial

f(x)=s+a1x1+a2x2+...+atxt of maximal degree
t
such that it passes through
s
at the origin. The simplest way would be to randomly sample the coefficient vector
fa=[a1,...,an]
from a field.

As we have discussed before, this same polynomial can be represented instead through its evaluation set

fx¯={(x1,f(x1)),(x2,f(x2)),...,(xn,f(xn))} as long as
xi0
and it contains at least
nt+1
values evaluated at unique points within it (redundant if more elements are in it than
t+1
). In fact, any
t+1
element subset of
fx¯
is sufficient to reconstruct
f(x)
through Lagrange interpolation:
f(x)=i=1t+1lxi(x)f(xi)lxi(x)=j=0,jit+1xxjxixj

A distributor simply gives out a single element of the evaluation set

(xi,f(xi)) to each party as a share. It is clear that
t+1
shares would allow discovery of
f(x)
and therefore its evaluation of it at the origin
f(0)=s
. We can refer to this procedure as
Reconst
,
s=Reconst((x1,f(x1)),(x2,f(x2)),...,(xt+1,f(xt+1)))
This concludes the description of the secret sharing scheme.


Properties

It is important for SSS secret reconstruction

Reconst 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

t+1, particularly
2t+1
in the naive approach. With further communication between parties, this can be reduced back to
t+1
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

s1 and
s2
that are shared across
n
parties as before with
t+1
shares needed for reconstructing each. For the
i
th party, the shares are
(xi,f1(xi))
and
(xi,f2(xi))
, which means that we are assuming the evaluation set
{xi=1:n}
is the same for both polynomials
f1,f2
that secrets are embedded in.

Now, we wish to show that if

s3=αs1+βs2, it is possible to reconstruct this new secret
s3
from any
t+1
subset of the original shares. This is very straightforward for individual parties. They can simply compute a share for the new secret
s3
as
(xi,αf1(xi)+βf2(xi))
from their existing shares for secrets
s1
and
s2
. Using the linearity of Lagrange interpolation at the same set of evaluation points
xi
,
s3=Reconst((x1,αf1(x1)+βf2(xi)),...,(xt+1,αf1(xt+1)+βf2(xt+1)))=αReconst((x1,f1(x1)),...,(xt+1,f1(xt+1)))+βReconst((x1,f2(x1)),...,(xt+1,f2(xt+1)))=αs1+βs2

Adding two polynomials

f1(x) and
f2(x)
that pass through
s1
and
s2
at the origin simply results in a polynomial
f3(x)
(which we can obtain through
t+1
shares of
s3
) that passes through
s3=s1+s2
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

s3=s1s2. Consider a polynomial
f3(x)=f1(x)
f2(x)
where
f1
and
f2
are defined as before. It is clear that
f3(0)=f1(0)f2(0)
=s1s2=s3
, which means that this polynomial passes through
s3
at the origin.

However, the maximal degree of the polynomial

f3(x) is
2t
, as it is a multiplication of two polynomials with maximal degree
t
. This would mean that it would require
2t+1
distinct evaluations of this polynomial for it to be reconstructed through Lagrange interpolation.

As the evaluation of

f3(x) at a particular point
xi
is simply
f3(xi)=f1(xi)f2(xi)
, and any
2t+1
distinct evaluations of
f3(x)
uniquely identifies it among all polynomials with maximal degree
2t
, knowledge of
(xi,f1(xi)f2(xi))
at
(2t+1)
distinct evaluation points
xi
is enough to recover
f3(x)=f1(x)f2(x)
through Lagrange interpolation. Therefore, each individual party can create
(xi,f1(xi)f2(xi))
from
(xi,f1(xi))
and
(xi,f2(xi))
that they already have, so that they can use it to collaborate with
2t
other parties to reconstruct
s3
directly.

If

n parties have shares for secrets
s1
and
s2
,
2t+1n
parties can come together to obtain secret
s3
using only their shares for
s1
and
s2
. This would of course require that
t<n/2
at the beginning. Further, it is not ideal that required number of participants are now almost double the original
t+1
for reconstructing secrets.


A secure degree reduction for multiplicative homomorphism

Clearly, using

f3(x)=f1(x)f2(x) directly is not viable if we need to keep the required number of participants at
t+1
. In this section, we present a method where a new polynomial of maximal degree
t
is communicated and shared between
n
parties s.t. it passes through the multiplicative secret
s3=s1s2
at the origin.

This is accomplised by each party making computations on the shares they already have for

s1 and
s2
and communicating to other parties some of the results of these computations without revealing their original shares.

It starts with each party

i generating a new polynomial
fi(x)
of maximal degree
t
that pass through
f1(xi)f2(xi)
at its origin. Then the evaluations of these
fi(x)
at
{x1,x2,...,xn}
are computed by each party, which we will refer to as
{zi1,zi2,...,zin}
. All of this can be represented as a matrix of values:
0x1x2...xnf1(x)|f1(x1)f2(x1)z11z12...z1nf2(x)|f1(x2)f2(x2)z21z22...z2n..................fn(x)|f1(xn)f2(xn)zn1zn2...znn

As it stands, the information in the

ith row is known only to the
i
th party. A fair (non-adversarial) distributor/dealer sends information across parties such that the
i
th party now also knows all the information from the
i
th column. Particularly,
[z1i,z2i,...,zni]
becomes known to the
i
th party alongside
[zi1,zi2,...,zin]
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

fi(x) that pass through
[z1i,z2i,...,zni]
at points
[x1,x2,...,xn]
. Note that each
fi(x)
is encoding some information from all the
n
different random polynomials
f
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
f
.
f1(x)f2(x)...fn(x)0|v1?v2?...vn?x1|z11z12...z1nx2|z21z22...z2n...............xn|zn1zn2...znn

It is important to realize that unlike

fi(x) which are randomly chosen to be of maximal degree
t
with only a single constraint at their origin evaluation,
fi
are determined through their
n
constraints with Lagrange interpolation and have a maximal degree of
n1
as a result.

Now, the polynomial

fi, as well as its value at the origin
vi=fi(0)
, are known only to the
i
th party. It turns out that any distinct
t+1
collection of
(xi,vi)
identifies (through Lagrange interpolation) the same polynomial
f+(x)
of maximal degree
t
and further this polynomial passes through
s3=s1s2=f1(0)f2(0)
at the origin.

0x1x2...xnf+(x)|f1(0)f2(0)=s3v1v2...vn

If this claim, which we will call, origin transfer lemma, is indeed true, all the parties now have updated shares

(xi,vi) for secret
s3
that they computed from their original shares for
s1
and
s2
(along with some information from others) without revealing those shares to others. Further, any
t+1
of these new shares can be used for reconstructing secret
s3
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

(n+1)×(n+1) matrix whose elements represents evaluations of a series of polynomials at points
[0,x1,x2,...,xn]
.
0x1x2...xnf3(x)f1(x)f2(x)...fn(x)0f+(x)|f1(0)f2(0)?v1v2...vnx1f1(x)|f1(x1)f2(x1)z11z12...z1nx2f2(x)|f1(x2)f2(x2)z21z22...z2n.....................xnfn(x)|f1(xn)f2(xn)zn1zn2...znn
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
f+(x)
at
[0,x1,x2,...,xn]
, while the first column represents the evaluation of polynomial
f3(x)
at
[0,x1,x2,...,xn]
etc. Note that we can write this a bit more concisely as follows:
0x1x2...xnf3(x)f1(x)f2(x)...fn(x)0f+(x)|f3(0)?v1v2...vnx1f1(x)|f3(x1)z11z12...z1nx2f2(x)|f3(x2)z21z22...z2n..................xnfn(x)|f3(xn)zn1zn2...znn

We obtained this matrix simply by combining all the information from the previous section. First column corresponds to evaluations of

f3(x).
zij
are random values picked by each party such that each row corresponds to evaluations of random polynomials
fi(x)
of maximal degree
t
. Finally,
vi
of the first row are deterministically obtained from the Lagrange interpolations of columns of
zij
, which create
fi(x)
as described before, whose evaluations at
0
corresponds to
vi
.

What about

f+(x) in the first row? It is defined as a polynomial obtained from any
t+1
subset of
vi
, and therefore has maximal degree
t
. 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
0
which needs to equal
f3(0)=f1(0)f2(0)
=s3=s1s2
for the origin transfer lemma to be correct.

All row polynomials,

fi(x) and
f+(x)
, are defined through Lagrange interpolation of
t+1
evaluations. Specifically, we will define them through their evaluations at
[x1,...,xt+1]
:

fr(x)=c=1t+1(j=0,jct+1xxjxcxj)fr(xc)=c=1t+1(j=0,jct+1xxjxcxj)zrcf+(x)=c=1t+1(j=0,jct+1xxjxcxj)f+(xc)=c=1t+1(j=0,jct+1xxjxcxj)vc

The column polynomials

fc(x), on the other hand, use all
n
evaluations available for a maximal order of
n1
:
fc(x)=r=1n(j=0,jrnxxjxrxj)fc(xr)=r=1n(j=0,jrnxxjxrxj)zrc

The origin transfer lemma, as we called it (for the lack of a better term), is simply about proving two set of facts: that

f+(0)=f3(0) and that
f+(xc)=vcc{t+2,...,n}
. If these can be proved based on the definitions above, we would be done.


We begin by writing out the definition of

vc:
vc=fc(0)=r=1n(j=0,jrnxjxrxj)fc(xr)=r=1n(j=0,jrnxjxrxj)zrc=r=1nγrzrc.
As we can see from this result,
vc
is just a linear combination of the column of values
z:c
, and the same weights apply to all
vc
regardless of which column
c
it is.

Mirroring this on the horizontal direction, we can also write the relationships between

fr(0) and row values
zr:
, but for any
t+1
points of evaluation:
fr(0)=f3(xr)=c=1t+1γczrc.

Further, since

f+(x) is produced by Lagrange interpolation, we can compute f^+(0) directly,
f+(0)=c=1t+1(j=0,jct+1xjxcxj)vcf+(0)=c=1t+1γc(r=1nγrzrc)f+(0)=c=1t+1r=1nγcγrzrcf+(0)=r=1nγr(c=1t+1γczrc)f+(0)=r=1nγrf3(xr)=f3(0).

Note that in the last step, we use a similar reasoning to the one we used for

vc computations, to obtain
f3(0)
, which is exactly what we wanted. The first part of the lemma is now proven.


The second part, that

f+(xc)=vcc{t+2,...,n}, 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,

f+(x)=r=1nγrfr(x) now that we know for a fact that this relationship holds at points,
x{x1,...,xt+1}
as we explained earlier in our discussion of
vc=f+(xc)
and
z:c
which correspond to
f:(xc)
. Given this and the fact that the maximal orders of
f+(x)
and
f:(x)
are
t
, it is easy to see that the above equality holds for all
x
, as there are
t+1
contraints for
t+1
degrees of freedom.

Given the above equation, it is trivial to show that

c{t+2,...,n},
f+(xc)=r=1nγrfr(xc)=r=1nγrzrc=vc
This concludes our proof of the origin transfer lemma.


References

  1. [AHS20] Jean-Philippe Aumasson, Adrian Hamelink, and Omer Shlomovits. A Survey of ECDSA Threshold Signing. https://eprint.iacr.org/2020/1390.pdf, in IACR, 2020.
  2. [Sha79] Adi Shamir. How to Share a Secret. https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf, 1979.
  3. Some relevant stackexchange posts: https://crypto.stackexchange.com/questions/15395/can-i-use-shamirs-secret-sharing-scheme-for-multiplicative-homomorphism-for-sec
    https://crypto.stackexchange.com/questions/13088/secure-degree-reduction-for-shamirs-secret-sharing