[SPEC] Writing out the math for t-out-of-n keygen

[akileshtangella]

Goal of this note is to extend $n\text{-of-}n$ CGGMP '21 to $t\text{-of-}n$ CGGMP '21 using ideas from GG '20.

Review of $(t, n)$ Feldman VSS

$(t,n)$ secret sharing is one where $t+1$ parties are needed to reconstruct secret. Let the dealer have a secret $\sigma$. Feldman VSS works as follows:

1. Dealer generates a random $t$-degree polynomial $p(z) = \sigma + a_1z +...+ a_tz^t$.
2. Dealer sends each participant $i$: $\sigma_i = p(i)$, $v_j = g^{a_j}$ (for all $j \in [1..t]$), and $v_0 = g^{\sigma}$.
3. Participant $i$ can check its share is consistent by checking: $g^{\sigma_i} = \Pi_j v_j^{i^j}$.

Phase 1

$P_i$ samples $u_i \leftarrow \mathbb{F}_q$. Set $U_i = g^{u_i} \in \mathbb{G} $. Computes a commitment to $U_i$. Broadcasts commitment to $U_i$.

Phase 2

De-commit from $U_i$. Do a $(t-1, n)$ Feldman-VSS of $u_i$. Note: each party $i$ receives a vector of length $n-1$: $(x_{i,1},...,x_{i,n})$ of secret shares. Let $x_i$ be the sum of the components of these vectors. Note that $x_i$ is $(t-1, n)$ Shamir secret sharing of the the secret key $x = \sum_i u_i$.

Note the values $X_i = g^{x_i}$ are public.

Also, set the group public key as $U_1 \cdot...\cdot U_n$, which is indeed $g^x$.

Phase 3

Each party now has access to an $x_i$ and every party knows $X_i$ for each $i$. From here on, follow CGGMP '21's key generation skipping the first step of round 1 (sampling $x_i \leftarrow \mathbb{F}_q$ and setting $X_i = g^{x_i}$). Also skip the second step of the output (setting $X = \prod_i X_i$). Basically, follow CGGMP '21's steps for the Schnorr proof that party $i$ knows the discrete log of $X_i$.