Ferkans — Interactive Telecom Tutor

Why Secret Sharing?

Suppose you want to store a cryptographic key, a medical record, or a nuclear-launch code in a way that no single server can read it, but any authorized coalition of servers can. The requirement has two sides: robustness (some servers may crash, so the secret must still be recoverable) and privacy (some servers may be compromised, so the secret must remain hidden).

Secret sharing is the information-theoretic solution to this problem. A secret $s$ is split into $n$ shares $s_1, \ldots, s_n$ with two properties: any $t$ shares reconstruct $s$ perfectly, and any $t-1$ shares reveal absolutely nothing about $s$ (not "computationally hard to guess" — literally zero mutual information).

Secret sharing is one of two pillars that support all of Parts II–V of this book (the other is network coding). The coded matrix multiplication of Chapter 5 will evaluate polynomials in exactly the same way Shamir does; the secure aggregation protocols of Chapter 10 will use additive secret sharing; ByzSecAgg (Chapter 11) uses ramp secret sharing explicitly. Spending time on Chapter 3 is the investment that makes the rest of the book readable.

Perfect Secrecy

A cryptographic guarantee that the adversary's posterior distribution on the secret equals its prior, regardless of computational power. Equivalent to $I(s; \text{view}) = 0$ . Information-theoretic, not computational.

Theorem: Perfect Secrecy Implies $|\text{share}| \geq |s|$

In any $(t, n)$ -threshold secret-sharing scheme with perfect secrecy, each share $s_k$ must have entropy at least as large as the secret itself: $H(s_k) \;\geq\; H(s), \qquad \text{for every } k = 1, \ldots, n.$ In particular, the total share alphabet has size at least $|\mathcal{S}|^n$ .

Suppose (for contradiction) some share $s_k$ had entropy less than the secret. Then by a pigeonhole / conditional-entropy argument, an authorized coalition including $s_k$ would have strictly less information than $s$ itself — contradicting correctness. The point is that perfect secrecy is expensive: each party must store at least as much data as the secret, no matter how clever the scheme. This is why ramp schemes (Section 3.4) are interesting — they relax perfect secrecy to buy smaller shares.

Proof

Apply chain rule

Let $\mathcal{U}$ be a forbidden coalition of size $t-1$ that does not contain $k$ , and let $\mathcal{T} = \mathcal{U} \cup \{k\}$ be the corresponding authorized coalition of size $t$ . Perfect secrecy gives $I(s; \{s_j : j \in \mathcal{U}\}) = 0$ .

Use correctness

Correctness gives $s$ as a deterministic function of $\{s_j : j \in \mathcal{T}\}$ , hence $H(s \mid \{s_j : j \in \mathcal{T}\}) = 0$ .

Combine

$H(s) = H(s \mid \{s_j : j \in \mathcal{U}\}) = H(s, s_k \mid \{s_j : j \in \mathcal{U}\}) - H(s_k \mid s, \{s_j : j \in \mathcal{U}\}) \leq H(s_k \mid \{s_j : j \in \mathcal{U}\}) \leq H(s_k)$ . $\blacksquare$

,

Key Takeaway

Perfect secrecy costs at least one secret-size per share. There is no free lunch: the total storage of a perfectly-secret $(t, n)$ -scheme is at least $n$ times the secret size. Ramp schemes will give up some secrecy to reduce this by a factor of $g$ — a foundational trade-off we quantify in Section 3.4.

Example: The $(n, n)$ Additive Scheme

Describe an $(n, n)$ -threshold scheme — where all $n$ parties must cooperate to reconstruct — and verify both its correctness and perfect secrecy. This scheme is used implicitly in secure aggregation (Chapter 10).

Solution

Construction

Let $s \in \mathbb{F}_q$ . Pick $n-1$ independent uniform random values $r_1, \ldots, r_{n-1} \in \mathbb{F}_q$ and set $s_1 = r_1, \quad s_2 = r_2, \quad \ldots, \quad s_{n-1} = r_{n-1}, \quad s_n = s - \sum_{k=1}^{n-1} r_k.$

Correctness

The sum of all shares is $\sum_k s_k = r_1 + r_2 + \cdots + r_{n-1} + s - \sum_{k=1}^{n-1} r_k = s$ , so any authorized coalition (the full set) reconstructs $s$ via addition.

Perfect secrecy

Any forbidden coalition of size $n - 1$ holds $n - 1$ of the shares. If they hold $s_1, \ldots, s_{n-1}$ , these are $r_1, \ldots, r_{n-1}$ — uniform and independent of $s$ . If they hold $s_n$ but not some other $s_i$ , then $s_n = s - \sum_{j \neq i} r_j - r_i$ , and since $r_i$ is uniform and independent, $s_n$ looks uniform over $\mathbb{F}_q$ — again independent of $s$ . In all cases, the coalition's view is independent of $s$ . $\blacksquare$

Application preview

This is precisely the scheme used by Bonawitz et al. in secure aggregation (Chapter 10). Users' gradients play the role of the secret, and pairwise random masks play the role of $r_k$ . The server (one "party") learns $\sum_k \mathbf{g}_k$ but no individual $\mathbf{g}_k$ .

Why We Need $t < n$

The additive $(n, n)$ scheme works only when every party is available. In practice, parties fail — servers crash, users drop out of a federated-learning round, Byzantine workers refuse to respond. The general $(t, n)$ problem — any $t$ of the $n$ parties suffice — is much harder, because the scheme must be simultaneously correct on every size- $t$ subset while leaking nothing to every size- $(t-1)$ subset. Shamir's scheme (Section 3.2) is the canonical solution; its elegance is that a single polynomial simultaneously satisfies all $\binom{n}{t}$ reconstruction constraints and all $\binom{n}{t-1}$ secrecy constraints.

Splitting a Secret Across $n$ Parties

Conceptual animation: a secret

s

is split into

n

shares via uniform random noise. Any

t

shares reconstruct

s

; any

t-1

shares reveal nothing. The pictorial intuition is that the secret sits at the intersection of

t

"curves" (polynomials, hyperplanes, ...), and fewer than

t

curves do not determine an intersection.

Common Mistake: XOR Sharing is $(n, n)$ , Not $(t, n)$

Mistake:

Treat the $(n, n)$ XOR / additive scheme as if it supported threshold reconstruction with $t < n$ .

Correction:

The additive scheme of the example above requires all $n$ shares to reconstruct. Dropping any one share destroys the secret completely (the "missing" share masks everything). For a threshold below $n$ , one must use a genuinely more sophisticated scheme — Shamir's polynomial construction (Section 3.2) or equivalent. A common implementation bug in federated-learning systems is to use XOR sharing and then discover that the protocol breaks under any user dropout.

Historical Note: Shamir and Blakley: Parallel Discovery in 1979

1979

Adi Shamir and George Blakley independently introduced $(t, n)$ -threshold secret sharing in 1979. Shamir's scheme — which we will develop in Section 3.2 — uses polynomial evaluation over a finite field and is the version that dominates modern practice. Blakley's scheme — which we treat in Section 3.3 — uses hyperplanes in a high-dimensional vector space. The two constructions are equivalent up to the field-size overhead (Shamir needs $|\mathbb{F}| > n$ ; Blakley uses a more cumbersome geometric encoding), but Blakley's geometric perspective remains valuable for intuition and for certain generalizations. Both schemes originated in the mathematics of polynomial interpolation but crystallized almost simultaneously — a classic example of two independent answers to the same underlying information-theoretic question.

,

⚠️Engineering Note

Secret Sharing in Real Systems

Modern threshold cryptography in the cloud uses secret sharing to split private keys across hardware-security modules (HSMs) run by different providers. AWS KMS with threshold ECDSA, Google Cloud Confidential Computing, and Fireblocks' MPC wallet custody all deploy Shamir-style schemes to guarantee that the loss or compromise of any single HSM does not leak the key. On the blockchain side, threshold-ECDSA wallets in major custodial platforms use $(t, n)$ -schemes with $t \in \{2, 3\}$ and $n \in \{3, 5\}$ . The pattern is: never store a cryptographic secret as a single blob; always split.

Practical Constraints

•
AWS KMS threshold ECDSA supports $(t, n) \in \{(2,3), (3,5)\}$
•
Fireblocks MPC wallets use a variant of Shamir over $\mathbb{F}_{2^{256}}$
•
Multi-region HSM deployments typically target $t = \lceil 2n/3 \rceil$ for Byzantine-fault tolerance

📋 Ref: NIST SP 800-60 (threshold cryptography roadmap)

Quick Check

Which of the following statements about a $(t, n)$ -threshold secret-sharing scheme with perfect secrecy is TRUE?

A coalition of $t-1$ parties can guess the secret with high probability.

The size of each share can be made arbitrarily small by increasing the field size.

Any $t$ parties can reconstruct the secret exactly, and any $t-1$ parties have no information about it.

The reconstruction algorithm uses the $t$ parties' shares and some public randomness shared across the whole system.

Correction:

Any

t

parties can reconstruct the secret exactly, and any

t-1

parties have no information about it.

This is exactly the definition: correctness on authorized coalitions, information-theoretic security on forbidden coalitions.

The (t,n)(t, n)(t,n)-Threshold Problem

Why Secret Sharing?

Definition: (t,n)(t, n)(t,n)-Threshold Secret-Sharing Scheme

(t,n)(t, n)(t,n)-Threshold Secret Sharing

Perfect Secrecy

Theorem: Perfect Secrecy Implies ∣share∣≥∣s∣|\text{share}| \geq |s|∣share∣≥∣s∣

Apply chain rule

Use correctness

Combine

Key Takeaway

Example: The (n,n)(n, n)(n,n) Additive Scheme

Construction

Correctness

Perfect secrecy

Application preview

Why We Need t<nt < nt<n

Splitting a Secret Across nnn Parties

Common Mistake: XOR Sharing is (n,n)(n, n)(n,n), Not (t,n)(t, n)(t,n)