Shamir's Secret Sharing (SSS)

1. What is Shamir’s Secret Sharing?

• Shamir’s Secret Sharing (SSS) is a cryptographic technique for splitting one secret into multiple shares.
• It is based on polynomial interpolation over a finite field.
• The secret is not stored directly in any individual share.
• Instead, the secret is encoded as the value of a polynomial at x = 0.

Example: 3-of-5

• Generate 5 shares.
• Any 3 shares can reconstruct the secret.
• 1 or 2 shares cannot uniquely determine the original secret.
• 4 or 5 shares can also reconstruct it.

5 total shares
        │
        ├── Share 1
        ├── Share 2
        ├── Share 3
        ├── Share 4
        └── Share 5
 
Threshold = 3
 
3 shares → Secret
2 shares → Cannot uniquely determine Secret
1 share  → Cannot uniquely determine Secret

---

2. Why do we need SSS?

• Storing one sensitive secret in one location creates a single point of failure.
• If that location is compromised, the entire secret can be compromised.
• SSS distributes control of the secret among multiple parties.

Example: protecting an encryption key

Master Encryption Key
        │
        ▼
     3-of-5 SSS
        │
 ┌──────┼──────┬──────┐
 ▼      ▼      ▼      ▼
S1     S2     S3     S4     S5

Possible distribution:

Share 1 → Security Team
Share 2 → CTO
Share 3 → Offline Vault
Share 4 → Disaster Recovery
Share 5 → CEO

• One compromised share is not enough.
• Two compromised shares are still not enough.
• Any three authorized shares can recover the key.

---

3. Threshold notation

SSS is commonly described as:

k-of-n

Where:

• k = minimum number of shares required to reconstruct the secret.
• n = total number of shares generated.

Examples

Scheme	Meaning
2-of-3	Any 2 of 3 shares recover the secret
3-of-5	Any 3 of 5 shares recover the secret
5-of-7	Any 5 of 7 shares recover the secret
10-of-15	Any 10 of 15 shares recover the secret

---

4. Core mathematical idea

SSS uses a polynomial.

For a 3-of-5 scheme, we need a polynomial of degree 2:

$$f(x)=a_0+a_{1}x+a_2{x}^2$$

The secret is stored as:

$$a_0=S$$

Therefore:

$$f(0)=S$$

So we can write:

$$f(x)=S+a_{1}x+a_2{x}^2$$

The coefficients a1 and a2 are randomly generated.

---

5. Why does a 3-of-5 scheme use a quadratic polynomial?

A polynomial of degree d requires d + 1 points to uniquely reconstruct it.

Therefore:

1-of-n → degree 0 polynomial
2-of-n → degree 1 polynomial
3-of-n → degree 2 polynomial
4-of-n → degree 3 polynomial
5-of-n → degree 4 polynomial

General rule:

$$\text{polynomial degree}=k-1$$

So:

3-of-5
   ↓
threshold = 3
   ↓
degree = 3 - 1
   ↓
degree = 2
   ↓
quadratic polynomial

---

6. Numerical example

Let’s use a small example so the mathematics is easy to see.

Suppose:

$$S=10$$

We want:

3-of-5

Choose two random coefficients:

$$a_1=4$$ $$a_2=3$$

Therefore:

$$f(x)=10+4x+3x^2$$

The secret is:

$$f(0)=10$$

---

7. Generate the shares

Evaluate the polynomial at different x values.

Share 1

$$f(1)=10+4(1)+3(1{)}^2$$ $$f(1)=17$$

Share:

(1, 17)

Share 2

$$f(2)=10+4(2)+3(2{)}^2$$ $$f(2)=30$$

Share:

(2, 30)

Share 3

$$f(3)=10+4(3)+3(3{)}^2$$ $$f(3)=49$$

Share:

(3, 49)

Share 4

$$f(4)=10+4(4)+3(4{)}^2$$ $$f(4)=74$$

Share:

(4, 74)

Share 5

$$f(5)=10+4(5)+3(5{)}^2$$ $$f(5)=105$$

Share:

(5, 105)

So the five shares are:

Share 1 → (1, 17)
Share 2 → (2, 30)
Share 3 → (3, 49)
Share 4 → (4, 74)
Share 5 → (5, 105)

---

8. What does a share actually contain?

A share is essentially a point:

$$(x,f(x))$$

For example:

(2, 30)

means:

x = 2
y = 30

It does not directly contain:

secret = 10

The secret is hidden inside the polynomial.

---

9. Reconstructing the secret

Suppose we have:

(1, 17)
(2, 30)
(3, 49)

Three points are enough to uniquely determine a quadratic polynomial.

We use Lagrange interpolation.

The general formula is:

$$f(x)=\sum _{i=1}^k{y}_i{L}_i(x)$$

where:

$$L_i(x)=\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}$$

But we only need the secret.

Since:

$$S=f(0)$$

we calculate the interpolation directly at:

$$x=0$$

---

10. Lagrange calculation

Our points are:

(x1, y1) = (1, 17)
(x2, y2) = (2, 30)
(x3, y3) = (3, 49)

Contribution from Share 1

$$L_1(0)=\frac{(0-2)(0-3)}{(1-2)(1-3)}$$ $$=\frac{6}{2}=3$$

Contribution:

$$17\times 3=51$$

Contribution from Share 2

$$L_2(0)=\frac{(0-1)(0-3)}{(2-1)(2-3)}$$ $$=\frac{3}{-1}=-3$$

Contribution:

$$30\times (-3)=-90$$

Contribution from Share 3

$$L_3(0)=\frac{(0-1)(0-2)}{(3-1)(3-2)}$$ $$=\frac{2}{2}=1$$

Contribution:

$$49\times 1=49$$

---

11. Recover the secret

Add the contributions:

$$f(0)=51-90+49$$ $$f(0)=10$$

Therefore:

$$\boxed{S=10}$$

The original secret has been recovered.

---

12. Why 2 shares are not enough

Suppose we only have:

(1, 17)
(2, 30)

There are many quadratic polynomials that can pass through those two points.

Therefore, we cannot uniquely determine:

$$f(0)$$

The important distinction is:

2 points
   ↓
many possible quadratic polynomials
   ↓
many possible secrets
   ↓
cannot determine original secret

But:

3 points
   ↓
exactly one quadratic polynomial
   ↓
f(0)
   ↓
original secret

That is the mathematical reason the threshold works.

---

13. Finite fields

The simple example above uses ordinary integer arithmetic.

Real cryptographic implementations use arithmetic inside a finite field.

A common construction is:

$$GF(p)$$

where p is a large prime.

Operations are performed modulo p.

For example, if:

$$p=17$$

then:

$$25\mathrm{mod}17=8$$

and:

$$30\mathrm{mod}17=13$$

This keeps all values inside a finite mathematical field.

---

14. Modular division

Normal division does not work directly in a finite field.

Instead:

$$\frac{a}{b}$$

becomes:

$$a\times b^{-1}(\mathrm{mod}p)$$

where:

$$b^{-1}$$

is the modular multiplicative inverse.

In Python:

inverse = pow(b, -1, PRIME)

This is used during Lagrange interpolation.

---

15. Overall SSS algorithm

Splitting

Secret
  │
  ▼
Choose random coefficients
  │
  ▼
Create polynomial
  │
  ▼
Evaluate polynomial at x=1,2,3,...
  │
  ▼
Generate shares

Mathematically:

$$f(x)=S+a_{1}x+a_2{x}^2+\cdots$$

Then:

$$Shar{e}_i=(x_i,f(x_i))$$

Reconstruction

Enough shares
      │
      ▼
Lagrange interpolation
      │
      ▼
Reconstruct polynomial
      │
      ▼
Evaluate at x=0
      │
      ▼
Secret

Because:

$$f(0)=S$$

---

16. SSS vs encryption

SSS is not encryption.

It is a secret-sharing mechanism.

Encryption

Plaintext
    │
    ▼
Encryption Key
    │
    ▼
Ciphertext

Secret Sharing

Secret
   │
   ▼
SSS
   │
   ├── Share 1
   ├── Share 2
   ├── Share 3
   ├── Share 4
   └── Share 5

SSS can be used to protect an encryption key:

AES Master Key
      │
      ▼
   3-of-5 SSS
      │
 ┌────┼────┬────┐
 ▼    ▼    ▼    ▼
S1   S2   S3   S4   S5

Later:

S1 + S3 + S5
       │
       ▼
   SSS recovery
       │
       ▼
 AES Master Key

---

17. Practical use cases

• Encryption key backup
  • Split a master key among multiple trusted parties.
• Disaster recovery
  • No single employee or machine needs to hold the complete recovery secret.
• Cryptocurrency/private-key custody
  • Distribute control of sensitive key material.
• Certificate/key management
  • Protect high-value cryptographic keys.
• Organizational access control
  • Require multiple people to participate before recovering a secret.
• Backup systems
  • Avoid a single backup location becoming a single point of failure.

---

18. Important security property

A properly implemented threshold scheme aims for:

fewer than k shares
        ↓
no useful information about the secret

while:

k or more shares
        ↓
secret can be reconstructed

This is the core security property of Shamir’s Secret Sharing.

---

19. Python implementation

The following implementation is educational. For production cryptography, use a well-reviewed, maintained implementation rather than writing your own cryptographic primitive.

Imports and finite field

from secrets import randbelow
 
 
# Large prime defining our finite field.
PRIME = 2**127 - 1

Polynomial evaluation

def eval_polynomial(coefficients, x):
    """
    Evaluate:
 
        f(x) = a0 + a1*x + a2*x^2 + ...
 
    modulo PRIME.
 
    Horner's method is used to evaluate the polynomial.
    """
 
    result = 0
 
    for coefficient in reversed(coefficients):
        result = (result * x + coefficient) % PRIME
 
    return result

Creating shares

def create_shares(secret, threshold, num_shares):
    """
    Create a k-of-n Shamir Secret Sharing scheme.
 
    Example:
 
        threshold = 3
        num_shares = 5
 
    means any 3 of the 5 shares can reconstruct the secret.
    """
 
    if threshold > num_shares:
        raise ValueError(
            "Threshold cannot exceed number of shares"
        )
 
    if not (0 <= secret < PRIME):
        raise ValueError(
            "Secret must be inside the finite field"
        )
 
    # a0 = secret
    coefficients = [secret]
 
    # Add random coefficients.
    #
    # For threshold = 3:
    #
    # f(x) = secret + a1*x + a2*x^2
    #
    for _ in range(threshold - 1):
        coefficients.append(
            randbelow(PRIME)
        )
 
    shares = []
 
    for x in range(1, num_shares + 1):
 
        y = eval_polynomial(
            coefficients,
            x
        )
 
        shares.append((x, y))
 
    return shares

Reconstructing the secret

def reconstruct_secret(shares):
    """
    Recover f(0) using Lagrange interpolation.
    """
 
    secret = 0
 
    for i, (xi, yi) in enumerate(shares):
 
        numerator = 1
        denominator = 1
 
        for j, (xj, _) in enumerate(shares):
 
            if i == j:
                continue
 
            # Numerator:
            # (0 - xj)
            numerator = (
                numerator * (-xj)
            ) % PRIME
 
            # Denominator:
            # (xi - xj)
            denominator = (
                denominator * (xi - xj)
            ) % PRIME
 
        # Modular division:
        #
        # numerator / denominator
        #
        # becomes:
        #
        # numerator * inverse(denominator)
        #
        lagrange_coefficient = (
            numerator
            * pow(
                denominator,
                -1,
                PRIME
            )
        ) % PRIME
 
        secret = (
            secret
            + yi * lagrange_coefficient
        ) % PRIME
 
    return secret

Complete example

secret = 123456789
 
# Create 5 shares.
# Any 3 shares are sufficient.
shares = create_shares(
    secret=secret,
    threshold=3,
    num_shares=5
)
 
print("Shares:")
 
for share in shares:
    print(share)
 
 
# Select any 3 shares.
selected_shares = [
    shares[0],
    shares[2],
    shares[4]
]
 
 
# Recover the secret.
recovered = reconstruct_secret(
    selected_shares
)
 
print("Original:", secret)
print("Recovered:", recovered)

Expected result:

Original: 123456789
Recovered: 123456789

The actual share values will be different each time because the polynomial coefficients are randomly generated.

---

20. Secret as bytes

Real secrets are often byte strings rather than small integers.

Convert bytes to an integer:

secret_bytes = b"my-secret"
 
secret_int = int.from_bytes(
    secret_bytes,
    byteorder="big"
)

After reconstruction:

recovered_bytes = recovered.to_bytes(
    (recovered.bit_length() + 7) // 8,
    byteorder="big"
)
 
print(recovered_bytes)

Output:

b'my-secret'

For real cryptographic keys, the field size and encoding must be chosen carefully so the entire secret fits correctly.

---

21. Complete mental model

                 SECRET
                    │
                    │
                    ▼
           f(0) = SECRET
                    │
                    ▼
       ┌──────────────────────┐
       │ Random Polynomial    │
       │                      │
       │ f(x) = S + a1*x      │
       │          + a2*x² ... │
       └──────────────────────┘
                    │
          Evaluate at x values
                    │
       ┌────────────┼────────────┐
       ▼            ▼            ▼
   (1, f(1))    (2, f(2))    (3, f(3)) ...
       │            │            │
       ▼            ▼            ▼
    Share 1      Share 2      Share 3
       │            │            │
       └────────────┼────────────┘
                    │
              k shares needed
                    │
                    ▼
          Lagrange Interpolation
                    │
                    ▼
                  f(0)
                    │
                    ▼
                 SECRET

---

22. Key points to remember

• SSS = Shamir’s Secret Sharing.
• It splits one secret into n shares.
• A threshold k determines how many shares are required.
• It uses a polynomial of degree k - 1.
• The secret is stored as:

$$f(0)=S$$

• Each share is a point:

$$(x_i,f(x_i))$$

• Lagrange interpolation reconstructs the polynomial.
• Reconstruction evaluates the polynomial at x = 0.
• Fewer than k shares cannot uniquely determine the secret.
• Real implementations use finite-field arithmetic.
• SSS itself is not encryption.
• SSS can be used to distribute or protect encryption keys.
• The educational Python implementation above demonstrates the mathematics but should not be treated as production cryptographic software.