# Does lagrange interpolation work with points in an elliptic curve?

Defining the lagrange interpolation for $$x=0$$ as $$\mathcal{L} = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}$$ with $$l_{i}$$ as the lagrange basis polynomials. Does this hold if we apply the elliptic curve generator for each share $$y_{i} \times G \rightarrow Y_{i}$$ ?

1. Defining the elliptic curve version as $$\mathcal{L}_{G} = \sum_{i=1}^{t+1} Y_{i} \times l_{i}$$

2. Using a set of shares for the secret $$\alpha$$ as $$S_{\alpha} = \{i \in [1, t + 1] : (i, y_{i})\}$$ and elliptic curve point shares as $$P_{\alpha} = \{i \in [1, t + 1] : (i, y_{i} \times G)\}$$

I expect $$\mathcal{L}(S_{\alpha}) \times G = \mathcal{L}_{G}(P_{\alpha}) = \alpha \times G$$ to be the same, as also any homomorphic properties to hold.

As far as I know, I haven't seen anyone formulating this or use it in practice in any existing implementation. But the math seems correct. I just don't want to start implementing it without being sure that it works.

• What would the result of Lagrange interpolation on a curve mean? There is only a group structure, not a ring structure, so there is no notion of polynomials over curve points. – Squeamish Ossifrage May 22 '19 at 15:00
• Not really interested on the meaning, if it works. Does that invalidate my math? I suppose you can view it as interpolation of encrypted shares. – shumy May 22 '19 at 15:14
• Ummm…how can something meaningless work? What is your criterion for ‘working’ and ‘validity’ if the juxtaposition of symbols has no meaning? – Squeamish Ossifrage May 22 '19 at 15:16
• I should also state that $y_{i}$ is defined in the same field used for the elliptic curve. And since the elliptic curve generator has distributive properties, I believe I can do all the operations I am proposing. It works if the final equality is valid. – shumy May 22 '19 at 15:24
• You can make a map from the scalar ring into $G$ that maps $x_i \in R$ to $Y_i \in G$ by $x \mapsto \sum_i [l_i(x)]Y_i$ where $l_i$ are the Lagrange basis polynomials for the $\{x_i\}$. This map has a polynomial representation $x \mapsto [f(x)]G$ where $f$ is the Lagrange interpolation sending $x_i$ to $\log_G Y_i$ in the scalar ring, but of course we can't find that representation without computing discrete logs. But none of this gives a map from curve points to curve points. – Squeamish Ossifrage May 22 '19 at 17:41

This is "half an answer" while I think about the other half :)

The mathematical model that I find most useful for all discrete logarithm based cryptography is that of a vector space over a finite field. In many ways, the multiplicative-group implementation and the elliptic curve implementation are isomorphic, although it can be confusing because it's natural to write the former multiplicatively and the latter additively.

For example, the multiplicative-group setup usually has you pick two primes $$p, q$$ with $$q$$ dividing $$(p-1)/2$$, and the embedding function $$x \mapsto g^x \mod p$$ where $$g$$ is an element of multiplicative order $$q$$ modulo $$p$$ (e.g. $$g^q \equiv 1$$ modulo $$p$$).

In the elliptic curve setup, you have a base point $$P$$ of order $$q$$, there is no small-$$p$$ and the embedding function is $$x \mapsto x \times P$$.

The important mathematical structure here is that the target of the embedding function is a vector space (of dimension 1) over $$\mathbb F_p$$ and in this model, the embedding function is linear. That lets you work out a lot of things.

I know of several projects that have done various secret-sharing stuff in the multiplicative-group setting, a lot of them concerned with electronic voting, and all of this should port almost 1:1 to the elliptic curve setting. In fact I wish people would do this. You can indeed generate a (Shamir) secret-shared secret key among some authorities, everyone publishes their local public key and then one computes the global election public key as a linear combination (which is what Lagrange is doing) $$Y = \sum_i c_i \times Y_i$$ where the $$Y_i$$ are the local public keys.

In principle you could define a product $$\otimes$$ on the target space (e.g. the curve) via $$(x \times P) \otimes (y \times P) := (xy \mod q) \times P$$ since the embedding function is bijective. This makes the target space into a ring and should have most of the properties that you need to do things with polynomials there, answering SO's question (I think). The practical problem here is that actually computing this product is equivalent to solving CDH. This should not be a problem in two cases though: (1) in a security proof where you just want to reason about things, (2) in a secret-sharing scheme where the parties who want to compute this product hold the necessary preimages in the finite field.

# EDIT

It should all still work fine. For example:

Over a finite field you can $$(k, n)$$ share a secret $$s$$ by setting $$a_0 = s$$, picking $$a_1 ... a_{k-1}$$ at random and creating the shares $$s_i = \sum_{t=0}^{k-1} a_t i^t$$. To recover from $$k$$ shares $$(i, s_i)_{t=1}^k$$ you compute $$\sum_{t=1}^k \lambda_t s_t$$ where the $$\lambda_t$$ are the Lagrange coefficients.

If your secret $$S$$ is in the curve, and if you can pick random curve points $$A_1 ... A_{k-1}$$ then you can create shares by $$S_i = \sum_{t=0}^{k-1} [i^t] A_t$$ where $$[t]A$$ denotes scalar multiplication for a scalar t and curve point $$A$$. The recovery formula is $$S = \sum_{t=1}^k [\lambda_t] S_t$$. The reason this works is that both the $$i^t$$ and the $$\lambda_t$$ are scalars so you're never multiplying curve points.

(You can create a random curve point by picking a random scalar $$r$$ and computing $$[r]P$$. Creating a random curve point where you don't know the dlog is harder, but unnecessary here.)

What's going on under the hood here is that, since every curve point has exactly one discrete logarithm, we can define $$s$$ such that $$S = [s]P$$ and $$a_1 ... a_{k-1}$$ such that $$A_t = [a_t]P$$ where $$P$$ is the base point. Using linearity, the way we create the shares is thus $$S_i = \sum_{t=0}^{k-1} [i^t a_t] P$$ so if we choose $$s_i$$ such that $$S_i = [s_i]P$$ then for recovery we get $$\sum_{t=1}^k [\lambda_t s_t]P = [\sum_{t=1}^k \lambda_t s_t] P$$. But the coefficient in the brackets here is exactly the recovery formula for secret sharing over a finite field, so we recover $$[s]P = S$$ as expected.

(This is incidentally also an example of how you can happily reason about taking discrete logs in security proofs.)

• True, in principle there is an isomorphism of the curve group and some subgroup of $\mathbb Z/p\mathbb Z$ for some $p$ and so in principle a ring structure exists, but it's not something that can be computed, as the OP seems to want. If you want to do secret-sharing for a…secret curve point, then one can use $x \mapsto \sum_i [l_i(x)]Y_i$ for random points $Y_i$ and evaluate it at the points $(1, 2, \dots)$. And there are multiparty computations one can do this way like threshold signatures, but the OP specifically asked about Lagrange interpolation on a curve. – Squeamish Ossifrage May 22 '19 at 20:47
• "This should not be a problem [...] in a security proof where you just want to reason about things" Of course it is a problem; in most cases your algorithm must run in poly-time, so you can't use a CDH oracle (unless you assume towards contradiction that CDH does not hold). That's in part why bilinear maps are used; they provide a partial solution to the problem of computing products in the exponent. – fkraiem May 23 '19 at 6:41
• But, $Y=\sum_{i} c_{i} \times Y_{i}$ should translate to addition of elliptic curve points $c_{1} \times Y_{1}\ +\ ..\ +\ c_{n} \times Y_{n}$. There should be no problem about the CDH assumption! – shumy May 23 '19 at 9:29
• Maybe the confusion is that $x$ values in the $c_{i}$ coefficients do not translate to curve points, they are scalars. In fact, just constants of the indices in the sharing scheme, $c_{i} = \prod_{m \neq i}{ \frac{m}{i - m}}$. – shumy May 23 '19 at 9:40

Defining $$l_{i} = \prod_{m=1, m \neq i}^{t+1}{ \frac{m}{i - m}}$$ works perfectly fine. I have done a port of rust-threshold-secret-sharing using curve25519-dalek with positive results.

Let prime $$r$$ denote the order of the elliptic curve. Let $$G$$ denote the generator point. There is a multiplication law $$P^{\prime}= [a]P$$ defined between $$a, a \in Z^{\ast}_{r}$$ and $$P$$ where $$P$$ is a point on the elliptic curves. Thus, we have following equation: $$\begin{equation} [a \cdot b ]G = [a]P \text{ where } P = [b]G \end{equation}$$

In Shamir secret sharing scheme, secret $$S$$ can be calculated from its shares by: $$s = \sum_{i=1}^{t+1}l_i \cdot s_i \text{ mod } r$$ where $$l_i = \prod_{m=1,m \neq i}^{t+1}\frac{m}{i-m}$$. Hence,

$$\begin{equation} [s]G = [\sum_{i=1}^{t+1}l_i \cdot s_i \text{ mod } r]G \end{equation}$$

Combine equation (1) and (2), we have:

$$\begin{equation} [s]G = \sum_{i=1}^{t+1}[l_i]P_i \quad \text{where} \quad P_i = [s_i]G \end{equation}$$