Shamir's secret sharing (SSS)
Shamir’s secret sharing (SSS) is an efficient secret sharing algorithm for distributing private information among a group, first developed by Adi Shamir in 1979.
Basics
Assume that the secret \(S\) can be represented as an element \(a_0\) of a finite field \(\mathbb{GF}(p)\) (where \(q\) is greater than the number \(n\) of shares being generated). Randomly choose \(k-1\) elements, \(a_1, \dots, a_{k-1}\), from \(\mathbb{GF}(p)\) and construct the polynomial:
\[f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{k-1} x^{k-1} \mod p\]Compute any \(n\) points on the curve, for instance, set \(i = 1, \dots, n\) to find points \((i, f(i))\) and every participant is given a point (a non-zero input to the polynomial, and the corresponding output). Given any subset of \(k\) of these pairs, \(a_0\) can be obtained using interpolation, with one possible formula for doing so being:
\[ a_0 = f(0) = \sum_{j=0}^{k-1} y_j \prod_{\substack{m=0 \\ m \neq j}}^{k-1} \frac{x_m}{x_m - x_j} \mod p \]where the list of points on the polynomial is given as \(k\) pairs of the form \((x_i, y_i)\). Note that \(f(0)\) is equal to the first coefficient of the polynomial \(f(x)\), which is our secret \(S\).
Here is the Python implementation, directly taken from Wikipedia’s page
| |
Attacks
Share forgery
Assuming the attacker has one correct share \((x_1, y_1)\), know the \(x\)-coordinates of everyone (\(x_1, x_2, \dots, x_k\)) and the secret \(S\), he can then modify his share to make the recombined secret any secret \(S'\) he wants.
To do so, he modifies his share as follows:
\[y'_1 = y_1 + (S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}\]It works because of how the secret is recovered, given the shares, using Lagrange basis polynomials. The recombination can be expressed as:
\[ S = \sum_{i=1}^k y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i} \mod p \]By including their modified share, the attacker changes this to:
\[ \left(y_1 + (S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}\right)\prod_{j=2}^{k}\frac{x_j}{x_j - x_1} + \sum_{i=2}^k y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i} \mod p \]This simplifies to :
\[(S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}\prod_{j=2}^{k}\frac{x_j}{x_j - x_1} + \sum_{i=1}^k y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i}\]which ultimately simplifies to \(S'\), our target secret.
| |
Deterministic coefficients
If the coefficients of the underlying polynomial are deterministic (i.e., predictable), then you can easily recover all the coefficients given that you know at least the first coefficient \(a_1\) (not \(a_0\), because it’s the secret we’re looking for) and the way they are generated.
Now, if you happen to know one correct share \((x, y)\) and \(k\), the number of shares needed to unlock the secret, you can recover the latter by calculating:
\[ S = y - \sum_{i=1}^{k} f(a_{i-1}) \cdot x^i \mod p \]with \(f(x)\) being an oracle that, given a coefficient, returns the next generated one.
| |
Small coefficients
If the coefficients \(a_0, a_1, \cdots, a_{k-1}\) of the polynomial are small in \(\mathbb{F}_p\), then given \(i\) shares out of the \(k\) minimum necessary to reconstruct the polynomial, one can use the LLL algorithm to recover those coefficients, and thus the secret.
Given those shares, you can write the following system of linear equations
\[ \begin{aligned} \left\{\begin{aligned} y_1 = a_0 + a_1 x_1 + a_2 x_1^2 + &\cdots + a_{k-1} x_1^{k-1} \mod p \\ y_2 = a_0 + a_1 x_2 + a_2 x_2^2 + &\cdots + a_{k-1} x_2^{k-1} \mod p \\ &\vdots \\ y_i = a_0 + a_1 x_i + a_2 x_i^2 + &\cdots + a_{k-1} x_i^{k-1} \mod p \\ \end{aligned}\right. \\ \\ \Longleftrightarrow \quad \left\{\begin{aligned} y_1 - a_0 + a_1 x_1 + a_2 x_1^2 + &\cdots + a_{k-1} x_1^{k-1} + h_1 p = 0 \\ y_2 - a_0 + a_1 x_2 + a_2 x_2^2 + &\cdots + a_{k-1} x_2^{k-1} + h_2 p = 0 \\ &\vdots \\ y_i - a_0 + a_1 x_i + a_2 x_i^2 + &\cdots + a_{k-1} x_i^{k-1} + h_i p = 0 \\ \end{aligned}\right. \\ \end{aligned} \]From those equations, we can build our base for the LLL algorithm in the form of the following block matrix :
\[ L = \left[\begin{array}{c|c} \begin{matrix} -y_1 & -y_2 & \cdots & -y_i \\ 1 & 1 & \cdots & -1 \\ x_1 & x_2 & \cdots & x_i \\ x_1^2 & x_2^2 & \cdots & x_i^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{k-1} & x_2^{k-1} & \cdots & x_i^{k-1} \\ \end{matrix} & \begin{matrix} 1 & & & & & \\ & 1 & & & & \\ & & 1 & & & \\ & & & 1 & & \\ & & & & \ddots & \\ & & & & & 1 \\ \end{matrix} \\ \hline \begin{matrix} p & & & & & \\ & p & & & & \\ & & p & & & \\ & & & \ddots & & \\ & & & & & p \\ \end{matrix} & \begin{matrix} 0 & 0 & \cdots & & & 0 \\ 0 & 0 & \cdots & & & 0 \\ \vdots & \vdots & \ddots & & & \\ \\ 0 & 0 & \cdots & & & 0\\ \end{matrix} \\ \end{array} \right] \]Then, we apply weights to this matrix to account for the size differences between the coefficients and the secret.
To do so, we multiply \(L\) by a special diagonal matrix \(W\) representing the weights, defined as:
\[ W = \begin{bmatrix} w_1 & 0 & \cdots & 0 \\ 0 & w_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \\ 0 & 0 & \cdots & w_n \\ \end{bmatrix} \]Proof
It’s because, for matrices in any dimension, the following equality holds
\[ \begin{bmatrix} a & b & \cdots & c \\ d & e & \cdots & f \\ \vdots & \vdots & \ddots & \\ g & h & \cdots & i \\ \end{bmatrix} \cdot \begin{bmatrix} w_1 & 0 & \cdots & 0 \\ 0 & w_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \\ 0 & 0 & \cdots & w_n \\ \end{bmatrix} = \begin{bmatrix} w_1 a & w_2 b & \cdots & w_n c \\ w_1 d & w_2 e & \cdots & w_n f \\ \vdots & \vdots & \ddots & \\ w_1 g & w_2 h & \cdots & w_n i \\ \end{bmatrix} \]We now have
\[ L^{'} = L \cdot W \]which, once in its reduced form, should contain the vector
\[ \begin{bmatrix} 0 \\ 0 \\ \vdots \\ S \\ a_1 \\ a_2 \\ \vdots \\ a_{k-1} \\ h \\ \end{bmatrix} \cdot W \]thus, giving the coefficients after multiplying by \(W^{-1}\)
| |