< / >

Shamir's secret sharing

October 26, 2023

@trizin

Have you ever wanted to split a precious secret, ensuring only a specific group could piece it back together?

Welcome to the world of Shamir's Secret Sharing, a powerful algorithm that's not just secure, but information-theoretically so. This means no quantum computer, nor any future technological marvel, can crack it. With Shamir's method, you can choose how many pieces (or 'shares') a secret is divided into and how many of those pieces are needed to reconstruct the original information. When the right number of shares come together, the secret is unveiled.

Why makes it so powerful?

At its core, SSS is based on polynomial interpolation in finite fields. The secret is represented as a point on a polynomial, and to reconstruct that secret, you need a certain number of other points (or shares). If you have fewer shares than required, the information from those shares doesn't give you any meaningful insight into the actual secret. This is not just a computational limitation-it's a fundamental property, meaning that even with infinite computational power (like a quantum computer), you can't derive the secret from insufficient shares.

How it works?

Let's say Alice has a secret number "42" and she'd like to share this secret among five of her friends, but she wants to ensure that only when two or more of them come together can they reconstruct the secret.

Choosing a Polynomial

Alice needs a polynomial of degree 1, one less than the threshold of 2. This polynomial has two coefficients: the secret number itself and a randomly chosen number. Let's say Alice picks the random number as 3. So, the polynomial Alice formulates is:

f(x)=3x+42f(x) = 3x+42

Generating Shares

Right now Alice has to generate 5 shares, to do that Alice, for 5 of her friends, can input 1..5 into the polynomial and share the results with corresponding friends:

  1. f(1)=45f(1)=45
  2. f(2)=48f(2)=48
  3. f(3)=51f(3)=51
  4. f(4)=54f(4)=54
  5. f(5)=57f(5)=57

As you can see, having one of the shares does not give you any information (1, 45).

Reconstructing the Secret

For demonstration, let's say two friends, holding shares (2, 48) and (5, 57), decide to join forces. Using these points, they can determine the polynomial:

Using the formula a line y=mx+cy = mx + c and two points (shares):

y−y2x−x2=y2−y1x2−x1y−57x−5=57−485−2y−57x−5=93y−57=3x−15y−42=3xy=3x+42\begin{aligned} \frac{y-y_2}{x-x_2} &= \frac{y_2-y_1}{x_2-x_1} \\ \frac{y-57}{x-5} &= \frac{57-48}{5-2} \\ \frac{y-57}{x-5} &= \frac{9}{3} \\ y - 57 &= 3x - 15 \\ y - 42 &= 3x \\ y &= 3x + 42 \\ \end{aligned}

This reveals the secret coefficient, 3, and the secret number, 42.

Threshold of 3

Alice still wishes to share her secret number "42" with her five friends, but this time, she wants a minimum of three of them to collaborate to uncover the secret.

Choosing a Polynomial

Alice needs a polynomial of degree 2, one less than the threshold of 3. Let's say the random coefficients are 5 and 3:

f(x)=5x2+3x+42f(x) = 5x^2+3x+42

Generating Shares

For each of her five friends, Alice computes the polynomial with values 1 through 5:

  1. f(1)=5(12)+3(1)+42=50f(1)=5(1^2)+3(1)+42=50
  2. f(2)=5(22)+3(2)+42=68f(2)=5(2^2)+3(2)+42=68
  3. f(3)=5(32)+3(3)+42=96f(3)=5(3^2)+3(3)+42=96
  4. f(4)=5(42)+3(4)+42=134f(4)=5(4^2)+3(4)+42=134
  5. f(5)=5(52)+3(5)+42=182f(5)=5(5^2)+3(5)+42=182

Note that a single share or even two shares do not provide any information about the secret.

Reconstructing the Secret

To uncover the secret, any three friends must pool their shares. For instance, suppose the friends with shares (1, 50), (3, 96), and (5, 182) decide to collaborate.

To determine the polynomial f(x)f(x), we'll use Lagrange's interpolation formula:

f(x)=∑i=1nyi×Li(x)f(x) = \sum_{i=1}^{n} y_i \times L_i(x)

where Li(x)L_i(x) is the Lagrange basis polynomial, given by:

Li(x)=∏1≤j≤n,j≠ix−xjxi−xjL_i(x) = \prod_{1 \leq j \leq n, j \neq i} \frac{x - x_j}{x_i - x_j}

Given our points:

(x1,y1)=(1,50)(x2,y2)=(3,96)(x3,y3)=(5,182)\begin{aligned} (x_1, y_1) &= (1, 50) \\ (x_2, y_2) &= (3, 96) \\ (x_3, y_3) &= (5, 182) \\ \end{aligned}

We compute the Lagrange basis polynomials:

L1(x)=(x−x2)(x−x3)(x1−x2)(x1−x3)L2(x)=(x−x1)(x−x3)(x2−x1)(x2−x3)L3(x)=(x−x1)(x−x2)(x3−x1)(x3−x2)\begin{aligned} L_1(x) &= \frac{(x - x_2)(x - x_3)}{(x_1 - x_2)(x_1 - x_3)} \\ L_2(x) &= \frac{(x - x_1)(x - x_3)}{(x_2 - x_1)(x_2 - x_3)} \\ L_3(x) &= \frac{(x - x_1)(x - x_2)}{(x_3 - x_1)(x_3 - x_2)} \\ \end{aligned}

Substitute in the known x-values to get:

L1(x)=(x−3)(x−5)(1−3)(1−5)L2(x)=(x−1)(x−5)(3−1)(3−5)L3(x)=(x−1)(x−3)(5−1)(5−3)\begin{aligned} L_1(x) &= \frac{(x - 3)(x - 5)}{(1 - 3)(1 - 5)} \\ L_2(x) &= \frac{(x - 1)(x - 5)}{(3 - 1)(3 - 5)} \\ L_3(x) &= \frac{(x - 1)(x - 3)}{(5 - 1)(5 - 3)} \\ \end{aligned}

This gives:

L1(x)=x2−8x+158L2(x)=−x2+6x−54L3(x)=x2−4x+38\begin{aligned} L_1(x) &= \frac{x^2-8x+15}{8} \\ L_2(x) &= \frac{-x^2+6x-5}{4} \\ L_3(x) &= \frac{x^2-4x+3}{8} \\ \end{aligned}

Now, using the formula for f(x)f(x):

f(x)=y1×L1(x)+y2×L2(x)+y3×L3(x)f(x) = y_1 \times L_1(x) + y_2 \times L_2(x) + y_3 \times L_3(x)

Substitute in the y-values:

f(x)=50(x2−8x+158)+96(−x2+6x−54)+182(x2−4x+38)f(x) = 50(\frac{x^2-8x+15}{8}) + 96(\frac{-x^2+6x-5}{4}) + 182(\frac{x^2-4x+3}{8})

Combine like terms:

f(x)=5x2+3x+42f(x) = 5x^2+3x+42

And that's the reconstructed polynomial, which reveals the secret "42".

Conclusion

Shamir's Secret Sharing is a remarkable algorithm that stands at the intersection of mathematics and cryptography. With its robust information-theoretic security, it promises resistance against even the most advanced computational technologies like quantum computers.

The beauty of the algorithm lies in its simplicity and elegance; by transforming a secret into a polynomial and sharing distinct points of that polynomial, one can ensure that only a collaborative effort of a predetermined number of participants can uncover the hidden secret.