How to apply lagrange interpolation on bilinear pairings? 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:


$pk_{common} = \sum_{i=1}^{t+1} l_{i}*pk_{i}$
$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?
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.