Ferkans — Interactive Telecom Tutor

Why Shrink the Shares?

Section 3.1 showed that perfect secrecy in a $(t, n)$ -threshold scheme forces every share to be at least as big as the secret. That is a real cost: if we want to share a 1 GB gradient vector across $n = 100$ federated users, every user must store 1 GB of share. In federated learning, where per-user storage is at a premium, this overhead is crippling.

The ramp variant relaxes the perfect-secrecy constraint. Instead of "any $t$ reconstruct, any $t-1$ learn nothing", we demand "any $t_2$ reconstruct, any $t_1$ learn nothing" with $t_1 < t_2$ . The gap $g = t_2 - t_1$ is called the ramp width; coalitions of size between $t_1$ and $t_2$ learn a controlled, quantifiable amount about the secret. In exchange, shares become $g$ times smaller — exactly what we need for federated learning.

Ramp secret sharing is the workhorse of Chapter 11's ByzSecAgg protocol and of several CommIT-group results in later chapters. This section gives the construction and quantifies the trade-off.

,

Ramp Secret-Sharing Share Generation

Complexity:

O(n t_2)

finite-field multiplications

Input: Secret

\mathbf{s} = (s^{(1)}, \ldots, s^{(g)}) \in \mathbb{F}_q^g

, thresholds

t_1 < t_2

, number of parties

n \geq t_2

, distinct nonzero

\alpha_1, \ldots, \alpha_n

.

Output: Shares

s_1, \ldots, s_n \in \mathbb{F}_q

.

1. Draw

r_1, \ldots, r_{t_1}

independently and uniformly from

\mathbb{F}_q

.

2. Build polynomial

p(x) = \sum_{j=1}^{g} s^{(j)} \cdot L_j(x) + \sum_{j=1}^{t_1} r_j \cdot M_j(x),

where

L_j(x)

and

M_j(x)

are fixed, publicly known

degree-

(t_2 - 1)

Lagrange-like basis polynomials chosen so

that the

L_j

's encode the secret chunks and the

M_j

's add

randomness across the other coefficients.

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)

A simpler, equivalent construction is to let $p(x)$ be a degree- $(t_2 - 1)$ polynomial with $g$ of its coefficients equal to the secret chunks and the remaining $t_1$ coefficients uniform random. Reconstruction is still Lagrange interpolation.

Theorem: Ramp Rate–Security Tradeoff

The $(t_1, t_2, n)$ -ramp scheme with ramp width $g = t_2 - t_1$ satisfies

Correctness. Any $t_2$ shares reconstruct the full secret $\mathbf{s} \in \mathbb{F}_q^g$ .
Perfect secrecy below $t_1$ . Any subset of size $\leq t_1$ has $I(\mathbf{s}; \text{shares}) = 0$ .
Share rate. $|s_k| = 1$ field element, while $|\mathbf{s}| = g$ field elements. Hence $R_{\text{share}} = |s_k|/|\mathbf{s}| = 1/g$ — a $g$ -fold savings over Shamir's $R_{\text{share}} = 1$ .
Linear leakage. For coalition size $t_1 + i$ ( $1 \leq i \leq g$ ), $I(\mathbf{s}; \text{shares}) = i \cdot \log q$ bits, linear in the number of "extra" shares beyond $t_1$ .

Ramp "reuses" the same degree- $(t_2 - 1)$ polynomial to encode $g$ secrets simultaneously. The perfect-secrecy guarantee is preserved for any coalition that cannot evaluate more than $t_1$ points — those coalitions see only a $t_1$ -dimensional subspace of random variables. Once the coalition size exceeds $t_1$ , each additional share reveals one more secret chunk in a controlled fashion. The $g$ -fold savings in share size is why ramp is the scheme of choice for federated learning with large gradients.

Proof

Correctness

Same as Shamir: a degree- $(t_2 - 1)$ polynomial is uniquely determined by its values at $t_2$ distinct points, so Lagrange interpolation from any $t_2$ shares recovers the full coefficient vector, including the $g$ secret chunks.

Perfect secrecy below $t_1$

Any size- $t_1$ coalition observes $p(\alpha_{k_1}), \ldots, p(\alpha_{k_{t_1}})$ — a Vandermonde-invertible linear transformation of the $t_1$ uniform random coefficients (combined with the $g$ fixed secret chunks). The secret chunks, being fixed, do not contribute to the conditional distribution of the view, which is exactly uniform over $\mathbb{F}_q^{t_1}$ — hence independent of $\mathbf{s}$ .

Share rate

Each share is one field element; the secret is $g$ field elements. Per-share efficiency is $1/g$ of the secret size — a direct $g$ -fold savings over Shamir.

Linear leakage in the ramp

For a coalition of size $t_1 + i$ with $i \in \{1, \ldots, g\}$ , the extra $i$ shares partially determine the polynomial's coefficients. A linear-algebraic calculation shows that exactly $i$ secret chunks can be expressed as linear combinations of the observations, giving $I(\mathbf{s}; \text{shares}) = i \cdot \log q$ bits. $\blacksquare$

Ramp Secret Sharing: Rate vs. Security

Plot the share-size rate $R_{\text{share}} = 1/g$ as a function of the ramp width $g = t_2 - t_1$ , with the overlaid security guarantee $t_1 / n$ (perfect-secrecy threshold fraction). As $g$ grows, the shares shrink but perfect-secrecy tolerance ( $t_1$ ) shrinks too. The Pareto frontier is a simple hyperbola.

Parameters

n

(parties)20

t_2

(reconstruction)10

Example: Why Ramp Is the Right Choice for Federated Learning

In a federated-learning round, each user holds a gradient vector of $d = 10^6$ coordinates. We want to secret-share each user's gradient among the other $n = 100$ users, requiring perfect secrecy against any coalition of $t_1 = 30$ users and reconstructability by any $t_2 = 70$ . Compare the share size of Shamir vs. ramp.

Solution

Shamir approach

Use $(t = 31, n = 100)$ Shamir (for perfect secrecy against any 30-user coalition). Each gradient scalar requires one share per user, so each user's share is $10^6$ scalars — the full gradient size per user!

Ramp approach

Use $(t_1 = 30, t_2 = 70, n = 100)$ -ramp with $g = 40$ . Each share is $10^6 / 40 = 25\,000$ scalars, a $40\times$ savings. Perfect secrecy holds against any 30-user coalition; reconstruction still works with any 70 users; coalitions of 31–69 users learn a controlled, quantifiable amount (linear in coalition size beyond $t_1$ ).

Caveat

The ramp scheme does not provide perfect secrecy against coalitions in the ramp zone. In federated learning this is usually acceptable because (i) the server is honest-but- curious and sees no coalition of users, and (ii) realistic threat models assume $< t_1$ colluders. ByzSecAgg (Chapter 11) adds cryptographic bounds that make the ramp leakage provably small even in adversarial settings.

Ramp Leakage as Coalition Grows

Animation: a ramp scheme's mutual information between the secret and the coalition shares as coalition size grows from

0

to

n

. Flat zero below

t_1

, linear ramp from

t_1

to

t_2

, saturated at

\H(\\mathbf{s})

once

t_2

is reached.

Share Size vs. Ramp Width $g$

Explore the share-size savings of ramp over Shamir as a function of ramp width $g$ . The vertical axis is the ratio $R_{\text{share}} = 1/g$ . Adjust $t_1$ and $n$ to see how the achievable ramp width is bounded by $n - t_1$ — you cannot go beyond full-polynomial fill without losing reconstruction.

Parameters

t_1

(secrecy threshold)5

n

(parties)30

Key Takeaway

Ramp secret sharing trades graceful-degradation of secrecy for a $g$ -fold share-size savings. Set $g = 1$ and you recover Shamir with perfect secrecy; set $g$ large and shares become tiny at the cost of partial leakage in the ramp zone. The optimal operating point for federated learning is typically $g \approx n/2$ , balancing storage with realistic adversary bounds. ByzSecAgg (Chapter 11) makes this choice explicit.

Common Mistake: Ramp is NOT Perfectly Secret Beyond $t_1$

Mistake:

Use a ramp scheme and describe its security guarantee as "perfect secrecy against any coalition smaller than $t_2$ ".

Correction:

Ramp is perfectly secret only against coalitions of size $\leq t_1$ . Between $t_1$ and $t_2$ , a carefully-chosen coalition learns a linear amount of information about the secret. If the threat model includes coalitions in the ramp zone, you must either use Shamir (with its $g$ -fold storage cost) or supplement the ramp scheme with an additional cryptographic layer (as ByzSecAgg does in Chapter 11). Confusing "no reconstruction" with "perfect secrecy" is a common source of subtle bugs in FL system design.

🔧Engineering Note

Ramp in Production: ByzSecAgg's Key Primitive

ByzSecAgg (Chapter 11 of this book) is the CommIT group's Byzantine-resilient secure-aggregation protocol. It combines ramp secret sharing, coded computing for distance-based outlier detection, and vector commitments to achieve a communication complexity of $O(n \log n + B \cdot d)$ against $B$ Byzantine users — a significant improvement over the $O(n^2)$ of Bonawitz et al. The key insight is that the ramp parameters $g = t_2 - t_1$ can be chosen proportionally to $B$ , which makes the per- user share small while preserving privacy. Without the ramp generalization, ByzSecAgg's savings would be impossible.

Practical Constraints

•
ByzSecAgg uses $g = O(B)$ in the ramp construction
•
Share size scales as $d/g = d/B$ per user — much better than $d$
•
Trade-off: must accept some leakage in the ramp zone

📋 Ref: Jahani-Nezhad/Maddah-Ali/Caire 2023 IEEE J-SAIT

Historical Note: Ramp Sharing: Blakley and Meadows, Yamamoto

1984–1986

Ramp secret sharing was introduced independently by George Blakley and Catherine Meadows (Crypto 1984, published 1985) and by Hirosuke Yamamoto (IEEE T-IT 1986). Blakley and Meadows motivated ramp from a storage-efficiency angle (KGH's perfect- secrecy lower bound is too expensive for large secrets); Yamamoto gave the information-theoretic characterization of the leakage in the ramp zone and proved the capacity formulation that dominates modern treatment. The two papers are a classic illustration of the cross-pollination between cryptography and multi-user information theory that this book tries to embody.

,

Quick Check

A ramp scheme has $(t_1, t_2, n) = (10, 30, 40)$ . What is the per-share size as a fraction of the secret size?

$1/30$

$1/20$

$1/10$

$1/40$

Correction:

1/20

$R_{\text{share}} = 1/g = 1/(t_2 - t_1) = 1/20$ . Each share is $1/20$ the size of the secret — a $20\times$ savings over Shamir's $1$ .

Ramp Secret Sharing: Trading Security for Efficiency

Why Shrink the Shares?

Definition: (t1,t2,n)(t_1, t_2, n)(t1​,t2​,n)-Ramp Secret Sharing

Ramp Secret Sharing

Ramp Secret-Sharing Share Generation

Theorem: Ramp Rate–Security Tradeoff

Correctness

Perfect secrecy below $t_1$

Share rate

Linear leakage in the ramp

Ramp Secret Sharing: Rate vs. Security

Parameters

Example: Why Ramp Is the Right Choice for Federated Learning

Shamir approach

Ramp approach

Caveat

Ramp Leakage as Coalition Grows

Share Size vs. Ramp Width ggg

Parameters

Key Takeaway

Common Mistake: Ramp is NOT Perfectly Secret Beyond t1t_1t1​

Ramp in Production: ByzSecAgg's Key Primitive

Historical Note: Ramp Sharing: Blakley and Meadows, Yamamoto

Quick Check

Definition:
$(t_1, t_2, n)$ -Ramp Secret Sharing

Share Size vs. Ramp Width $g$

Common Mistake: Ramp is NOT Perfectly Secret Beyond $t_1$