Key Recovery Scheme

The aim of this scheme is to enable 3 players to generate a single public key which can be recovered using any $t$ of $n$ players. It is trustless and anonymous. The scheme can be used for multisig payments which appear on chain as normal payments.

The basic concept relies on the additivity of functions $(f\circ g)(a)=f(a)+g(a)$, and additive homomorphism of EC points. That way we avoid heavy MPC multiplications and keep the scheme lightweight.

The values $x_1,\dots ,x_n$ are fixed strings known by all players.

Let $⟨x⟩=\text{commit}(x)$ denote a hiding pedersen commitment to $x$.

Constructing the Curve

Each player $i$ constructs their own curves, with the resulting curve being the sum of them all. Given any t points, we can recover the original curve and hence the secret.

Player $i$ creates curve $i$

Player $i$ creates a random curve $C_i=Y+a_0+a_{1}X+\cdots +a_{t-1}{X}^{t-1}$, and broadcasts commits $A_0=⟨a_0⟩,\dots ,A_{t-1}=⟨a_{t-1}⟩$.

Then player $i$ lifts points $$R_j=(x_j,y_j)\in V(C_i)$$ sending each to player $j$.

Check $R_j\in V(C_i)$

Upon receiving player $j$ receiving $R_j$, they check that $$⟨y_j⟩+⟨a_0⟩+x_j⟨a_1⟩+\cdots +x_j^{t-1}⟨a_{t-1}⟩=\infty$$

Compute Shared Public Key

Let $C=C_1+\cdots +C_n$, then the secret key (unknown to any player) is: $$d=C(0)$$ The corresponding public key is: $$P=A_{01}+\cdots +A_{0n}=⟨C_1(0)+\cdots +C_n(0)⟩=⟨C(0)⟩$$

Key Recovery

Let $T\subseteq N$ be the subset $|T|=t$ of players recovering the secret key. Reordering as needed, all players in $T$ send their points $R_j$ for curves $C_1,\dots ,C_n$ to player 1.

For each curve $C_i$, player 1 now has $t$ points. Using either lagrange interpolation or row reduction, they can recover curves $C_1,\dots ,C_n$ and compute $C=C_1+\cdots +C_n$.

Then player 1 computes the shared secret $d=C(0)$.