Exercises

Split secret $s \in \mathcal{S}$ among $n$ parties with Share and Reconstruct algorithms such that: (1) any $t$ parties reconstruct $s$ exactly; (2) any $\leq t - 1$ parties learn nothing about $s$.

$I(s; \{s_k : k \in \mathcal{U}\}) = 0$ for every forbidden coalition $\mathcal{U}$. Equivalently, the conditional distribution of the coalition's view given any candidate secret equals the marginal distribution of the view.

$\deg p(x) = t - 1$.

A degree-$(t-1)$ polynomial has $t$ free coefficients and is uniquely determined by $t$ evaluations (Lagrange). Fewer than $t$ evaluations leave at least one free parameter — information-theoretically unrecoverable — which gives the secret-sharing perfect-secrecy guarantee.

$p(x) = 7 + 3x$ over $\mathbb{F}_{11}$.

$s_1 = p(1) = 7 + 3 = 10$; $s_2 = p(2) = 7 + 6 = 13 \equiv 2 \pmod{11}$; $s_3 = p(4) = 7 + 12 = 19 \equiv 8 \pmod{11}$.

$g = t_2 - t_1 = 15 - 5 = 10$.

$R_{\text{share}} = 1/g = 1/10$. Each share is one-tenth the size of the secret — a $10\times$ savings over Shamir.

$\ell_1(0) = (0 - 2)/(1 - 2) = 2$; $\ell_2(0) = (0 - 1)/(2 - 1) = -1 \equiv 10 \pmod{11}$. $s = 10 \cdot 2 + 2 \cdot 10 = 20 + 20 = 40 \equiv 7 \pmod{11}$. ✓

A single share $s_1 = 10$ satisfies $10 = 7 + 3 \cdot 1$ over $\mathbb{F}_{11}$, but equally well $10 = \tilde s + \tilde r \cdot 1$ for any $\tilde s \in \mathbb{F}_{11}$ with the appropriate $\tilde r$. Since $\tilde r$ was chosen uniformly, all 11 candidate secrets are equally likely.

$s_k = p(\alpha_k), s_k' = p'(\alpha_k)$. Then $s_k + s_k' = p(\alpha_k) + p'(\alpha_k) = (p + p')(\alpha_k)$, and $(p + p')(0) = p(0) + p'(0) = s + s'$. So $\{s_k + s_k' : k\}$ are Shamir shares of $s + s'$.

Linear secret sharing permits local addition of shares without communication — a central requirement of efficient secure multi-party computation. Each party can compute its own share of a sum by adding locally-held shares, with no interaction. This is the foundation of the BGW protocol (Ben-Or–Goldwasser–Wigderson) for MPC and extends to scalar multiplication similarly.

If the coalition's view is within TV distance $\epsilon$ of uniform, then by Pinsker's inequality $I(s; \text{view}) \leq h(\epsilon)$ bits. The best adversary can guess the secret with probability $\Pr[\text{correct}] \leq 1/|\mathcal{S}| + \epsilon$.

Retracing the proof of Theorem (Share-Entropy Bound, §3.1) with the statistical-secrecy inequality replacing perfect-secrecy, the bound $H(s_k) \geq H(s)$ is relaxed to $H(s_k) \geq H(s) - h(\epsilon)$.

For cryptographic-grade $\epsilon = 2^{-80}$, $h(\epsilon)$ is negligible, so the bound is essentially unchanged. Statistical secrecy is therefore not a useful relaxation for reducing share sizes — this is the reason ramp schemes chose a different relaxation (controlled leakage) instead.

Let $p(x) = 4 + 3x + 5x^2$ over $\mathbb{F}_7$. Here the two secret chunks are the $x^0$ and $x^2$ coefficients; the $x^1$ coefficient $r_1 = 3$ is uniform random.

With $\alpha_1 = 1, \alpha_2 = 2, \alpha_3 = 3$: $s_1 = 4 + 3 + 5 = 12 \equiv 5 \pmod 7$; $s_2 = 4 + 6 + 20 = 30 \equiv 2 \pmod 7$; $s_3 = 4 + 9 + 45 = 58 \equiv 2 \pmod 7$.

All three shares determine the degree-2 polynomial by Vandermonde interpolation — the $(4, 5)$ chunks appear as the $x^0$ and $x^2$ coefficients once $p$ is recovered.

A single share $s_k = 4 + 3\alpha_k + 5\alpha_k^2$ fixes one linear constraint on the three unknowns $(s^{(1)}, r_1, s^{(2)})$, leaving a 2-dimensional uniform distribution — so both secret chunks are uniform given one share. Perfect secrecy against $t_1 = 1$.

$p(x) = s + r_1 x$ over $\mathbb{F}_{11}$. Each share is one field element $s_k = p(\alpha_k)$. Per-share storage: $\log_2 11 \approx 3.5$ bits.

Choose the point $\mathbf{p} = (s, p_2) \in \mathbb{F}_{11}^2$ with $p_2$ uniform. Each party's hyperplane is a line in $\mathbb{F}_{11}^2$ passing through $\mathbf{p}$ — equation $\mathbf{a}_k^\top \mathbf{x} = b_k$, i.e., a pair $(\mathbf{a}_k, b_k)$ of three field elements (two for the normal, one for the offset; one can be absorbed). Per-share storage: roughly $2 \log_2 11 \approx 7$ bits — double Shamir's.

Both schemes guarantee perfect $(2, 3)$-secrecy against one colluder.

Secret $s = \sum_{k=1}^n s_k$ over $\mathbb{F}_q$, where $s_1, \ldots, s_{n-1}$ are uniform and independent and $s_n = s - \sum_{k < n} s_k$.

Given $s_1, \ldots, s_{n-1}$, the missing $s_n = s - \sum s_k$ is the only unknown. Since $s_n$ is uniform (as a function of the random $s_1, \ldots, s_{n-1}$ given any candidate $s$), the conditional distribution of $s$ given $s_1, \ldots, s_{n-1}$ is uniform.

All $n$ shares are needed; one missing share makes the secret completely unrecoverable. This is exactly the guarantee secure aggregation relies on in Chapter 10: as long as one user holds its share privately, the server learns nothing.

If $s_k = p(\alpha_k)$ with $p(0) = s$, then $c \cdot s_k = c \cdot p(\alpha_k) = (c p)(\alpha_k)$, and $(c p)(0) = c \cdot s$. The polynomial $c p$ still has degree $t - 1$, so the threshold is preserved.

Combined with linear-addition (Exercise 6), scalar multiplication gives us non-interactive computation of linear functions on secret-shared data. Every party locally computes its share of $a \cdot s_1 + b \cdot s_2$ without communication. This is the foundation of the BGW protocol for MPC on arithmetic circuits.

If $s_k = p(\alpha_k)$ and $s_k' = q(\alpha_k)$ with $\deg p = \deg q = t - 1$, then $s_k \cdot s_k' = (pq)(\alpha_k)$ is a share of a polynomial of degree $2(t - 1)$. Reconstructing $pq$ requires $2t - 1$ shares, not $t$ — the threshold has inflated.

Each party $k$ Shamir-shares its local product $s_k s_k'$ among the $n$ parties using a fresh degree-$(t - 1)$ polynomial $r_k(x)$ with $r_k(0) = s_k s_k'$. Party $j$ then sums its received shares $\sum_k c_k r_k(\alpha_j)$ using the Lagrange interpolation coefficients $c_k = \ell_k(0)$. The result is a share of $\sum_k c_k s_k s_k' = (pq)(0) = ab$ in a degree-$(t - 1)$ polynomial. Threshold restored.

The re-sharing step requires one round of communication (each party sends $n$ shares). This is where the "interaction" in MPC comes from — linear operations are local, but multiplication requires a round.

A $(t, n)$-Shamir scheme is a Reed-Solomon code with minimum distance $d = n - t + 1$. Error detection requires $d > e$, i.e., $e < n - t + 1$. Each extra unit of detection capability costs a reduction in the reconstruction threshold — or, equivalently, extra share size for a given $t$.

A verifiable secret-sharing scheme (Chor-Goldwasser-Micali- Awerbuch 1985, Ben-Or-Goldwasser-Wigderson 1988) adds $O(\log n)$ authentication bits per share for detection, giving the stated bound. The precise constants depend on the verifiable-secret-sharing construction chosen.

Chapter 11 of this book uses verifiable secret sharing (via vector commitments) as a primitive for Byzantine- resilient aggregation, adding exactly this $\log n$ bit overhead per share.

A coalition of size $t_1 + i$ views $t_1 + i$ shares, each being $p(\alpha_k)$ for a polynomial with $t_1$ uniform coefficients and $g$ fixed (secret) coefficients. After accounting for the $t_1$ random degrees of freedom, the remaining information is about the secret. Linear algebra over the Vandermonde matrix shows this to be exactly $i$ out of $g$ independent scalars of the secret, i.e., $i \cdot \log q$ bits.

$I(\mathbf{s}; \text{coalition}) = i \cdot \log q = (i/g) \cdot g \log q = (i/g) \cdot H(\mathbf{s})$.

At $i = g$ (coalition size $t_2$), all $g$ secret chunks are recoverable, so $I(\mathbf{s}; \text{coalition}) = H(\mathbf{s})$. The leakage grows linearly in the coalition size beyond $t_1$ and saturates at $t_2$, matching the statement of Theorem 3.4.1.

To tolerate $d$ dropouts we need $t_2 \leq n - d$; to guarantee perfect secrecy against any $c$-sized collusion we need $t_1 \geq c$. Choose $t_1 = c$ and $t_2 = n - d$. Ramp width $g = n - d - c$.

Each gradient coordinate produces one share per user, but with ramp the share is $d_{\text{model}} / g$ scalars. Total upload per user: $d_{\text{model}} / g$.

Server collects $t_2$ shares and reconstructs the aggregate via Lagrange interpolation. Total download $= t_2 \cdot d_{\text{model}} / g = d_{\text{model}}$ (the reconstruction makes up for the compression).

Bonawitz et al.'s pairwise masking is essentially a $g = 1$ variant (no compression), with communication overhead $\Theta(n^2)$ from the pairwise graph. The ramp design reduces per-user upload by a factor of $g$ at the cost of graceful-degradation secrecy in the ramp zone $(c, n-d)$. For $n = 1000$, $c = 50$, $d = 50$, the savings factor $g = 900$ is dramatic.

This exercise is essentially a sketch of the ByzSecAgg protocol (Chapter 11, CommIT contribution). The full protocol additionally handles Byzantine users via coded outlier detection and vector commitments.