Does lagrange interpolation work with points in an elliptic curve?

Question

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.

Answer 1

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

EDIT: other half added below.

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

Answer 2

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.

Answer 3

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}