Shamir's Secret Sharing and Polynomial Interpolation

This article explains how Shamir's Secret Sharing, a foundational cryptographic algorithm, utilizes the mathematical concept of polynomial interpolation to securely divide sensitive data among multiple participants. By embedding a secret into a mathematical curve, the system ensures that the original information can only be reconstructed when a predetermined minimum number of participants combine their individual shares, leaving any smaller group with zero knowledge of the secret.

The Fundamental Math: Defining a Curve

Shamir's Secret Sharing relies on a basic theorem of algebra: it takes \(k\) distinct points to uniquely define a polynomial of degree \(k - 1\).

  • Degree 1 (A straight line): You need 2 points to draw a unique straight line. With only 1 point, an infinite number of lines can pass through it.
  • Degree 2 (A parabola): You need 3 points to define a unique parabola. With only 2 points, an infinite number of parabolas can pass through them.
  • Degree \(k - 1\): You need \(k\) points to define this polynomial.

In Shamir's scheme, the number of points required to define the polynomial (\(k\)) represents the threshold of participants needed to unlock the secret. The total number of points generated (\(n\)) represents the total number of participants. This is often referred to as a \((k, n)\) threshold scheme.

Step 1: Hiding the Secret in a Polynomial

To divide a secret—which must first be converted into a number (\(S\))—among \(n\) people such that \(k\) people are required to reconstruct it, the algorithm constructs a random polynomial of degree \(k - 1\).

The general formula for this polynomial is: \(f(x) = S + a_1x + a_2x^2 + ... + a_{k-1}x^{k-1}\)

Here is how the components work:

  1. The Secret (\(S\)): The secret is placed as the constant term (the y-intercept). This means that when \(x = 0\), the value of the function \(f(0)\) is equal to the secret \(S\).
  2. Random Coefficients (\(a_1\) to \(a_{k-1}\)): The remaining \(k - 1\) numbers are chosen completely at random and kept secret during the generation process, then destroyed.

Example: Imagine the secret is the number 50, and you want to require 3 people to reconstruct it (\(k = 3\)). You need a polynomial of degree \(3 - 1 = 2\) (a parabola). You pick two random numbers for the coefficients, say 4 and 2. Your polynomial is: \(f(x) = 50 + 4x + 2x^2\).

Step 2: Generating and Distributing the Shares

Once the polynomial is established, the algorithm generates \(n\) distinct points on that curve to act as the shares.

To do this, you plug \(n\) different non-zero numbers into the variable \(x\) and calculate the resulting \(y\) value, where \(y = f(x)\). Each participant is given one \((x, y)\) coordinate pair. You can never use \(x = 0\) as a share, because \(f(0)\) is the secret itself.

Continuing the example where \(f(x) = 50 + 4x + 2x^2\), we can generate shares for 4 participants (\(n = 4\)):

  • Participant 1 (\(x = 1\)): \(f(1) = 50 + 4(1) + 2(1)^2 = 56\). Share is (1, 56).
  • Participant 2 (\(x = 2\)): \(f(2) = 50 + 4(2) + 2(2)^2 = 66\). Share is (2, 66).
  • Participant 3 (\(x = 3\)): \(f(3) = 50 + 4(3) + 2(3)^2 = 80\). Share is (3, 80).
  • Participant 4 (\(x = 4\)): \(f(4) = 50 + 4(4) + 2(4)^2 = 98\). Share is (4, 98).

Each participant now holds a valid point on the parabola, but no single point reveals the y-intercept (\(50\)).

Step 3: Reconstructing the Secret via Interpolation

To recover the secret, at least \(k\) participants must bring their \((x, y)\) coordinates together. Because \(k\) points uniquely define a polynomial of degree \(k - 1\), there is only one matching curve that passes through all of their points.

The mathematical tool used to find this curve from the given points is called Lagrange Interpolation.

Given \(k\) points: \((x_1, y_1), (x_2, y_2), ..., (x_k, y_k)\), Lagrange interpolation constructs a series of basis polynomials and sums them together to recreate the original function \(f(x)\). Because we only care about the secret (\(S\)), we do not even need to reconstruct the entire polynomial; we only need to evaluate the Lagrange interpolation formula at \(x = 0\).

In our example, if Participants 1, 2, and 4 combine their shares—(1, 56), (2, 66), and (4, 98)—the Lagrange formula processes these three coordinates, traces the unique parabola that connects them, and calculates where that parabola crosses the y-axis (\(x = 0\)). The math resolves to 50, revealing the secret.

Why Fewer Than \(k\) Shares Reveal Nothing

If only 2 participants from our example try to combine their shares—say, (1, 56) and (2, 66)—they do not have enough information to run the interpolation for a degree-2 polynomial.

Mathematically, for every possible secret value \(S'\), there is a valid parabola that passes through (0, \(S'\)), (1, 56), and (2, 66). Without the third point to lock the curve in place, the secret could literally be any number.

The Role of Finite Fields in Real-World Cryptography

In standard algebra, plotting curves with real numbers can leak hints about the secret. Because polynomial curves grow predictably toward infinity, having a few points might allow an attacker to guess the general range of the y-intercept.

To prevent this and achieve information-theoretic security, Shamir's Secret Sharing does not use standard infinite numbers. Instead, all polynomial calculations are performed using finite field arithmetic (modulo a large prime number \(P\)).

In this system, the result of \(f(x)\) is divided by \(P\), and the remainder becomes the \(y\) coordinate. This wraps the smooth curve around a finite grid, turning the predictable parabola into what looks like a random scatter of points. While the visual curve is destroyed, the algebraic rules of Lagrange interpolation still function identically, ensuring that \(k\) shares still pinpoint the exact secret, while \(k - 1\) shares yield pure mathematical noise.