# Secret Sharing
## Shamir Secret Sharing

Let's go over the basics of Shamir secret sharing.

Suppose I want to share a secret number (let's say 300) with my 3 friends. It's a secret so they should not be able to deduce 300 from their individual shares. The first thought that pops up in my head is to split up the number randomly and give each friend a share (let's say 49, 142, 109). This way, none of my friends can know what my number is without adding all their shares together.

Let's add another constraint. Let's say I want to make sure that *any of my two friends* can get together and figure out my secret. This means that all my friends need to have an equal share of the secret. So I give them the value 150.

Now let's add another constraint. *All the shares of the secret should be distinct from each other, and one share should not reveal anything about another share.* Difficult, eh?

So it turns out that we need to move away from simple arithmetic and start using **polynomials**. One of the constructs of polynomials is that given $t+1$ evaluations of $(x,y)$, there is a unique degree-$t$ polynomial that satisfies those evaluations. For example, for a linear equation $y=ax+b$, given two distinct evaluations, we can figure out $a,b$ values.

Naturally, we can evaluate any random $x$ on a known polynomial. But we can also perform the evaluation without calculating the coefficients of a polynomial by using the **Lagrange interpolation**, a formula which takes as input $t+1$ evaluations and a random $x$ value and outputs the evaluation.

Building off of this, I can hide my secret in a polynomial and share only the evaluations of the polynomials to my friends. If I want to share my secret with 5 friends and make sure at least 3 friends are needed to figure out the secret, I would create a degree-$2$ polynomial $f(x)=ax^2+bx+c$ and create 5 evaluations. So how do I hide my secret? I could set it as the evaluation of any number, but for convenience I'll use zero: $f(0)$.

A generalized explanation of this concept would be:
> Share a secret $x\in Z_q$ (for a prime number q) with $n$ parties by creating a degree $t$ polynomial $f(x)$ that satisfies $f(0)=x$ and distributing $n$ evaluations to each party. Secret will not be revealed as long as at most $t$ parties are corrupted.

Now if you've been paying attention, you would've noticed that I have full knowledge of the secret at every point of the secret sharing process. But what if we want to make sure that **no one can know the secret unless more than $t$ parties have been corrupted**?

## Joint Random Secret Sharing

Turns out if all of my friends perform the above secret sharing protocol individually, they can share a secret without anyone knowing about it (unless $t+1$ of them are corrupt, of course).

This might not make sense intuitively, so let me illustrate an example. Suppose there are 3 parties and they have each created a secret:
$$x_1=9$$ $$x_2=4$$ $$x_3=-7$$

They also created secret-hiding polynomials: $$f_1(x)=5x+9$$ $$f_2(x)=13x+4$$ $$f_3(x)=21x-7$$

Based on an agreed system of indexing (who is 1, 2, or 3), they create and share evaluations of their polynomials:

Party 1->Party 2: f_1(2)=19
Party 1->Party 3: f_1(3)=24
Party 2->Party 3: f_2(3)=43
Party 2->Party 1: f_2(1)=17
Party 3->Party 1: f_3(1)=14
Party 3->Party 2: f_3(2)=35

Given that the parties also have evaluations of their own polynomials, Party 1 ends up with 3 evaluations of 3 separate polynomials at $x=1$. (Also Party 2 at $x=2$ and Party 3 at $x=3$):
$$
\text{Party} \space 1: f_1(1)=14, f_2(1)=14, f_3(1)=17
$$$$
\text{Party} \space 2: f_1(2)=19, f_2(2)=30, f_3(2)=35
$$$$
\text{Party} \space 3: f_1(3)=24, f_2(3)=43, f_3(3)=54
$$

Now, adding up all these evaluations becomes equal to an evaluation of the sum of all polynomials:
$$
f_{sum}(x)=f_1(x)+f_2(x)+f_3(x)=39x+6
$$
where the new joint secret $f_{sum}(0)=6$ is not known to any of the parties unless 2 out of the 3 parties are corrupt.