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:

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?

• 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? Feb 21 '19 at 14:04
• @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? 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 . 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.

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

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