I have seen in some places applications of Shamir secret sharing and lagrange interpolation mixed with bilinear pairings, however I fail to understand how this works. For instance, here I find the statements:

  1. $pk_{common} = \sum_{i=1}^{t+1} l_{i}*pk_{i}$
  2. $e(h, pk_{common})$

If $pk_{common}$ is a point in some $\mathbb{G}$, how can a lagrange interpolation result (the polynomial or an evaluation for $x=0$) transform into a suitable point that can be used in the pairing function?

  • $\begingroup$ I'm missing where you're getting confused; $pk_i$ and $pk_{common}$ are points in $\mathbb{G}$, and $l_i$ are integers; computing $pk_{common}$ from $pk_i$ and $l_i$ is straight-forward; and as $pk_{common}$ is a point in $\mathbb{G}$, it is a valid input to $e$. Are you asking how we come up with the $l_i$ values? $\endgroup$
    – poncho
    Feb 21 '19 at 14:04
  • $\begingroup$ @poncho "Are you asking how we come up with the $l_{i}$ values?" Most probably yes. Because from the wikipedia definition, those are "lagrange basis polynomials". So I suppose $pk_{i}$ is a point and $l_{i}$ is a scalar, but then I don't understand how this connects with the definition of the lagrage interpolation. PS: Are you the author of the blog post? $\endgroup$
    – shumy
    Feb 21 '19 at 14:21

Are you asking how we come up with the $l_i$ values?" Most probably yes

How we find these values is pretty much standard Shamir Secret Sharing, and has nothing directly to do with the pairing we'll do later.

To do a quick review, in Shamir Secret Sharing, we pick a finite field, and a $t$ degree polynomial $P$ (whose constant term is the secret we'll share, and the rest of the terms are random [1]. We generate shares by assigning each share a nonzero index $i_j$ (which can be public), and the value $y_j = P( i_j)$, that is, the polynomial evaluated at the index.

Now, if we know $t+1$ shares, we know enough to reconstruct the polynomial (and thus the constant term, which is the secret); the standard way to do this is to not bother computing the entire polynomial, but instead just compute the values:

$$l_j = \frac{\prod_{k=1,...,t+1, k \ne i}-i_k}{\prod_{k=1,...,t+1, k \ne i}i_j-i_k}$$

And, this we can reconstruct the secret as:

$$s = \sum_{i=1}^{t+1} l_j y_j $$

If you go through the math, you'll find that this value $s$ is precisely the constant term of the polynomial $P$.

The $l_j$ values are precisely what you are asking about.

Now, the standard Shamir method has the secret (and the coefficients of the polynomial) being elements of the finite field; what this paper does is tweak things a bit by making the secret, the rest of the coefficients and the secret $y_j$ values being elliptic curve points (one way of thinking of it is that, instead of having the secret being a value $s$, it is actually the point $sG$). They then have the finite field that the $i_j$ values work in being $GF(q)$, where $q$ is the prime order of the curve. Because the above algorithm never needs to multiply two different $y_j$ values, this all works out.

[1]: Note: we allow the high order term of the polynomial to be 0. Standard terminology would state this would be a $t-1$ or lower degree polynomial; however, we need to allow this case to provide for the informational security that Shamir provides.

  • $\begingroup$ "instead of having the secret being a value $s$, it is actually the point $sG$". OK, that enlightened my doubts. $\endgroup$
    – shumy
    Feb 22 '19 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.