# Secret sharing overview
:female_elf:
:email:
:mailbox_with_mail: :mailbox_with_mail: :mailbox_with_mail:
:male_elf: :male_elf: :male_elf:
Lorenzo Gentile
---
### Idea
Secret sharing allows a *dealer* to split a secret $s$ into a set of shares $S = \{s_1,...,s_k\}$ among a set of parties $P = \{P_1,...,P_n\}$ such that the secret $s$ can be reconstructed through the *cooperation* of chosen sets of parties, otherwise *no information* is obtainable.
---
In order to reconstruct the secret $s$ it may be required the *cooperation* of:
- $n$-out-of-$n$ parties;
- $t$-out-of-$n$ parties with $t < n$ (threshold secret sharing);
- arbritrary sets of parties (general access structure secret sharing).
---
### Key definitions
A **qualified set** is a subset of the parties $P$ allowed to reconstruct the secret $s$.
An **unqualified set** is a subset of the parties $P$ **not** allowed to reconstruct the secret $s$.
---
An **access structure** $\Gamma$ contains all the qualified sets over a set of parties $P$. Every superset of a qualified set is a qualified set, then $\Gamma$ can be defined in terms of **minimal qualified sets**.
A **secrecy structure** $\Pi$ contains all unqualified sets over a set of parties $P$. Every subset of an unqualified set in an unqualified set, then $\Pi$ can be defined in terms of **maximal unqualified sets**.
---
### A wrong example
```
3-out-of-3
s = "secret"
s_1 = "se----"
s_2 = "--cr--"
s_3 = "----et"
Send s_i to P_i for i = 1,2,3.
< 3 shares/parties are enoguh to obtain information about s!
```
---
### $n$-out-of-$n$ secret sharing
Suppose the secret $s \in \mathbb{Z}_q$ with $q$ prime (field of integers modulo $q$). Then, the delaer proceeds as follows:
- Sample $n-1$ uniformly random shares $s_1,\dots, s_{n-1} \leftarrow \mathbb{Z}_q$;
- Compute $s_n = (s-(s_1 +\dots+ s_{n-1}))$ $mod$ $q$;
- Send share $s_i$ to $P_i \in P$ for $i = 1,\dots,n$.
---
The secret $s$ can only be reconstructed if all shares $(s_1,\dots, s_n)$ are known ($s = (s_1 + ... + s_n)$ $mod$ $q$), that requires the cooperation of all the $n$ parties.
---
### Example $4$-out-of-$4$ secret sharing
Let $P = \{P_1, P_2, P_3, P_4\}$ and $s \in \mathbb{Z}_q$.
*e.g.*
$s = 42$
$q = 256$
---
The dealer splits $s$ in $s_1,\dots,s_4$, *i.e.*, samples $s_1,\dots, s_{3}$ uniformly at random from $\mathbb{Z}_q$ and sets $s_4 = (s - (s_1 + \dots + s_3))$ $mod$ $q$.
For $i = 1, \dots , 4$ sends $s_i$ to $P_i$.
$e.g.$
$s_1 = 34$
$s_2 = 75$
$s_3 = 251$
$s_4 = (42 - (34 + 75 + 251))$ $mod$ $256 = 194$
---
In that way, $P_1$,$P_2$,$P_3$,$P_4$ are required to reconstruct the secret ($s = (s_1 + ... + s_4)$ $mod$ $q$) since shares are distributed as follows:
| | $s_1$ | $s_2$ | $s_3$ | $s_4$ |
|-------|-------|-------|-------|-------|
| $P_1$ | Yes | | | |
| $P_2$ | | Yes | | |
| $P_3$ | | | Yes | |
| $P_4$ | | | | Yes |
*e.g.*
$s = (34 + 75 + 251 + 194)$ $mod$ $256 = 42$
---
### $t$-out-of-$n$ and general access structure secret sharing
Suppose the secret $s \in \mathbb{Z}_q$. Then, the delaer proceeds as follows:
- Let $T_1, . . . , T_k$ be the **maximal unqualified sets** in the secrecy structure $\Pi$. For every maximal unqualified set $T_i \in \Pi$, let $\hat{T_i} = P \setminus T_i$.
- Split $s$ in $s_1,\dots,s_k$ ($k$ different shares) as seen before and for $i = 1, \dots , k$ send $s_i$ to all parties $P_j \in \hat{T}_i$.
---
The secret $s$ can only be reconstructed if all shares $(s_1,\dots, s_k)$ are known ($s = (s_1 + ... + s_k)$ $mod$ $q$), that requires the cooperation of any qualified set of parties in the access structure $\Gamma$.
---
### Example $2$-out-of-$4$ secret sharing
Let $P = \{P_1, P_2, P_3, P_4\}$ and $s \in \mathbb{Z}_q$.
Let $\Pi = \{\{P_1\}, \{P_2\}, \{P_3\}, \{P_4\}\}$
be the secrecy structure described in terms of maximal unqualified sets,
where $T_1 = \{P_1\}$ and so on.
---
Then,
$\hat{T}_1 = P \setminus T_1 = \{P_2, P_3, P_4\}$
$\hat{T}_2 = P \setminus T_2 = \{P_1, P_3, P_4\}$
$\hat{T}_3 = P \setminus T_3 = \{P_1, P_2, P_4\}$
$\hat{T}_4 = P \setminus T_4 = \{P_1, P_2, P_3\}$
---
The dealer splits $s$ in $s_1,\dots,s_4$, *i.e.*, samples $s_1,\dots, s_{3}$ uniformly at random from $\mathbb{Z}_q$ and sets $s_4 = (s - (s_1 + \dots + s_3))$ $mod$ $q$.
For $i = 1, \dots , 4$ sends $s_i$ to all parties $P_j \in \hat{T}_i$.
---
In that way, at least $2$ parties out of $4$ are required to reconstruct the secret ($s = (s_1 + ... + s_4)$ $mod$ $q$) since shares are distributed as follows:
| | $s_1$ | $s_2$ | $s_3$ | $s_4$ |
|-------|-------|-------|-------|-------|
| $P_1$ | | Yes | Yes | Yes |
| $P_2$ | Yes | | Yes | Yes |
| $P_3$ | Yes | Yes | | Yes |
| $P_4$ | Yes | Yes | Yes | |
---
### Example general access structure secret sharing
Let $P = \{P_1, P_2, P_3, P_4\}$ and $s \in \mathbb{Z}_q$.
Let $\Pi = \{\{P_1,P_2\}, \{P_1,P_3\}, \{P_2,P_3\}, \{P_4\}\}$
be the secrecy structure described in terms of maximal unqualified sets,
where $T_1 = \{P_1,P_2\}$ and so on.
---
Then,
$\hat{T}_1 = P \setminus T_1 = \{P_3, P_4\}$
$\hat{T}_2 = P \setminus T_2 = \{P_2, P_4\}$
$\hat{T}_3 = P \setminus T_3 = \{P_1, P_4\}$
$\hat{T}_4 = P \setminus T_4 = \{P_1, P_2, P_4\}$
---
The dealer splits $s$ in $s_1,\dots,s_4$, *i.e.*, samples $s_1,\dots, s_{3}$ uniformly at random from $\mathbb{Z}_q$ and sets $s_4 = (s - (s_1 + \dots + s_3))$ $mod$ $q$.
For $i = 1, \dots , 4$ sends $s_i$ to all parties $P_j \in \hat{T}_i$.
---
In that way, $P_1,P_2,P_3$ or any of them and $P_4$ are required to reconstruct the secret ($s = (s_1 + ... + s_4)$ $mod$ $q$) since shares are distributed as follows:
| | $s_1$ | $s_2$ | $s_3$ | $s_4$ |
|-------|-------|-------|-------|-------|
| $P_1$ | | | Yes | Yes |
| $P_2$ | | Yes | | Yes |
| $P_3$ | Yes | | | Yes |
| $P_4$ | Yes | Yes | Yes | |
---
### Shamir secret sharing for $t$-out-of-$n$
Suppose the secret $s \in \mathbb{Z}_q$. Then, the delaer proceeds as follows:
- Generate $p(x) = s + c_1 x + \cdots + c_{t-1} x^{t-1}$ where $c_1, \cdots, c_{t-1}$ are randomly sampled from $\mathbb{Z}_q$.
- Each share $s_i$ is computed as $s_i = p(x_i)$ (for example $x_i = i$) and is sent to $P_i$.
---
- In order to reconstrct $s$ we compute $p(x) = \sum \limits_{i=1}^{i = t} p(x_i)\mathcal{L}_{i}(x)$ where $\mathcal{L}_{i}(x) = \prod \limits_{j = 1, j \ne i}^{j = t} \frac{x-x_j}{x_i - x_j}$, then $s = p(0)$.
Intutively, a polynomial of degree $t-1$ is completely defined by providing $t$ distinct points, i.e., $t$ shares are required to reconstrct the secret $s$.
---
### Example $3$-out-of-$4$ Shamir secret sharing:
Let $P = \{P_1, P_2, P_3, P_4\}$ and $s \in \mathbb{Z}_5$ and equal to $3$:
- Let $p(x) = s + c_1x_1 + c_2x_2 = 3 + x + 2x^2$ ($t = 3$ so degree is $2$) where $c_1, c_2$ are randomly sampled from $\mathbb{Z}_q$.
---
- Compute share $s_i=p(x_i)$ and send it to $P_i$ for $i=1,\dots,n$ (for example $x_i = i$), *i.e.*, $s_1 = p(1) = 1$, $s_2 = p(2) = 3$, $s_3 = p(3) = 4$.
---
- In order to reconstruct $s$ compute $p(x) = \sum \limits_{i=1}^{i = 3} p(x_i)\mathcal{L}_{i}(x)$ where $\mathcal{L}_{i}(x) = \prod \limits_{j = 1, j \ne i}^{j = 3} \frac{x-x_j}{x_i - x_j}$.
---
$\mathcal{L}_{1}(x) = \frac{x-2}{1-2}\frac{x-3}{1-3} = 3 + \dots$
$\mathcal{L}_{2}(x) = \frac{x-1}{2-1}\frac{x-3}{2-3} = -3 + \dots$
$\mathcal{L}_{3}(x) = \frac{x-1}{3-1}\frac{x-2}{3-2} = 1 + \dots$
$\mathcal{L}_{1}(0) = 3$
$\mathcal{L}_{2}(0) = -3$
$\mathcal{L}_{3}(0) = 1$
$p(x) = \sum \limits_{i=1}^{i = 3} p(x_i)\mathcal{L}_{i}(x) = 1 \cdot 3 + 3 \cdot -3 + 4 \cdot 1 + \dots$
$p(0) = 3$
---
### Let's play with it!
Available on [GitHub](https://github.com/lorenzogentile404/secret-sharing-suite).
```python
def compute_shares(s, n):
print('s_1,..., s_{n-1} <-$- Z_q')
print('s_n = (s - (s_1 + ... + s_{n-1})) % q')
S = [0 for i in range(0,n)]
for i in range(0, n):
if i == n - 1:
S[n-1] = (s - sum(S)) % q # s_n = s - (s_1 + ... + s_{n-1}) % q
else:
S[i] = randint(0,q-1) # s_1,...,s_{n-1}
print('s_' + str(i + 1) + ' = ' + str(S[i]))
return S
def reconstruct(S):
print('\ns_r = (s_1 + ... + s_n) % q')
s_r = sum(S) % q
print('s_r = ' + str(s_r) + ' => ' + int_to_string(s_r,len(msg)))
```
---
#### Time for questions!
:female_elf:
:email:
:mailbox_with_mail: :mailbox_with_mail: :mailbox_with_mail:
:male_elf: :male_elf: :male_elf:
Lorenzo Gentile
{"metaMigratedAt":"2023-06-15T16:56:44.055Z","metaMigratedFrom":"YAML","title":"Secret sharing","breaks":true,"description":"View the slide with \"Slide Mode\".","contributors":"[{\"id\":\"d80064c0-9b1a-4455-a2b0-11618ed627cd\",\"add\":17001,\"del\":8231}]"}