Ferkans — Interactive Telecom Tutor

Polynomials Are the Right Tool

Why polynomials? Because a polynomial of degree $t-1$ is uniquely determined by its values at any $t$ distinct points and is completely unconstrained by its values at any $t - 1$ points. This single algebraic fact delivers both correctness (any $t$ evaluations interpolate back to $p(0) = s$ ) and perfect secrecy (any $t-1$ evaluations are statistically indistinguishable from random, for any fixed $s$ ). Shamir's 1979 insight was that this two-for-one gift is exactly what secret sharing needs.

The construction takes two lines to state and four to implement. The result is the canonical information-theoretic threshold cryptography.

Shamir Share Generation

Complexity:

O(nt)

finite-field multiplications

Input: Secret

s \in \mathbb{F}_q

, threshold

t

, number of

parties

n \leq q - 1

, distinct nonzero evaluation points

\alpha_1, \ldots, \alpha_n \in \mathbb{F}_q^*

.

Output: Shares

s_1, \ldots, s_n

for the

n

parties.

1. Draw

r_1, \ldots, r_{t-1}

independently and uniformly from

\mathbb{F}_q

.

2. Define the polynomial

p(x) = s + r_1 x + r_2 x^2 + \cdots + r_{t-1} x^{t-1}

.

3. for

k = 1, 2, \ldots, n

do

4.

\quad s_k \leftarrow p(\alpha_k)

5. end for

6. return

(s_1, s_2, \ldots, s_n)

The polynomial $p$ is constructed with $p(0) = s$ so that the secret is recoverable at $x = 0$ . Each party $k$ is assigned a fixed distinct evaluation point $\alpha_k \neq 0$ ; the mapping $k \mapsto \alpha_k$ is public, while the coefficients $r_1, \ldots, r_{t-1}$ are freshly random per share.

Shamir Reconstruction via Lagrange Interpolation

Complexity:

O(t^2)

finite-field operations, or

O(t \log^2 t)

with FFTs

Input: Any

t

shares

\{(\alpha_k, s_k) : k \in \mathcal{T}\}

where

|\mathcal{T}| = t

.

Output: The secret

s

.

1. for each

k \in \mathcal{T}

do

2.

\quad \ell_k(0) \leftarrow \prod_{j \in \mathcal{T}, j \neq k} \dfrac{0 - \alpha_j}{\alpha_k - \alpha_j} = \prod_{j \neq k} \dfrac{-\alpha_j}{\alpha_k - \alpha_j}

3. end for

4.

s \leftarrow \displaystyle\sum_{k \in \mathcal{T}} s_k \cdot \ell_k(0)

5. return

s

The Lagrange basis polynomials $\ell_k$ evaluated at $x = 0$ give the interpolation coefficients. Every coalition of size $t$ uses its own $\alpha_k$ 's to compute its own $\ell_k(0)$ 's — the reconstruction formula works over all size- $t$ subsets.

Theorem: Shamir's $(t, n)$ -Threshold: Correctness and Perfect Secrecy

For every prime power $q > n$ and distinct nonzero $\alpha_1, \ldots, \alpha_n \in \mathbb{F}_q^*$ , Shamir's scheme (Algorithms 3.1, 3.2) is a perfect $(t, n)$ -threshold secret-sharing scheme over $\mathbb{F}_q$ :

Correctness. For every secret $s \in \mathbb{F}_q$ and every $\mathcal{T} \subseteq \{1, \ldots, n\}$ with $|\mathcal{T}| = t$ , Lagrange interpolation on $\{(\alpha_k, s_k) : k \in \mathcal{T}\}$ recovers $p(0) = s$ exactly.
Perfect secrecy. For every forbidden coalition $\mathcal{U}$ with $|\mathcal{U}| \leq t - 1$ and every secret value $\tilde s \in \mathbb{F}_q$ , $\Pr[\text{shares of } \mathcal{U} \mid s = \tilde s]$ is uniform over $\mathbb{F}_q^{|\mathcal{U}|}$ ; equivalently, $I(s; \{s_k : k \in \mathcal{U}\}) = 0$ .

A polynomial of degree $t-1$ has $t$ free parameters (the coefficients $s, r_1, \ldots, r_{t-1}$ ). Specifying $t$ evaluations completely determines the polynomial; specifying fewer than $t$ leaves at least one free parameter, and the randomness of the $r_i$ 's ensures that free parameter is uniform. This is the information-theoretic heart of the scheme.

Proof

Correctness: $p$ has degree $\leq t-1$

A degree- $(t-1)$ polynomial is uniquely determined by its values at any $t$ distinct points. The Lagrange interpolation formula evaluated at $0$ gives $p(0) = s$ exactly. Hence any authorized $\mathcal{T}$ reconstructs correctly.

Perfect secrecy: set up

Fix a forbidden coalition $\mathcal{U} = \{k_1, \ldots, k_m\}$ with $m \leq t - 1$ . We show that for any candidate secret value $\tilde s \in \mathbb{F}_q$ , the coalition's view $(s_{k_1}, \ldots, s_{k_m})$ is uniform over $\mathbb{F}_q^m$ , hence independent of $s$ .

Perfect secrecy: uniform shares

The coalition's shares are $s_{k_i} = p(\alpha_{k_i}) = \tilde s + \sum_{j=1}^{t-1} r_j \alpha_{k_i}^j$ . This is a linear transformation of the uniformly random vector $(r_1, \ldots, r_{t-1}) \in \mathbb{F}_q^{t-1}$ plus the constant $\tilde s$ . The matrix of this transformation has rows $(\alpha_{k_i}, \alpha_{k_i}^2, \ldots, \alpha_{k_i}^{t-1})$ ; since $m \leq t-1$ and the $\alpha_{k_i}$ are distinct nonzero elements of $\mathbb{F}_q$ , this is a Vandermonde-like matrix of full row rank $m$ .

Perfect secrecy: finish

A full-row-rank linear transformation of a uniform random vector is itself uniform over the image. Hence the coalition's view is uniform over $\mathbb{F}_q^m$ , independent of the secret $\tilde s$ . This holds for every $\tilde s$ ; therefore $I(s; \{s_k : k \in \mathcal{U}\}) = 0$ . $\blacksquare$

Example: Shamir Over $\mathbb{F}_7$ : $(2, 3)$ -Threshold

Share secret $s = 5$ among 3 parties (evaluation points $\alpha_1 = 1, \alpha_2 = 2, \alpha_3 = 3$ ) with threshold $t = 2$ over $\mathbb{F}_7$ , using random coefficient $r_1 = 4$ . Verify that any two shares reconstruct the secret, and that one share reveals nothing.

Solution

Build the polynomial

$p(x) = 5 + 4x$ over $\mathbb{F}_7$ .

Compute shares

$s_1 = p(1) = 5 + 4 = 9 \equiv 2 \pmod 7.$ $s_2 = p(2) = 5 + 8 = 13 \equiv 6 \pmod 7.$ $s_3 = p(3) = 5 + 12 = 17 \equiv 3 \pmod 7.$

Reconstruct from shares 1 and 2

Lagrange basis at $x = 0$ : $\ell_1(0) = (0-2)/(1-2) = -2/-1 = 2$ . $\ell_2(0) = (0-1)/(2-1) = -1/1 = -1 \equiv 6 \pmod 7$ . $s = s_1 \ell_1(0) + s_2 \ell_2(0) = 2 \cdot 2 + 6 \cdot 6 = 4 + 36 = 40 \equiv 5 \pmod 7.$ ✓

Reconstruct from shares 2 and 3

Lagrange basis at $x = 0$ : $\ell_2(0) = (0-3)/(2-3) = -3/-1 = 3$ . $\ell_3(0) = (0-2)/(3-2) = -2/1 = -2 \equiv 5 \pmod 7$ . $s = s_2 \ell_2(0) + s_3 \ell_3(0) = 6 \cdot 3 + 3 \cdot 5 = 18 + 15 = 33 \equiv 5 \pmod 7.$ ✓ Same secret, confirming that the answer does not depend on which two shares we use.

One share reveals nothing

A single share — say $s_1 = 2$ — is consistent with every possible secret $\tilde s \in \mathbb{F}_7$ under a suitable random $r_1$ : for each $\tilde s$ there is a unique $\tilde r_1$ such that $\tilde s + \tilde r_1 \cdot 1 = 2$ . Since $r_1$ was uniform, the seven candidate secrets are equally likely given $s_1$ . Perfect secrecy confirmed.

Shamir Polynomial Evaluation

Plot a degree- $(t-1)$ polynomial over the reals to visualize Shamir's scheme. The secret is $p(0)$ ; the shares are $p(\alpha_1), p(\alpha_2), \ldots, p(\alpha_n)$ . Move the slider to see how any $t$ of the $n$ points uniquely determine the curve, but fewer than $t$ points leave infinitely many candidate curves — each passing through the known points but hitting a different value at $x = 0$ .

Parameters

t

(threshold)3

Polynomial degree = $t - 1$

n

(shares)5

Number of parties

Secret

s

2

Polynomial value at $x = 0$

Shamir: From Shares to Polynomial to Secret

Animated sequence: (1) a random polynomial of degree

t - 1

is drawn with the secret at

x = 0

; (2)

n

evaluation points are highlighted; (3) any

t

of them determine the polynomial and hence the secret; (4) any

t - 1

leave infinitely many curves consistent with those points, visualizing perfect secrecy.

Shamir Threshold Explorer

Adjust $t$ (threshold) and $n$ (number of shares) and see the security / robustness trade-off. The plot shows: (top) share values as a function of the polynomial; (bottom) the number of "consistent secrets" given a forbidden coalition of size $t - 1$ — which equals $q$ (the field size) because every secret is equally likely. Changing $t$ changes the polynomial's shape but not the information-theoretic security guarantee.

Parameters

t

(threshold)3

n

(parties)6

q

(field size)31

Reconstruction Cost at Scale

Naive Lagrange interpolation runs in $O(t^2)$ field operations. For $t$ on the order of a few thousand — the regime of ByzSecAgg in Chapter 11 — this becomes noticeable. The standard optimization is to compute the $\ell_k(0)$ coefficients via FFT over the evaluation points, bringing the cost to $O(t \log^2 t)$ . Practical implementations (PyTorch / C++ MPC libraries) achieve this with modest constant factors on modern hardware. For the purpose of this book, treat reconstruction as cheap relative to the per-round training compute.

Common Mistake: Evaluation Points Must Be Distinct and Nonzero

Mistake:

Assign party $1$ evaluation point $\alpha_1 = 0$ (maybe "to save field elements").

Correction:

Party $1$ 's share would then equal the secret: $s_1 = p(0) = s$ . One share would suffice to reconstruct, ruining the threshold structure. Always use distinct nonzero evaluation points — typically $\alpha_k = k$ for $k = 1, \ldots, n$ when $n < q$ .

Common Mistake: Field Size Must Exceed $n$

Mistake:

Use $q \leq n$ (e.g., $q = 2$ when $n = 5$ ).

Correction:

There are only $q - 1$ nonzero elements in $\mathbb{F}_q$ , so at most $q - 1$ distinct evaluation points. If $n \geq q$ then two parties must share the same $\alpha$ , breaking the construction. Practical Shamir implementations use $\mathbb{F}_{2^k}$ for large $k$ — e.g., $\mathbb{F}_{2^{256}}$ in modern MPC wallets — giving ample room.

⚠️Engineering Note

Shamir in MPC Wallet Systems

Production MPC (multi-party computation) wallet systems such as Fireblocks, ZenGo, and Unbound Tech all use Shamir's scheme as a building block. The typical deployment uses $(t, n) = (3, 5)$ over $\mathbb{F}_{2^{256}}$ , with shares stored in geographically distributed HSMs owned by independent trust zones. The pattern is: never store a private key as a single blob; reconstruct on demand from $t$ shares and discard. Modern threshold-signature protocols (GG18, CMP21) build on this foundation to sign ECDSA transactions without ever reconstructing the private key at all — a stronger guarantee that blends Shamir with coded computing (Chapter 5).

Practical Constraints

•
Fireblocks MPC: $(t, n) = (3, 5)$ , field $\mathbb{F}_{2^{256}}$ , per-signature cost $\sim$ 50 ms
•
Lightweight implementations use $\mathbb{F}_{2^{64}}$ for IoT
•
Practical $t$ values rarely exceed 10 due to latency budgets in consumer products

📋 Ref: NIST SP 800-186 (threshold crypto); MPC Wallet Alliance specs

Why This Matters: The Same Polynomial Trick Appears Again in Chapter 5

Chapter 5 develops polynomial codes for distributed matrix multiplication. The construction is virtually identical to Shamir's: each worker is assigned an evaluation point, the master encodes data-dependent polynomials, and recovery from any $K$ responses uses the same Lagrange interpolation. The difference is that Shamir's polynomial has random coefficients (for privacy), while the polynomial-code polynomial has data-dependent coefficients (for correctness). Recognizing this structural kinship is the key to seeing why Chapter 5 calls coded computing "Shamir's polynomial plus linear structure".

🎓CommIT Contribution(2021)

Group Contributions Building on Shamir Secret Sharing

K. Wan, D. Tuninetti, G. Caire — IEEE International Symposium on Information Theory (ISIT)

Several CommIT group results build directly on Shamir's secret- sharing primitive introduced in this section. The Wan–Tuninetti–Caire coded-shuffling framework (Chapter 7) uses a Shamir-style polynomial evaluation for the coded message construction. The Jahani-Nezhad / Maddah-Ali / Caire ByzSecAgg result (Chapter 11) relies on ramp secret sharing — the generalization introduced in Section 3.4. Both families of results illustrate that secret sharing is not a historical curiosity but an active tool in modern distributed-computing research.

secret-sharingcoded-shufflingcommit-foundation

Quick Check

In a Shamir $(5, 8)$ -scheme, what is the degree of the underlying polynomial $p(x)$ ?

$4$

$5$

$7$

$8$

Correction:

4

The polynomial has degree $t - 1 = 4$ — exactly enough so that $t = 5$ evaluations determine it, but $t - 1 = 4$ evaluations do not.

Shamir's Secret Sharing

Polynomials Are the Right Tool

Shamir Share Generation

Shamir Reconstruction via Lagrange Interpolation

Theorem: Shamir's (t,n)(t, n)(t,n)-Threshold: Correctness and Perfect Secrecy

Correctness: $p$ has degree $\leq t-1$

Perfect secrecy: set up

Perfect secrecy: uniform shares

Perfect secrecy: finish

Example: Shamir Over F7\mathbb{F}_7F7​: (2,3)(2, 3)(2,3)-Threshold

Build the polynomial

Compute shares

Reconstruct from shares 1 and 2

Reconstruct from shares 2 and 3

One share reveals nothing

Shamir Polynomial Evaluation

Parameters

Shamir: From Shares to Polynomial to Secret

Shamir Threshold Explorer

Parameters

Reconstruction Cost at Scale

Common Mistake: Evaluation Points Must Be Distinct and Nonzero

Common Mistake: Field Size Must Exceed nnn

Shamir in MPC Wallet Systems

Why This Matters: The Same Polynomial Trick Appears Again in Chapter 5

Group Contributions Building on Shamir Secret Sharing

Quick Check

Theorem: Shamir's $(t, n)$ -Threshold: Correctness and Perfect Secrecy

Example: Shamir Over $\mathbb{F}_7$ : $(2, 3)$ -Threshold

Common Mistake: Field Size Must Exceed $n$