## Distributed Keys

When dealing with cryptography in general, the source of truth you use for encrypting your secrets is usually a single point of failure, in any naïve implementations. This could be the private key used to generate / verify signatures for example. Also, when decentralizing cryptography protocols, traditional ideas of verification must be extended to encompass many parties, with the intention of removing single point failures, not adding more. This goes over the basics of related distribution protocols for secret sharing and validation.

### Shamir's Secret Sharing

[This](https://dl.acm.org/doi/pdf/10.1145/359168.359176) is the foundation on which many distributed key generation (DKG) protocols are based. The punchline is that it allows for $t$ individuals, out of $n$ total, to verify a signature. Not only does this allow for fault tolerance (e.g. node in the network goes down), but allows for a quorum of attestations, improving trustlessness. Maximum security would require $n>\lfloor 2t - 1\rfloor$.

At the core of this concept is the following truth. Given a set $\{(x_i,y_i)\in\mathbb{R}_2\,|\, i\in[0, t]\}$, there exists a UNIQUE polynomial $q(x)$ of degree $t-1$ such that $q(x_i)=y_i$. We then express this polynomial as:
$$
q(x) = a_0 + a_1x+\cdots+a_{t-1}x^{t-1}
$$
where $a_0$ is the secret to be shared. Discretization is then done as $s_i = q(i)$, where $s_i$ is the partial shared secret. The partial signature is therefore $s_iH(m)$, where $H(m)$ is the hashed message in the group $\mathbb{G}_1$. The uniqueness of polynomial interoplation requires knowledge of exactly $t$ of these partial shares to recover the shared secret. Knowledge of only $t-1$ means that, of the candidate $a_0^\prime\in[0,p)$, there will be again only a unique polynomial fitting $(0, a_0^\prime)$ and $(i, a_i)$, each of these $p$ unique polynomials being equally likely, thus maintaining security of the shared secret.

Recovery of the shared secret is done via Lagrange interpolation:
$$
a_0 = q(0) = \sum_{j=0}^{t-1}y_t\prod_{m=0,m\neq j}^{t-1}\frac{x_m}{x_m-x_j}$$

The problems with this, while admittedly simple and extensible, is that it assumes honesty of the participants (at no point is there an ability to verify partial shares), and further that the shared secret is known singuarly at some point in space-time, both at instantiation of the sharing and at the recovery of the shares. To address these issues, we move beyond to ...

### Feldman's VSS

This is a new approach to secret sharing that addresses the concern that the partials are not verifiable by the council. We again now generate $q(x)$, with $q(0)=a_0$ which is the secret, and transmit to all $i$ participants a partial share $s_i = f(i)$. The dealer also sends a committment $\{A_k=g^{a_k}\}_{k=0,t}$, with $g$ a generator of $\mathbb{Z}_p^\ast$. This allows for verification (that the partials form a secret) by checking:
$$
g^{s_i}\stackrel{?}{=}\prod_{k=0}^t\left(A_k\right)^{i^k}
$$
performed in the field (aka mod $p$). If participant $i$ does not satisfy the above, a complaint is made publically against the dealer, who is required to then reveal $s_i$ that satisfy the above, else they're fired! 

The biggest issue is that this protocol leaks $A_0=g^{a_0}=g^{\rm secret}\mod p$. However, assume the bad actor knows $t$ or less shares $s_i$ and $g_{a_0}$. They can then compute $\{A_k\}_{k=1,t}$ via $A_k=g^{a_k}=\prod_{i=0}^t(g^{s_i})^{\lambda_{ki}}$, where $\lambda$ satisfies $a_k=\sum_{i=0}^t\lambda_{ki}f(i)$, which is still not enough to learn about $a_0$ anymore than what you could learn from $g^{a_0}$. 

### pedersen vss

To address the concern of the secret's secrecy, we move to pedersen dkg. Now in this [scheme](https://link.springer.com/chapter/10.1007/3-540-46416-6_47), each participant generates coefficients, and the cooperation of participants is what allows for the collective generation of a secret. The public parameters in this setup are a large prime $p$, a generator $g$ of a subgroup of $\mathbb{Z}_p^\ast$, and another element in the subgroup of $\mathbb{Z}_p$ generated by $g$, $h$, where no one knows $\log_g h$. Therefore, the cost of information-theoretic secrecy of the shared secret is the hard assumption that the bad actor, or a cheating dealer, cannot solve the DL problem. 

The dealer generates two random polynomials of degree $t$, $q(x)=\sum_k a_kx^k,\tilde{q}(x)=\sum_k b_kx^k\in\mathbb{Z}_p[x]$, with again $q(0)=a_0$ the shared secret. The dealer then transmits to each participant $i$ their share $(s_i=q(i), \tilde{s}_i=\tilde{q}(i))$, and broadcasts the values $\{C_k = g^{a_k}g^{b_k}\mod p\}_{k=0,t}$. Verification of the shared secret follows by:
$$
g^{s_i}h^{\tilde{s}_i}\stackrel{?}{=} \prod_{k=0}^t\left(C_k\right)^{i^k}\mod p
$$

As before, complaints against the dealer are made public, and are rectified by the dealer transmitting $(s_i, \tilde{s}_i)$ satisfying the above lest they face disqualification.