# Feldman DKG Explained (With Pen & Paper Example)

## Goal:
Distribute a secret among multiple parties, so that:
- No single party knows the secret.
- Any threshold number of parties (t) can reconstruct it.

---

## Setup
- Participants: $P_1$, $P_2$, $P_3$
- Threshold: t = 2
- Field: $Z_{17}$ (prime number 17)

Each participant generates their own degree-1 polynomial:

| Participant | Polynomial $f_i(x)$ |
|-------------|----------------------|
| $P_1$ | $f_1(x)$ = 3 + 2x |
| $P_2$ | $f_2(x)$ = 5 + 7x |
| $P_3$ | $f_3(x)$ = 9 + 4x |

The constant terms ($a_{i0}$) are their secret contributions.

Final Secret:
$$s = a_{10} + a_{20} + a_{30} = 3 + 5 + 9 = 17 \equiv 0 \pmod{17}$$

---

## Step 1: Generate Shares

Evaluate each polynomial at x = 1, 2, 3:

### Shares from $P_1$
$$ s_{11} = 5$$
$$s_{12} = 7$$
$$ s_{13} = 9$$

### Shares from P_2
$$s_{21} = 12$$
$$ s_{22} = 2$$
$$s_{23} = 9$$

### Shares from P_3
$$s_{31} = 13$$
$$s_{32} = 0$$
$$s_{33} = 4$$

---

## Step 2: Each Participant's Final Share

Add shares from all polynomials:

| Participant | Final Share $s_j$ |
|-------------|---------------------------------|
| $P_1$ | $s_1$ = 5 + 12 + 13 = 30 ≡ 13 |
| $P_2$ | $s_2$ = 7 + 2 + 0 = 9 |
| $P_3$ | $s_3$ = 9 + 9 + 4 = 22 ≡ 5 |

---

## Step 3: Reconstructing Secret s using $s_1$ = 13 and $s_$2 = 9

Threshold $t = 2$ means any two shares are enough.

### Compute Lagrange Coefficients at $x = 0$

$$\lambda_1 = rac{0 - 2}{1 - 2} = 2$$
$$\lambda_2 = rac{0 - 1}{2 - 1} = -1 \equiv 16 \pmod{17}$$

### Compute Secret

$$s = \lambda_1 \cdot s_1 + \lambda_2 \cdot s_2 = 2 \cdot 13 + 16 \cdot 9$$

Compute modulo 17:

- 2 * 13 = 26 ≡ 9
- 16 * 9 = 144 ≡ 8

Sum:
$$s = 9 + 8 = 17 \equiv 0 \pmod{17}$$

---

## Final Secret:
$$s = 0$$

---

## Recap

| Using Shares | Reconstructed Secret $s$ |
|-------------------|------------------------|
| $s_1$ = 13, $s_2$ = 9 | 0 |
| $s_2$ = 9, $s_3$ = 5 | 0 |
| $s_1$ = 13, $s_3$ = 5 | 0 |